gcc/cgraphunit.c

   1 /* Callgraph based interprocedural optimizations.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
   3    2011 Free Software Foundation, Inc.
   4    Contributed by Jan Hubicka
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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
  36         function.)
  37
  38     - varpool_finalize_variable
  39
  40       This function has same behavior as the above but is used for static
  41       variables.
  42
  43     - cgraph_finalize_compilation_unit
  44
  45       This function is called once (source level) compilation unit is finalized
  46       and it will no longer change.
  47
  48       In the the call-graph construction and local function
  49       analysis takes place here.  Bodies of unreachable functions are released
  50       to conserve memory usage.
  51
  52       The function can be called multiple times when multiple source level
  53       compilation units are combined (such as in C frontend)
  54
  55     - cgraph_optimize
  56
  57       In this unit-at-a-time compilation the intra procedural analysis takes
  58       place here.  In particular the static functions whose address is never
  59       taken are marked as local.  Backend can then use this information to
  60       modify calling conventions, do better inlining or similar optimizations.
  61
  62     - cgraph_mark_needed_node
  63     - varpool_mark_needed_node
  64
  65       When function or variable is referenced by some hidden way the call-graph
  66       data structure must be updated accordingly by this function.
  67       There should be little need to call this function and all the references
  68       should be made explicit to cgraph code.  At present these functions are
  69       used by C++ frontend to explicitly mark the keyed methods.
  70
  71     - analyze_expr callback
  72
  73       This function is responsible for lowering tree nodes not understood by
  74       generic code into understandable ones or alternatively marking
  75       callgraph and varpool nodes referenced by the as needed.
  76
  77       ??? On the tree-ssa genericizing should take place here and we will avoid
  78       need for these hooks (replacing them by genericizing hook)
  79
  80         Analyzing of all functions is deferred
  81         to cgraph_finalize_compilation_unit and expansion into cgraph_optimize.
  82
  83         In cgraph_finalize_compilation_unit the reachable functions are
  84         analyzed.  During analysis the call-graph edges from reachable
  85         functions are constructed and their destinations are marked as
  86         reachable.  References to functions and variables are discovered too
  87         and variables found to be needed output to the assembly file.  Via
  88         mark_referenced call in assemble_variable functions referenced by
  89         static variables are noticed too.
  90
  91         The intra-procedural information is produced and its existence
  92         indicated by global_info_ready.  Once this flag is set it is impossible
  93         to change function from !reachable to reachable and thus
  94         assemble_variable no longer call mark_referenced.
  95
  96         Finally the call-graph is topologically sorted and all reachable functions
  97         that has not been completely inlined or are not external are output.
  98
  99         ??? It is possible that reference to function or variable is optimized
 100         out.  We can not deal with this nicely because topological order is not
 101         suitable for it.  For tree-ssa we may consider another pass doing
 102         optimization and re-discovering reachable functions.
 103
 104         ??? Reorganize code so variables are output very last and only if they
 105         really has been referenced by produced code, so we catch more cases
 106         where reference has been optimized out.  */
 107
 108
 109 #include "config.h"
 110 #include "system.h"
 111 #include "coretypes.h"
 112 #include "tm.h"
 113 #include "tree.h"
 114 #include "rtl.h"
 115 #include "tree-flow.h"
 116 #include "tree-inline.h"
 117 #include "langhooks.h"
 118 #include "pointer-set.h"
 119 #include "toplev.h"
 120 #include "flags.h"
 121 #include "ggc.h"
 122 #include "debug.h"
 123 #include "target.h"
 124 #include "cgraph.h"
 125 #include "diagnostic.h"
 126 #include "tree-pretty-print.h"
 127 #include "gimple-pretty-print.h"
 128 #include "timevar.h"
 129 #include "params.h"
 130 #include "fibheap.h"
 131 #include "intl.h"
 132 #include "function.h"
 133 #include "ipa-prop.h"
 134 #include "gimple.h"
 135 #include "tree-iterator.h"
 136 #include "tree-pass.h"
 137 #include "tree-dump.h"
 138 #include "output.h"
 139 #include "coverage.h"
 140 #include "plugin.h"
 141
 142 static void cgraph_expand_all_functions (void);
 143 static void cgraph_mark_functions_to_output (void);
 144 static void cgraph_expand_function (struct cgraph_node *);
 145 static void cgraph_output_pending_asms (void);
 146
 147 FILE *cgraph_dump_file;
 148
 149 /* Used for vtable lookup in thunk adjusting.  */
 150 static GTY (()) tree vtable_entry_type;
 151
 152 /* Determine if function DECL is needed.  That is, visible to something
 153    either outside this translation unit, something magic in the system
 154    configury.  */
 155
 156 bool
 157 cgraph_decide_is_function_needed (struct cgraph_node *node, tree decl)
 158 {
 159   /* If the user told us it is used, then it must be so.  */
 160   if (node->local.externally_visible)
 161     return true;
 162
 163   /* ??? If the assembler name is set by hand, it is possible to assemble
 164      the name later after finalizing the function and the fact is noticed
 165      in assemble_name then.  This is arguably a bug.  */
 166   if (DECL_ASSEMBLER_NAME_SET_P (decl)
 167       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 168     return true;
 169
 170   /* With -fkeep-inline-functions we are keeping all inline functions except
 171      for extern inline ones.  */
 172   if (flag_keep_inline_functions
 173       && DECL_DECLARED_INLINE_P (decl)
 174       && !DECL_EXTERNAL (decl)
 175       && !lookup_attribute ("always_inline", DECL_ATTRIBUTES (decl)))
 176      return true;
 177
 178   /* If we decided it was needed before, but at the time we didn't have
 179      the body of the function available, then it's still needed.  We have
 180      to go back and re-check its dependencies now.  */
 181   if (node->needed)
 182     return true;
 183
 184   /* Externally visible functions must be output.  The exception is
 185      COMDAT functions that must be output only when they are needed.
 186
 187      When not optimizing, also output the static functions. (see
 188      PR24561), but don't do so for always_inline functions, functions
 189      declared inline and nested functions.  These were optimized out
 190      in the original implementation and it is unclear whether we want
 191      to change the behavior here.  */
 192   if (((TREE_PUBLIC (decl)
 193         || (!optimize
 194             && !node->local.disregard_inline_limits
 195             && !DECL_DECLARED_INLINE_P (decl)
 196             && !(DECL_CONTEXT (decl)
 197                  && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)))
 198        && !flag_whole_program
 199        && !flag_lto)
 200       && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 201     return true;
 202
 203   return false;
 204 }
 205
 206 /* Process CGRAPH_NEW_FUNCTIONS and perform actions necessary to add these
 207    functions into callgraph in a way so they look like ordinary reachable
 208    functions inserted into callgraph already at construction time.  */
 209
 210 bool
 211 cgraph_process_new_functions (void)
 212 {
 213   bool output = false;
 214   tree fndecl;
 215   struct cgraph_node *node;
 216
 217   varpool_analyze_pending_decls ();
 218   /*  Note that this queue may grow as its being processed, as the new
 219       functions may generate new ones.  */
 220   while (cgraph_new_nodes)
 221     {
 222       node = cgraph_new_nodes;
 223       fndecl = node->decl;
 224       cgraph_new_nodes = cgraph_new_nodes->next_needed;
 225       switch (cgraph_state)
 226         {
 227         case CGRAPH_STATE_CONSTRUCTION:
 228           /* At construction time we just need to finalize function and move
 229              it into reachable functions list.  */
 230
 231           node->next_needed = NULL;
 232           cgraph_finalize_function (fndecl, false);
 233           cgraph_mark_reachable_node (node);
 234           output = true;
 235           break;
 236
 237         case CGRAPH_STATE_IPA:
 238         case CGRAPH_STATE_IPA_SSA:
 239           /* When IPA optimization already started, do all essential
 240              transformations that has been already performed on the whole
 241              cgraph but not on this function.  */
 242
 243           gimple_register_cfg_hooks ();
 244           if (!node->analyzed)
 245             cgraph_analyze_function (node);
 246           push_cfun (DECL_STRUCT_FUNCTION (fndecl));
 247           current_function_decl = fndecl;
 248           if ((cgraph_state == CGRAPH_STATE_IPA_SSA
 249               && !gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
 250               /* When not optimizing, be sure we run early local passes anyway
 251                  to expand OMP.  */
 252               || !optimize)
 253             execute_pass_list (pass_early_local_passes.pass.sub);
 254           else
 255             compute_inline_parameters (node);
 256           free_dominance_info (CDI_POST_DOMINATORS);
 257           free_dominance_info (CDI_DOMINATORS);
 258           pop_cfun ();
 259           current_function_decl = NULL;
 260           break;
 261
 262         case CGRAPH_STATE_EXPANSION:
 263           /* Functions created during expansion shall be compiled
 264              directly.  */
 265           node->process = 0;
 266           cgraph_expand_function (node);
 267           break;
 268
 269         default:
 270           gcc_unreachable ();
 271           break;
 272         }
 273       cgraph_call_function_insertion_hooks (node);
 274       varpool_analyze_pending_decls ();
 275     }
 276   return output;
 277 }
 278
 279 /* As an GCC extension we allow redefinition of the function.  The
 280    semantics when both copies of bodies differ is not well defined.
 281    We replace the old body with new body so in unit at a time mode
 282    we always use new body, while in normal mode we may end up with
 283    old body inlined into some functions and new body expanded and
 284    inlined in others.
 285
 286    ??? It may make more sense to use one body for inlining and other
 287    body for expanding the function but this is difficult to do.  */
 288
 289 static void
 290 cgraph_reset_node (struct cgraph_node *node)
 291 {
 292   /* If node->process is set, then we have already begun whole-unit analysis.
 293      This is *not* testing for whether we've already emitted the function.
 294      That case can be sort-of legitimately seen with real function redefinition
 295      errors.  I would argue that the front end should never present us with
 296      such a case, but don't enforce that for now.  */
 297   gcc_assert (!node->process);
 298
 299   /* Reset our data structures so we can analyze the function again.  */
 300   memset (&node->local, 0, sizeof (node->local));
 301   memset (&node->global, 0, sizeof (node->global));
 302   memset (&node->rtl, 0, sizeof (node->rtl));
 303   node->analyzed = false;
 304   node->local.redefined_extern_inline = true;
 305   node->local.finalized = false;
 306
 307   cgraph_node_remove_callees (node);
 308
 309   /* We may need to re-queue the node for assembling in case
 310      we already proceeded it and ignored as not needed or got
 311      a re-declaration in IMA mode.  */
 312   if (node->reachable)
 313     {
 314       struct cgraph_node *n;
 315
 316       for (n = cgraph_nodes_queue; n; n = n->next_needed)
 317         if (n == node)
 318           break;
 319       if (!n)
 320         node->reachable = 0;
 321     }
 322 }
 323
 324 static void
 325 cgraph_lower_function (struct cgraph_node *node)
 326 {
 327   if (node->lowered)
 328     return;
 329
 330   if (node->nested)
 331     lower_nested_functions (node->decl);
 332   gcc_assert (!node->nested);
 333
 334   tree_lowering_passes (node->decl);
 335   node->lowered = true;
 336 }
 337
 338 /* DECL has been parsed.  Take it, queue it, compile it at the whim of the
 339    logic in effect.  If NESTED is true, then our caller cannot stand to have
 340    the garbage collector run at the moment.  We would need to either create
 341    a new GC context, or just not compile right now.  */
 342
 343 void
 344 cgraph_finalize_function (tree decl, bool nested)
 345 {
 346   struct cgraph_node *node = cgraph_node (decl);
 347
 348   if (node->local.finalized)
 349     cgraph_reset_node (node);
 350
 351   node->pid = cgraph_max_pid ++;
 352   notice_global_symbol (decl);
 353   node->local.finalized = true;
 354   node->lowered = DECL_STRUCT_FUNCTION (decl)->cfg != NULL;
 355   node->finalized_by_frontend = true;
 356
 357   if (cgraph_decide_is_function_needed (node, decl))
 358     cgraph_mark_needed_node (node);
 359
 360   /* Since we reclaim unreachable nodes at the end of every language
 361      level unit, we need to be conservative about possible entry points
 362      there.  */
 363   if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 364       || DECL_STATIC_CONSTRUCTOR (decl)
 365       || DECL_STATIC_DESTRUCTOR (decl)
 366       /* COMDAT virtual functions may be referenced by vtable from
 367          other compilation unit.  Still we want to devirtualize calls
 368          to those so we need to analyze them.
 369          FIXME: We should introduce may edges for this purpose and update
 370          their handling in unreachable function removal and inliner too.  */
 371       || (DECL_VIRTUAL_P (decl) && (DECL_COMDAT (decl) || DECL_EXTERNAL (decl))))
 372     cgraph_mark_reachable_node (node);
 373
 374   /* If we've not yet emitted decl, tell the debug info about it.  */
 375   if (!TREE_ASM_WRITTEN (decl))
 376     (*debug_hooks->deferred_inline_function) (decl);
 377
 378   /* Possibly warn about unused parameters.  */
 379   if (warn_unused_parameter)
 380     do_warn_unused_parameter (decl);
 381
 382   if (!nested)
 383     ggc_collect ();
 384 }
 385
 386 /* C99 extern inline keywords allow changing of declaration after function
 387    has been finalized.  We need to re-decide if we want to mark the function as
 388    needed then.   */
 389
 390 void
 391 cgraph_mark_if_needed (tree decl)
 392 {
 393   struct cgraph_node *node = cgraph_node (decl);
 394   if (node->local.finalized && cgraph_decide_is_function_needed (node, decl))
 395     cgraph_mark_needed_node (node);
 396 }
 397
 398 /* Return TRUE if NODE2 is equivalent to NODE or its clone.  */
 399 static bool
 400 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
 401 {
 402   while (node != node2 && node2)
 403     node2 = node2->clone_of;
 404   return node2 != NULL;
 405 }
 406
 407 /* Verify edge E count and frequency.  */
 408
 409 static bool
 410 verify_edge_count_and_frequency (struct cgraph_edge *e)
 411 {
 412   bool error_found = false;
 413   if (e->count < 0)
 414     {
 415       error ("caller edge count is negative");
 416       error_found = true;
 417     }
 418   if (e->frequency < 0)
 419     {
 420       error ("caller edge frequency is negative");
 421       error_found = true;
 422     }
 423   if (e->frequency > CGRAPH_FREQ_MAX)
 424     {
 425       error ("caller edge frequency is too large");
 426       error_found = true;
 427     }
 428   if (gimple_has_body_p (e->caller->decl)
 429       && !e->caller->global.inlined_to
 430       && (e->frequency
 431           != compute_call_stmt_bb_frequency (e->caller->decl,
 432                                              gimple_bb (e->call_stmt))))
 433     {
 434       error ("caller edge frequency %i does not match BB frequency %i",
 435              e->frequency,
 436              compute_call_stmt_bb_frequency (e->caller->decl,
 437                                              gimple_bb (e->call_stmt)));
 438       error_found = true;
 439     }
 440   return error_found;
 441 }
 442
 443 /* Switch to THIS_CFUN if needed and print STMT to stderr.  */
 444 static void
 445 cgraph_debug_gimple_stmt (struct function *this_cfun, gimple stmt)
 446 {
 447   /* debug_gimple_stmt needs correct cfun */
 448   if (cfun != this_cfun)
 449     set_cfun (this_cfun);
 450   debug_gimple_stmt (stmt);
 451 }
 452
 453 /* Verify cgraph nodes of given cgraph node.  */
 454 DEBUG_FUNCTION void
 455 verify_cgraph_node (struct cgraph_node *node)
 456 {
 457   struct cgraph_edge *e;
 458   struct function *this_cfun = DECL_STRUCT_FUNCTION (node->decl);
 459   basic_block this_block;
 460   gimple_stmt_iterator gsi;
 461   bool error_found = false;
 462
 463   if (seen_error ())
 464     return;
 465
 466   timevar_push (TV_CGRAPH_VERIFY);
 467   for (e = node->callees; e; e = e->next_callee)
 468     if (e->aux)
 469       {
 470         error ("aux field set for edge %s->%s",
 471                identifier_to_locale (cgraph_node_name (e->caller)),
 472                identifier_to_locale (cgraph_node_name (e->callee)));
 473         error_found = true;
 474       }
 475   if (node->count < 0)
 476     {
 477       error ("execution count is negative");
 478       error_found = true;
 479     }
 480   if (node->global.inlined_to && node->local.externally_visible)
 481     {
 482       error ("externally visible inline clone");
 483       error_found = true;
 484     }
 485   if (node->global.inlined_to && node->address_taken)
 486     {
 487       error ("inline clone with address taken");
 488       error_found = true;
 489     }
 490   if (node->global.inlined_to && node->needed)
 491     {
 492       error ("inline clone is needed");
 493       error_found = true;
 494     }
 495   for (e = node->indirect_calls; e; e = e->next_callee)
 496     {
 497       if (e->aux)
 498         {
 499           error ("aux field set for indirect edge from %s",
 500                  identifier_to_locale (cgraph_node_name (e->caller)));
 501           error_found = true;
 502         }
 503       if (!e->indirect_unknown_callee
 504           || !e->indirect_info)
 505         {
 506           error ("An indirect edge from %s is not marked as indirect or has "
 507                  "associated indirect_info, the corresponding statement is: ",
 508                  identifier_to_locale (cgraph_node_name (e->caller)));
 509           cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
 510           error_found = true;
 511         }
 512     }
 513   for (e = node->callers; e; e = e->next_caller)
 514     {
 515       if (verify_edge_count_and_frequency (e))
 516         error_found = true;
 517       if (!e->inline_failed)
 518         {
 519           if (node->global.inlined_to
 520               != (e->caller->global.inlined_to
 521                   ? e->caller->global.inlined_to : e->caller))
 522             {
 523               error ("inlined_to pointer is wrong");
 524               error_found = true;
 525             }
 526           if (node->callers->next_caller)
 527             {
 528               error ("multiple inline callers");
 529               error_found = true;
 530             }
 531         }
 532       else
 533         if (node->global.inlined_to)
 534           {
 535             error ("inlined_to pointer set for noninline callers");
 536             error_found = true;
 537           }
 538     }
 539   for (e = node->indirect_calls; e; e = e->next_callee)
 540     if (verify_edge_count_and_frequency (e))
 541       error_found = true;
 542   if (!node->callers && node->global.inlined_to)
 543     {
 544       error ("inlined_to pointer is set but no predecessors found");
 545       error_found = true;
 546     }
 547   if (node->global.inlined_to == node)
 548     {
 549       error ("inlined_to pointer refers to itself");
 550       error_found = true;
 551     }
 552
 553   if (!cgraph_get_node (node->decl))
 554     {
 555       error ("node not found in cgraph_hash");
 556       error_found = true;
 557     }
 558
 559   if (node->clone_of)
 560     {
 561       struct cgraph_node *n;
 562       for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
 563         if (n == node)
 564           break;
 565       if (!n)
 566         {
 567           error ("node has wrong clone_of");
 568           error_found = true;
 569         }
 570     }
 571   if (node->clones)
 572     {
 573       struct cgraph_node *n;
 574       for (n = node->clones; n; n = n->next_sibling_clone)
 575         if (n->clone_of != node)
 576           break;
 577       if (n)
 578         {
 579           error ("node has wrong clone list");
 580           error_found = true;
 581         }
 582     }
 583   if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
 584     {
 585        error ("node is in clone list but it is not clone");
 586        error_found = true;
 587     }
 588   if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
 589     {
 590       error ("node has wrong prev_clone pointer");
 591       error_found = true;
 592     }
 593   if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
 594     {
 595       error ("double linked list of clones corrupted");
 596       error_found = true;
 597     }
 598   if (node->same_comdat_group)
 599     {
 600       struct cgraph_node *n = node->same_comdat_group;
 601
 602       if (!DECL_ONE_ONLY (node->decl))
 603         {
 604           error ("non-DECL_ONE_ONLY node in a same_comdat_group list");
 605           error_found = true;
 606         }
 607       if (n == node)
 608         {
 609           error ("node is alone in a comdat group");
 610           error_found = true;
 611         }
 612       do
 613         {
 614           if (!n->same_comdat_group)
 615             {
 616               error ("same_comdat_group is not a circular list");
 617               error_found = true;
 618               break;
 619             }
 620           n = n->same_comdat_group;
 621         }
 622       while (n != node);
 623     }
 624
 625   if (node->analyzed && gimple_has_body_p (node->decl)
 626       && !TREE_ASM_WRITTEN (node->decl)
 627       && (!DECL_EXTERNAL (node->decl) || node->global.inlined_to)
 628       && !flag_wpa)
 629     {
 630       if (this_cfun->cfg)
 631         {
 632           /* The nodes we're interested in are never shared, so walk
 633              the tree ignoring duplicates.  */
 634           struct pointer_set_t *visited_nodes = pointer_set_create ();
 635           /* Reach the trees by walking over the CFG, and note the
 636              enclosing basic-blocks in the call edges.  */
 637           FOR_EACH_BB_FN (this_block, this_cfun)
 638             for (gsi = gsi_start_bb (this_block);
 639                  !gsi_end_p (gsi);
 640                  gsi_next (&gsi))
 641               {
 642                 gimple stmt = gsi_stmt (gsi);
 643                 if (is_gimple_call (stmt))
 644                   {
 645                     struct cgraph_edge *e = cgraph_edge (node, stmt);
 646                     tree decl = gimple_call_fndecl (stmt);
 647                     if (e)
 648                       {
 649                         if (e->aux)
 650                           {
 651                             error ("shared call_stmt:");
 652                             cgraph_debug_gimple_stmt (this_cfun, stmt);
 653                             error_found = true;
 654                           }
 655                         if (!e->indirect_unknown_callee)
 656                           {
 657                             struct cgraph_node *n;
 658
 659                             if (e->callee->same_body_alias)
 660                               {
 661                                 error ("edge points to same body alias:");
 662                                 debug_tree (e->callee->decl);
 663                                 error_found = true;
 664                               }
 665                             else if (!e->callee->global.inlined_to
 666                                      && decl
 667                                      && cgraph_get_node (decl)
 668                                      && (e->callee->former_clone_of
 669                                          != cgraph_get_node (decl)->decl)
 670                                      && !clone_of_p (cgraph_node (decl),
 671                                                      e->callee))
 672                               {
 673                                 error ("edge points to wrong declaration:");
 674                                 debug_tree (e->callee->decl);
 675                                 fprintf (stderr," Instead of:");
 676                                 debug_tree (decl);
 677                                 error_found = true;
 678                               }
 679                             else if (decl
 680                                      && (n = cgraph_get_node_or_alias (decl))
 681                                      && (n->same_body_alias
 682                                          && n->thunk.thunk_p))
 683                               {
 684                                 error ("a call to thunk improperly represented "
 685                                        "in the call graph:");
 686                                 cgraph_debug_gimple_stmt (this_cfun, stmt);
 687                                 error_found = true;
 688                               }
 689                           }
 690                         else if (decl)
 691                           {
 692                             error ("an indirect edge with unknown callee "
 693                                    "corresponding to a call_stmt with "
 694                                    "a known declaration:");
 695                             error_found = true;
 696                             cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
 697                           }
 698                         e->aux = (void *)1;
 699                       }
 700                     else if (decl)
 701                       {
 702                         error ("missing callgraph edge for call stmt:");
 703                         cgraph_debug_gimple_stmt (this_cfun, stmt);
 704                         error_found = true;
 705                       }
 706                   }
 707               }
 708           pointer_set_destroy (visited_nodes);
 709         }
 710       else
 711         /* No CFG available?!  */
 712         gcc_unreachable ();
 713
 714       for (e = node->callees; e; e = e->next_callee)
 715         {
 716           if (!e->aux)
 717             {
 718               error ("edge %s->%s has no corresponding call_stmt",
 719                      identifier_to_locale (cgraph_node_name (e->caller)),
 720                      identifier_to_locale (cgraph_node_name (e->callee)));
 721               cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
 722               error_found = true;
 723             }
 724           e->aux = 0;
 725         }
 726       for (e = node->indirect_calls; e; e = e->next_callee)
 727         {
 728           if (!e->aux)
 729             {
 730               error ("an indirect edge from %s has no corresponding call_stmt",
 731                      identifier_to_locale (cgraph_node_name (e->caller)));
 732               cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
 733               error_found = true;
 734             }
 735           e->aux = 0;
 736         }
 737     }
 738   if (error_found)
 739     {
 740       dump_cgraph_node (stderr, node);
 741       internal_error ("verify_cgraph_node failed");
 742     }
 743   timevar_pop (TV_CGRAPH_VERIFY);
 744 }
 745
 746 /* Verify whole cgraph structure.  */
 747 DEBUG_FUNCTION void
 748 verify_cgraph (void)
 749 {
 750   struct cgraph_node *node;
 751
 752   if (seen_error ())
 753     return;
 754
 755   for (node = cgraph_nodes; node; node = node->next)
 756     verify_cgraph_node (node);
 757 }
 758
 759 /* Output all asm statements we have stored up to be output.  */
 760
 761 static void
 762 cgraph_output_pending_asms (void)
 763 {
 764   struct cgraph_asm_node *can;
 765
 766   if (seen_error ())
 767     return;
 768
 769   for (can = cgraph_asm_nodes; can; can = can->next)
 770     assemble_asm (can->asm_str);
 771   cgraph_asm_nodes = NULL;
 772 }
 773
 774 /* Analyze the function scheduled to be output.  */
 775 void
 776 cgraph_analyze_function (struct cgraph_node *node)
 777 {
 778   tree save = current_function_decl;
 779   tree decl = node->decl;
 780
 781   current_function_decl = decl;
 782   push_cfun (DECL_STRUCT_FUNCTION (decl));
 783
 784   assign_assembler_name_if_neeeded (node->decl);
 785
 786   /* disregard_inline_limits affects topological order of the early optimization,
 787      so we need to compute it ahead of rest of inline parameters.  */
 788   node->local.disregard_inline_limits
 789     = DECL_DISREGARD_INLINE_LIMITS (node->decl);
 790
 791   /* Make sure to gimplify bodies only once.  During analyzing a
 792      function we lower it, which will require gimplified nested
 793      functions, so we can end up here with an already gimplified
 794      body.  */
 795   if (!gimple_body (decl))
 796     gimplify_function_tree (decl);
 797   dump_function (TDI_generic, decl);
 798
 799   cgraph_lower_function (node);
 800   node->analyzed = true;
 801
 802   pop_cfun ();
 803   current_function_decl = save;
 804 }
 805
 806 /* Process attributes common for vars and functions.  */
 807
 808 static void
 809 process_common_attributes (tree decl)
 810 {
 811   tree weakref = lookup_attribute ("weakref", DECL_ATTRIBUTES (decl));
 812
 813   if (weakref && !lookup_attribute ("alias", DECL_ATTRIBUTES (decl)))
 814     {
 815       warning_at (DECL_SOURCE_LOCATION (decl), OPT_Wattributes,
 816                   "%<weakref%> attribute should be accompanied with"
 817                   " an %<alias%> attribute");
 818       DECL_WEAK (decl) = 0;
 819       DECL_ATTRIBUTES (decl) = remove_attribute ("weakref",
 820                                                  DECL_ATTRIBUTES (decl));
 821     }
 822 }
 823
 824 /* Look for externally_visible and used attributes and mark cgraph nodes
 825    accordingly.
 826
 827    We cannot mark the nodes at the point the attributes are processed (in
 828    handle_*_attribute) because the copy of the declarations available at that
 829    point may not be canonical.  For example, in:
 830
 831     void f();
 832     void f() __attribute__((used));
 833
 834    the declaration we see in handle_used_attribute will be the second
 835    declaration -- but the front end will subsequently merge that declaration
 836    with the original declaration and discard the second declaration.
 837
 838    Furthermore, we can't mark these nodes in cgraph_finalize_function because:
 839
 840     void f() {}
 841     void f() __attribute__((externally_visible));
 842
 843    is valid.
 844
 845    So, we walk the nodes at the end of the translation unit, applying the
 846    attributes at that point.  */
 847
 848 static void
 849 process_function_and_variable_attributes (struct cgraph_node *first,
 850                                           struct varpool_node *first_var)
 851 {
 852   struct cgraph_node *node;
 853   struct varpool_node *vnode;
 854
 855   for (node = cgraph_nodes; node != first; node = node->next)
 856     {
 857       tree decl = node->decl;
 858       if (DECL_PRESERVE_P (decl))
 859         cgraph_mark_needed_node (node);
 860       if (TARGET_DLLIMPORT_DECL_ATTRIBUTES
 861           && lookup_attribute ("dllexport", DECL_ATTRIBUTES (decl))
 862           && TREE_PUBLIC (node->decl))
 863         {
 864           if (node->local.finalized)
 865             cgraph_mark_needed_node (node);
 866         }
 867       else if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
 868         {
 869           if (! TREE_PUBLIC (node->decl))
 870             warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
 871                         "%<externally_visible%>"
 872                         " attribute have effect only on public objects");
 873           else if (node->local.finalized)
 874              cgraph_mark_needed_node (node);
 875         }
 876       if (lookup_attribute ("weakref", DECL_ATTRIBUTES (decl))
 877           && node->local.finalized)
 878         {
 879           warning_at (DECL_SOURCE_LOCATION (node->decl), OPT_Wattributes,
 880                       "%<weakref%> attribute ignored"
 881                       " because function is defined");
 882           DECL_WEAK (decl) = 0;
 883           DECL_ATTRIBUTES (decl) = remove_attribute ("weakref",
 884                                                      DECL_ATTRIBUTES (decl));
 885         }
 886       process_common_attributes (decl);
 887     }
 888   for (vnode = varpool_nodes; vnode != first_var; vnode = vnode->next)
 889     {
 890       tree decl = vnode->decl;
 891       if (DECL_PRESERVE_P (decl))
 892         {
 893           vnode->force_output = true;
 894           if (vnode->finalized)
 895             varpool_mark_needed_node (vnode);
 896         }
 897       if (TARGET_DLLIMPORT_DECL_ATTRIBUTES
 898           && lookup_attribute ("dllexport", DECL_ATTRIBUTES (decl))
 899           && TREE_PUBLIC (vnode->decl))
 900         {
 901           if (vnode->finalized)
 902             varpool_mark_needed_node (vnode);
 903         }
 904       else if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (decl)))
 905         {
 906           if (! TREE_PUBLIC (vnode->decl))
 907             warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
 908                         "%<externally_visible%>"
 909                         " attribute have effect only on public objects");
 910           else if (vnode->finalized)
 911             varpool_mark_needed_node (vnode);
 912         }
 913       if (lookup_attribute ("weakref", DECL_ATTRIBUTES (decl))
 914           && vnode->finalized
 915           && DECL_INITIAL (decl))
 916         {
 917           warning_at (DECL_SOURCE_LOCATION (vnode->decl), OPT_Wattributes,
 918                       "%<weakref%> attribute ignored"
 919                       " because variable is initialized");
 920           DECL_WEAK (decl) = 0;
 921           DECL_ATTRIBUTES (decl) = remove_attribute ("weakref",
 922                                                       DECL_ATTRIBUTES (decl));
 923         }
 924       process_common_attributes (decl);
 925     }
 926 }
 927
 928 /* Process CGRAPH_NODES_NEEDED queue, analyze each function (and transitively
 929    each reachable functions) and build cgraph.
 930    The function can be called multiple times after inserting new nodes
 931    into beginning of queue.  Just the new part of queue is re-scanned then.  */
 932
 933 static void
 934 cgraph_analyze_functions (void)
 935 {
 936   /* Keep track of already processed nodes when called multiple times for
 937      intermodule optimization.  */
 938   static struct cgraph_node *first_analyzed;
 939   struct cgraph_node *first_processed = first_analyzed;
 940   static struct varpool_node *first_analyzed_var;
 941   struct cgraph_node *node, *next;
 942
 943   bitmap_obstack_initialize (NULL);
 944   process_function_and_variable_attributes (first_processed,
 945                                             first_analyzed_var);
 946   first_processed = cgraph_nodes;
 947   first_analyzed_var = varpool_nodes;
 948   varpool_analyze_pending_decls ();
 949   if (cgraph_dump_file)
 950     {
 951       fprintf (cgraph_dump_file, "Initial entry points:");
 952       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
 953         if (node->needed)
 954           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
 955       fprintf (cgraph_dump_file, "\n");
 956     }
 957   cgraph_process_new_functions ();
 958
 959   /* Propagate reachability flag and lower representation of all reachable
 960      functions.  In the future, lowering will introduce new functions and
 961      new entry points on the way (by template instantiation and virtual
 962      method table generation for instance).  */
 963   while (cgraph_nodes_queue)
 964     {
 965       struct cgraph_edge *edge;
 966       tree decl = cgraph_nodes_queue->decl;
 967
 968       node = cgraph_nodes_queue;
 969       cgraph_nodes_queue = cgraph_nodes_queue->next_needed;
 970       node->next_needed = NULL;
 971
 972       /* ??? It is possible to create extern inline function and later using
 973          weak alias attribute to kill its body. See
 974          gcc.c-torture/compile/20011119-1.c  */
 975       if (!DECL_STRUCT_FUNCTION (decl))
 976         {
 977           cgraph_reset_node (node);
 978           continue;
 979         }
 980
 981       if (!node->analyzed)
 982         cgraph_analyze_function (node);
 983
 984       for (edge = node->callees; edge; edge = edge->next_callee)
 985         if (!edge->callee->reachable)
 986           cgraph_mark_reachable_node (edge->callee);
 987
 988       if (node->same_comdat_group)
 989         {
 990           for (next = node->same_comdat_group;
 991                next != node;
 992                next = next->same_comdat_group)
 993             cgraph_mark_reachable_node (next);
 994         }
 995
 996       /* If decl is a clone of an abstract function, mark that abstract
 997          function so that we don't release its body. The DECL_INITIAL() of that
 998          abstract function declaration will be later needed to output debug info.  */
 999       if (DECL_ABSTRACT_ORIGIN (decl))
1000         {
1001           struct cgraph_node *origin_node = cgraph_node (DECL_ABSTRACT_ORIGIN (decl));
1002           origin_node->abstract_and_needed = true;
1003         }
1004
1005       /* We finalize local static variables during constructing callgraph
1006          edges.  Process their attributes too.  */
1007       process_function_and_variable_attributes (first_processed,
1008                                                 first_analyzed_var);
1009       first_processed = cgraph_nodes;
1010       first_analyzed_var = varpool_nodes;
1011       varpool_analyze_pending_decls ();
1012       cgraph_process_new_functions ();
1013     }
1014
1015   /* Collect entry points to the unit.  */
1016   if (cgraph_dump_file)
1017     {
1018       fprintf (cgraph_dump_file, "Unit entry points:");
1019       for (node = cgraph_nodes; node != first_analyzed; node = node->next)
1020         if (node->needed)
1021           fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1022       fprintf (cgraph_dump_file, "\n\nInitial ");
1023       dump_cgraph (cgraph_dump_file);
1024       dump_varpool (cgraph_dump_file);
1025     }
1026
1027   if (cgraph_dump_file)
1028     fprintf (cgraph_dump_file, "\nReclaiming functions:");
1029
1030   for (node = cgraph_nodes; node != first_analyzed; node = next)
1031     {
1032       tree decl = node->decl;
1033       next = node->next;
1034
1035       if (node->local.finalized && !gimple_has_body_p (decl))
1036         cgraph_reset_node (node);
1037
1038       if (!node->reachable && gimple_has_body_p (decl))
1039         {
1040           if (cgraph_dump_file)
1041             fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
1042           cgraph_remove_node (node);
1043           continue;
1044         }
1045       else
1046         node->next_needed = NULL;
1047       gcc_assert (!node->local.finalized || gimple_has_body_p (decl));
1048       gcc_assert (node->analyzed == node->local.finalized);
1049     }
1050   if (cgraph_dump_file)
1051     {
1052       fprintf (cgraph_dump_file, "\n\nReclaimed ");
1053       dump_cgraph (cgraph_dump_file);
1054       dump_varpool (cgraph_dump_file);
1055     }
1056   bitmap_obstack_release (NULL);
1057   first_analyzed = cgraph_nodes;
1058   ggc_collect ();
1059 }
1060
1061
1062 /* Analyze the whole compilation unit once it is parsed completely.  */
1063
1064 void
1065 cgraph_finalize_compilation_unit (void)
1066 {
1067   timevar_push (TV_CGRAPH);
1068
1069   /* Do not skip analyzing the functions if there were errors, we
1070      miss diagnostics for following functions otherwise.  */
1071
1072   /* Emit size functions we didn't inline.  */
1073   finalize_size_functions ();
1074
1075   /* Mark alias targets necessary and emit diagnostics.  */
1076   finish_aliases_1 ();
1077
1078   if (!quiet_flag)
1079     {
1080       fprintf (stderr, "\nAnalyzing compilation unit\n");
1081       fflush (stderr);
1082     }
1083
1084   /* Gimplify and lower all functions, compute reachability and
1085      remove unreachable nodes.  */
1086   cgraph_analyze_functions ();
1087
1088   /* Mark alias targets necessary and emit diagnostics.  */
1089   finish_aliases_1 ();
1090
1091   /* Gimplify and lower thunks.  */
1092   cgraph_analyze_functions ();
1093
1094   /* Finally drive the pass manager.  */
1095   cgraph_optimize ();
1096
1097   timevar_pop (TV_CGRAPH);
1098 }
1099
1100
1101 /* Figure out what functions we want to assemble.  */
1102
1103 static void
1104 cgraph_mark_functions_to_output (void)
1105 {
1106   struct cgraph_node *node;
1107 #ifdef ENABLE_CHECKING
1108   bool check_same_comdat_groups = false;
1109
1110   for (node = cgraph_nodes; node; node = node->next)
1111     gcc_assert (!node->process);
1112 #endif
1113
1114   for (node = cgraph_nodes; node; node = node->next)
1115     {
1116       tree decl = node->decl;
1117       struct cgraph_edge *e;
1118
1119       gcc_assert (!node->process || node->same_comdat_group);
1120       if (node->process)
1121         continue;
1122
1123       for (e = node->callers; e; e = e->next_caller)
1124         if (e->inline_failed)
1125           break;
1126
1127       /* We need to output all local functions that are used and not
1128          always inlined, as well as those that are reachable from
1129          outside the current compilation unit.  */
1130       if (node->analyzed
1131           && !node->global.inlined_to
1132           && (!cgraph_only_called_directly_p (node)
1133               || (e && node->reachable))
1134           && !TREE_ASM_WRITTEN (decl)
1135           && !DECL_EXTERNAL (decl))
1136         {
1137           node->process = 1;
1138           if (node->same_comdat_group)
1139             {
1140               struct cgraph_node *next;
1141               for (next = node->same_comdat_group;
1142                    next != node;
1143                    next = next->same_comdat_group)
1144                 next->process = 1;
1145             }
1146         }
1147       else if (node->same_comdat_group)
1148         {
1149 #ifdef ENABLE_CHECKING
1150           check_same_comdat_groups = true;
1151 #endif
1152         }
1153       else
1154         {
1155           /* We should've reclaimed all functions that are not needed.  */
1156 #ifdef ENABLE_CHECKING
1157           if (!node->global.inlined_to
1158               && gimple_has_body_p (decl)
1159               /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1160                  are inside partition, we can end up not removing the body since we no longer
1161                  have analyzed node pointing to it.  */
1162               && !node->in_other_partition
1163               && !DECL_EXTERNAL (decl))
1164             {
1165               dump_cgraph_node (stderr, node);
1166               internal_error ("failed to reclaim unneeded function");
1167             }
1168 #endif
1169           gcc_assert (node->global.inlined_to
1170                       || !gimple_has_body_p (decl)
1171                       || node->in_other_partition
1172                       || DECL_EXTERNAL (decl));
1173
1174         }
1175
1176     }
1177 #ifdef ENABLE_CHECKING
1178   if (check_same_comdat_groups)
1179     for (node = cgraph_nodes; node; node = node->next)
1180       if (node->same_comdat_group && !node->process)
1181         {
1182           tree decl = node->decl;
1183           if (!node->global.inlined_to
1184               && gimple_has_body_p (decl)
1185               /* FIXME: in ltrans unit when offline copy is outside partition but inline copies
1186                  are inside partition, we can end up not removing the body since we no longer
1187                  have analyzed node pointing to it.  */
1188               && !node->in_other_partition
1189               && !DECL_EXTERNAL (decl))
1190             {
1191               dump_cgraph_node (stderr, node);
1192               internal_error ("failed to reclaim unneeded function");
1193             }
1194         }
1195 #endif
1196 }
1197
1198 /* DECL is FUNCTION_DECL.  Initialize datastructures so DECL is a function
1199    in lowered gimple form.
1200
1201    Set current_function_decl and cfun to newly constructed empty function body.
1202    return basic block in the function body.  */
1203
1204 static basic_block
1205 init_lowered_empty_function (tree decl)
1206 {
1207   basic_block bb;
1208
1209   current_function_decl = decl;
1210   allocate_struct_function (decl, false);
1211   gimple_register_cfg_hooks ();
1212   init_empty_tree_cfg ();
1213   init_tree_ssa (cfun);
1214   init_ssa_operands ();
1215   cfun->gimple_df->in_ssa_p = true;
1216   DECL_INITIAL (decl) = make_node (BLOCK);
1217
1218   DECL_SAVED_TREE (decl) = error_mark_node;
1219   cfun->curr_properties |=
1220     (PROP_gimple_lcf | PROP_gimple_leh | PROP_cfg | PROP_referenced_vars |
1221      PROP_ssa);
1222
1223   /* Create BB for body of the function and connect it properly.  */
1224   bb = create_basic_block (NULL, (void *) 0, ENTRY_BLOCK_PTR);
1225   make_edge (ENTRY_BLOCK_PTR, bb, 0);
1226   make_edge (bb, EXIT_BLOCK_PTR, 0);
1227
1228   return bb;
1229 }
1230
1231 /* Adjust PTR by the constant FIXED_OFFSET, and by the vtable
1232    offset indicated by VIRTUAL_OFFSET, if that is
1233    non-null. THIS_ADJUSTING is nonzero for a this adjusting thunk and
1234    zero for a result adjusting thunk.  */
1235
1236 static tree
1237 thunk_adjust (gimple_stmt_iterator * bsi,
1238               tree ptr, bool this_adjusting,
1239               HOST_WIDE_INT fixed_offset, tree virtual_offset)
1240 {
1241   gimple stmt;
1242   tree ret;
1243
1244   if (this_adjusting
1245       && fixed_offset != 0)
1246     {
1247       stmt = gimple_build_assign (ptr,
1248                                   fold_build2_loc (input_location,
1249                                                    POINTER_PLUS_EXPR,
1250                                                    TREE_TYPE (ptr), ptr,
1251                                                    size_int (fixed_offset)));
1252       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1253     }
1254
1255   /* If there's a virtual offset, look up that value in the vtable and
1256      adjust the pointer again.  */
1257   if (virtual_offset)
1258     {
1259       tree vtabletmp;
1260       tree vtabletmp2;
1261       tree vtabletmp3;
1262       tree offsettmp;
1263
1264       if (!vtable_entry_type)
1265         {
1266           tree vfunc_type = make_node (FUNCTION_TYPE);
1267           TREE_TYPE (vfunc_type) = integer_type_node;
1268           TYPE_ARG_TYPES (vfunc_type) = NULL_TREE;
1269           layout_type (vfunc_type);
1270
1271           vtable_entry_type = build_pointer_type (vfunc_type);
1272         }
1273
1274       vtabletmp =
1275         create_tmp_var (build_pointer_type
1276                         (build_pointer_type (vtable_entry_type)), "vptr");
1277
1278       /* The vptr is always at offset zero in the object.  */
1279       stmt = gimple_build_assign (vtabletmp,
1280                                   build1 (NOP_EXPR, TREE_TYPE (vtabletmp),
1281                                           ptr));
1282       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1283       mark_symbols_for_renaming (stmt);
1284       find_referenced_vars_in (stmt);
1285
1286       /* Form the vtable address.  */
1287       vtabletmp2 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp)),
1288                                    "vtableaddr");
1289       stmt = gimple_build_assign (vtabletmp2,
1290                                   build_simple_mem_ref (vtabletmp));
1291       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1292       mark_symbols_for_renaming (stmt);
1293       find_referenced_vars_in (stmt);
1294
1295       /* Find the entry with the vcall offset.  */
1296       stmt = gimple_build_assign (vtabletmp2,
1297                                   fold_build2_loc (input_location,
1298                                                    POINTER_PLUS_EXPR,
1299                                                    TREE_TYPE (vtabletmp2),
1300                                                    vtabletmp2,
1301                                                    fold_convert (sizetype,
1302                                                                  virtual_offset)));
1303       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1304
1305       /* Get the offset itself.  */
1306       vtabletmp3 = create_tmp_var (TREE_TYPE (TREE_TYPE (vtabletmp2)),
1307                                    "vcalloffset");
1308       stmt = gimple_build_assign (vtabletmp3,
1309                                   build_simple_mem_ref (vtabletmp2));
1310       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1311       mark_symbols_for_renaming (stmt);
1312       find_referenced_vars_in (stmt);
1313
1314       /* Cast to sizetype.  */
1315       offsettmp = create_tmp_var (sizetype, "offset");
1316       stmt = gimple_build_assign (offsettmp, fold_convert (sizetype, vtabletmp3));
1317       gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1318       mark_symbols_for_renaming (stmt);
1319       find_referenced_vars_in (stmt);
1320
1321       /* Adjust the `this' pointer.  */
1322       ptr = fold_build2_loc (input_location,
1323                              POINTER_PLUS_EXPR, TREE_TYPE (ptr), ptr,
1324                              offsettmp);
1325     }
1326
1327   if (!this_adjusting
1328       && fixed_offset != 0)
1329     /* Adjust the pointer by the constant.  */
1330     {
1331       tree ptrtmp;
1332
1333       if (TREE_CODE (ptr) == VAR_DECL)
1334         ptrtmp = ptr;
1335       else
1336         {
1337           ptrtmp = create_tmp_var (TREE_TYPE (ptr), "ptr");
1338           stmt = gimple_build_assign (ptrtmp, ptr);
1339           gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1340           mark_symbols_for_renaming (stmt);
1341           find_referenced_vars_in (stmt);
1342         }
1343       ptr = fold_build2_loc (input_location,
1344                              POINTER_PLUS_EXPR, TREE_TYPE (ptrtmp), ptrtmp,
1345                              size_int (fixed_offset));
1346     }
1347
1348   /* Emit the statement and gimplify the adjustment expression.  */
1349   ret = create_tmp_var (TREE_TYPE (ptr), "adjusted_this");
1350   stmt = gimple_build_assign (ret, ptr);
1351   mark_symbols_for_renaming (stmt);
1352   find_referenced_vars_in (stmt);
1353   gsi_insert_after (bsi, stmt, GSI_NEW_STMT);
1354
1355   return ret;
1356 }
1357
1358 /* Produce assembler for thunk NODE.  */
1359
1360 static void
1361 assemble_thunk (struct cgraph_node *node)
1362 {
1363   bool this_adjusting = node->thunk.this_adjusting;
1364   HOST_WIDE_INT fixed_offset = node->thunk.fixed_offset;
1365   HOST_WIDE_INT virtual_value = node->thunk.virtual_value;
1366   tree virtual_offset = NULL;
1367   tree alias = node->thunk.alias;
1368   tree thunk_fndecl = node->decl;
1369   tree a = DECL_ARGUMENTS (thunk_fndecl);
1370
1371   current_function_decl = thunk_fndecl;
1372
1373   /* Ensure thunks are emitted in their correct sections.  */
1374   resolve_unique_section (thunk_fndecl, 0, flag_function_sections);
1375
1376   if (this_adjusting
1377       && targetm.asm_out.can_output_mi_thunk (thunk_fndecl, fixed_offset,
1378                                               virtual_value, alias))
1379     {
1380       const char *fnname;
1381       tree fn_block;
1382
1383       DECL_RESULT (thunk_fndecl)
1384         = build_decl (DECL_SOURCE_LOCATION (thunk_fndecl),
1385                       RESULT_DECL, 0, integer_type_node);
1386       fnname = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (thunk_fndecl));
1387
1388       /* The back end expects DECL_INITIAL to contain a BLOCK, so we
1389          create one.  */
1390       fn_block = make_node (BLOCK);
1391       BLOCK_VARS (fn_block) = a;
1392       DECL_INITIAL (thunk_fndecl) = fn_block;
1393       init_function_start (thunk_fndecl);
1394       cfun->is_thunk = 1;
1395       assemble_start_function (thunk_fndecl, fnname);
1396
1397       targetm.asm_out.output_mi_thunk (asm_out_file, thunk_fndecl,
1398                                        fixed_offset, virtual_value, alias);
1399
1400       assemble_end_function (thunk_fndecl, fnname);
1401       init_insn_lengths ();
1402       free_after_compilation (cfun);
1403       set_cfun (NULL);
1404       TREE_ASM_WRITTEN (thunk_fndecl) = 1;
1405     }
1406   else
1407     {
1408       tree restype;
1409       basic_block bb, then_bb, else_bb, return_bb;
1410       gimple_stmt_iterator bsi;
1411       int nargs = 0;
1412       tree arg;
1413       int i;
1414       tree resdecl;
1415       tree restmp = NULL;
1416       VEC(tree, heap) *vargs;
1417
1418       gimple call;
1419       gimple ret;
1420
1421       DECL_IGNORED_P (thunk_fndecl) = 1;
1422       bitmap_obstack_initialize (NULL);
1423
1424       if (node->thunk.virtual_offset_p)
1425         virtual_offset = size_int (virtual_value);
1426
1427       /* Build the return declaration for the function.  */
1428       restype = TREE_TYPE (TREE_TYPE (thunk_fndecl));
1429       if (DECL_RESULT (thunk_fndecl) == NULL_TREE)
1430         {
1431           resdecl = build_decl (input_location, RESULT_DECL, 0, restype);
1432           DECL_ARTIFICIAL (resdecl) = 1;
1433           DECL_IGNORED_P (resdecl) = 1;
1434           DECL_RESULT (thunk_fndecl) = resdecl;
1435         }
1436       else
1437         resdecl = DECL_RESULT (thunk_fndecl);
1438
1439       bb = then_bb = else_bb = return_bb = init_lowered_empty_function (thunk_fndecl);
1440
1441       bsi = gsi_start_bb (bb);
1442
1443       /* Build call to the function being thunked.  */
1444       if (!VOID_TYPE_P (restype))
1445         {
1446           if (!is_gimple_reg_type (restype))
1447             {
1448               restmp = resdecl;
1449               add_local_decl (cfun, restmp);
1450               BLOCK_VARS (DECL_INITIAL (current_function_decl)) = restmp;
1451             }
1452           else
1453             restmp = create_tmp_var_raw (restype, "retval");
1454         }
1455
1456       for (arg = a; arg; arg = DECL_CHAIN (arg))
1457         nargs++;
1458       vargs = VEC_alloc (tree, heap, nargs);
1459       if (this_adjusting)
1460         VEC_quick_push (tree, vargs,
1461                         thunk_adjust (&bsi,
1462                                       a, 1, fixed_offset,
1463                                       virtual_offset));
1464       else
1465         VEC_quick_push (tree, vargs, a);
1466       for (i = 1, arg = DECL_CHAIN (a); i < nargs; i++, arg = DECL_CHAIN (arg))
1467         VEC_quick_push (tree, vargs, arg);
1468       call = gimple_build_call_vec (build_fold_addr_expr_loc (0, alias), vargs);
1469       VEC_free (tree, heap, vargs);
1470       gimple_call_set_cannot_inline (call, true);
1471       gimple_call_set_from_thunk (call, true);
1472       if (restmp)
1473         gimple_call_set_lhs (call, restmp);
1474       gsi_insert_after (&bsi, call, GSI_NEW_STMT);
1475       mark_symbols_for_renaming (call);
1476       find_referenced_vars_in (call);
1477       update_stmt (call);
1478
1479       if (restmp && !this_adjusting)
1480         {
1481           tree true_label = NULL_TREE;
1482
1483           if (TREE_CODE (TREE_TYPE (restmp)) == POINTER_TYPE)
1484             {
1485               gimple stmt;
1486               /* If the return type is a pointer, we need to
1487                  protect against NULL.  We know there will be an
1488                  adjustment, because that's why we're emitting a
1489                  thunk.  */
1490               then_bb = create_basic_block (NULL, (void *) 0, bb);
1491               return_bb = create_basic_block (NULL, (void *) 0, then_bb);
1492               else_bb = create_basic_block (NULL, (void *) 0, else_bb);
1493               remove_edge (single_succ_edge (bb));
1494               true_label = gimple_block_label (then_bb);
1495               stmt = gimple_build_cond (NE_EXPR, restmp,
1496                                         build_zero_cst (TREE_TYPE (restmp)),
1497                                         NULL_TREE, NULL_TREE);
1498               gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1499               make_edge (bb, then_bb, EDGE_TRUE_VALUE);
1500               make_edge (bb, else_bb, EDGE_FALSE_VALUE);
1501               make_edge (return_bb, EXIT_BLOCK_PTR, 0);
1502               make_edge (then_bb, return_bb, EDGE_FALLTHRU);
1503               make_edge (else_bb, return_bb, EDGE_FALLTHRU);
1504               bsi = gsi_last_bb (then_bb);
1505             }
1506
1507           restmp = thunk_adjust (&bsi, restmp, /*this_adjusting=*/0,
1508                                  fixed_offset, virtual_offset);
1509           if (true_label)
1510             {
1511               gimple stmt;
1512               bsi = gsi_last_bb (else_bb);
1513               stmt = gimple_build_assign (restmp,
1514                                           build_zero_cst (TREE_TYPE (restmp)));
1515               gsi_insert_after (&bsi, stmt, GSI_NEW_STMT);
1516               bsi = gsi_last_bb (return_bb);
1517             }
1518         }
1519       else
1520         gimple_call_set_tail (call, true);
1521
1522       /* Build return value.  */
1523       ret = gimple_build_return (restmp);
1524       gsi_insert_after (&bsi, ret, GSI_NEW_STMT);
1525
1526       delete_unreachable_blocks ();
1527       update_ssa (TODO_update_ssa);
1528
1529       cgraph_remove_same_body_alias (node);
1530       /* Since we want to emit the thunk, we explicitly mark its name as
1531          referenced.  */
1532       cgraph_add_new_function (thunk_fndecl, true);
1533       bitmap_obstack_release (NULL);
1534     }
1535   current_function_decl = NULL;
1536 }
1537
1538 /* Expand function specified by NODE.  */
1539
1540 static void
1541 cgraph_expand_function (struct cgraph_node *node)
1542 {
1543   tree decl = node->decl;
1544
1545   /* We ought to not compile any inline clones.  */
1546   gcc_assert (!node->global.inlined_to);
1547
1548   announce_function (decl);
1549   node->process = 0;
1550   if (node->same_body)
1551     {
1552       struct cgraph_node *alias, *next;
1553       bool saved_alias = node->alias;
1554       for (alias = node->same_body;
1555            alias && alias->next; alias = alias->next)
1556         ;
1557       /* Walk aliases in the order they were created; it is possible that
1558          thunks refers to the aliases made earlier.  */
1559       for (; alias; alias = next)
1560         {
1561           next = alias->previous;
1562           if (!alias->thunk.thunk_p)
1563             assemble_alias (alias->decl,
1564                             DECL_ASSEMBLER_NAME (alias->thunk.alias));
1565           else
1566             assemble_thunk (alias);
1567         }
1568       node->alias = saved_alias;
1569       cgraph_process_new_functions ();
1570     }
1571
1572   gcc_assert (node->lowered);
1573
1574   /* Generate RTL for the body of DECL.  */
1575   tree_rest_of_compilation (decl);
1576
1577   /* Make sure that BE didn't give up on compiling.  */
1578   gcc_assert (TREE_ASM_WRITTEN (decl));
1579   current_function_decl = NULL;
1580   gcc_assert (!cgraph_preserve_function_body_p (decl));
1581   cgraph_release_function_body (node);
1582   /* Eliminate all call edges.  This is important so the GIMPLE_CALL no longer
1583      points to the dead function body.  */
1584   cgraph_node_remove_callees (node);
1585
1586   cgraph_function_flags_ready = true;
1587 }
1588
1589 /* Return true when CALLER_DECL should be inlined into CALLEE_DECL.  */
1590
1591 bool
1592 cgraph_inline_p (struct cgraph_edge *e, cgraph_inline_failed_t *reason)
1593 {
1594   *reason = e->inline_failed;
1595   return !e->inline_failed;
1596 }
1597
1598
1599
1600 /* Expand all functions that must be output.
1601
1602    Attempt to topologically sort the nodes so function is output when
1603    all called functions are already assembled to allow data to be
1604    propagated across the callgraph.  Use a stack to get smaller distance
1605    between a function and its callees (later we may choose to use a more
1606    sophisticated algorithm for function reordering; we will likely want
1607    to use subsections to make the output functions appear in top-down
1608    order).  */
1609
1610 static void
1611 cgraph_expand_all_functions (void)
1612 {
1613   struct cgraph_node *node;
1614   struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1615   int order_pos, new_order_pos = 0;
1616   int i;
1617
1618   order_pos = cgraph_postorder (order);
1619   gcc_assert (order_pos == cgraph_n_nodes);
1620
1621   /* Garbage collector may remove inline clones we eliminate during
1622      optimization.  So we must be sure to not reference them.  */
1623   for (i = 0; i < order_pos; i++)
1624     if (order[i]->process)
1625       order[new_order_pos++] = order[i];
1626
1627   for (i = new_order_pos - 1; i >= 0; i--)
1628     {
1629       node = order[i];
1630       if (node->process)
1631         {
1632           gcc_assert (node->reachable);
1633           node->process = 0;
1634           cgraph_expand_function (node);
1635         }
1636     }
1637   cgraph_process_new_functions ();
1638
1639   free (order);
1640
1641 }
1642
1643 /* This is used to sort the node types by the cgraph order number.  */
1644
1645 enum cgraph_order_sort_kind
1646 {
1647   ORDER_UNDEFINED = 0,
1648   ORDER_FUNCTION,
1649   ORDER_VAR,
1650   ORDER_ASM
1651 };
1652
1653 struct cgraph_order_sort
1654 {
1655   enum cgraph_order_sort_kind kind;
1656   union
1657   {
1658     struct cgraph_node *f;
1659     struct varpool_node *v;
1660     struct cgraph_asm_node *a;
1661   } u;
1662 };
1663
1664 /* Output all functions, variables, and asm statements in the order
1665    according to their order fields, which is the order in which they
1666    appeared in the file.  This implements -fno-toplevel-reorder.  In
1667    this mode we may output functions and variables which don't really
1668    need to be output.  */
1669
1670 static void
1671 cgraph_output_in_order (void)
1672 {
1673   int max;
1674   struct cgraph_order_sort *nodes;
1675   int i;
1676   struct cgraph_node *pf;
1677   struct varpool_node *pv;
1678   struct cgraph_asm_node *pa;
1679
1680   max = cgraph_order;
1681   nodes = XCNEWVEC (struct cgraph_order_sort, max);
1682
1683   varpool_analyze_pending_decls ();
1684
1685   for (pf = cgraph_nodes; pf; pf = pf->next)
1686     {
1687       if (pf->process)
1688         {
1689           i = pf->order;
1690           gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1691           nodes[i].kind = ORDER_FUNCTION;
1692           nodes[i].u.f = pf;
1693         }
1694     }
1695
1696   for (pv = varpool_nodes_queue; pv; pv = pv->next_needed)
1697     {
1698       i = pv->order;
1699       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1700       nodes[i].kind = ORDER_VAR;
1701       nodes[i].u.v = pv;
1702     }
1703
1704   for (pa = cgraph_asm_nodes; pa; pa = pa->next)
1705     {
1706       i = pa->order;
1707       gcc_assert (nodes[i].kind == ORDER_UNDEFINED);
1708       nodes[i].kind = ORDER_ASM;
1709       nodes[i].u.a = pa;
1710     }
1711
1712   /* In toplevel reorder mode we output all statics; mark them as needed.  */
1713   for (i = 0; i < max; ++i)
1714     {
1715       if (nodes[i].kind == ORDER_VAR)
1716         {
1717           varpool_mark_needed_node (nodes[i].u.v);
1718         }
1719     }
1720   varpool_empty_needed_queue ();
1721
1722   for (i = 0; i < max; ++i)
1723     if (nodes[i].kind == ORDER_VAR)
1724       varpool_finalize_named_section_flags (nodes[i].u.v);
1725
1726   for (i = 0; i < max; ++i)
1727     {
1728       switch (nodes[i].kind)
1729         {
1730         case ORDER_FUNCTION:
1731           nodes[i].u.f->process = 0;
1732           cgraph_expand_function (nodes[i].u.f);
1733           break;
1734
1735         case ORDER_VAR:
1736           varpool_assemble_decl (nodes[i].u.v);
1737           break;
1738
1739         case ORDER_ASM:
1740           assemble_asm (nodes[i].u.a->asm_str);
1741           break;
1742
1743         case ORDER_UNDEFINED:
1744           break;
1745
1746         default:
1747           gcc_unreachable ();
1748         }
1749     }
1750
1751   cgraph_asm_nodes = NULL;
1752   free (nodes);
1753 }
1754
1755 /* Return true when function body of DECL still needs to be kept around
1756    for later re-use.  */
1757 bool
1758 cgraph_preserve_function_body_p (tree decl)
1759 {
1760   struct cgraph_node *node;
1761
1762   gcc_assert (cgraph_global_info_ready);
1763   /* Look if there is any clone around.  */
1764   node = cgraph_node (decl);
1765   if (node->clones)
1766     return true;
1767   return false;
1768 }
1769
1770 static void
1771 ipa_passes (void)
1772 {
1773   set_cfun (NULL);
1774   current_function_decl = NULL;
1775   gimple_register_cfg_hooks ();
1776   bitmap_obstack_initialize (NULL);
1777
1778   invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_START, NULL);
1779
1780   if (!in_lto_p)
1781     {
1782       execute_ipa_pass_list (all_small_ipa_passes);
1783       if (seen_error ())
1784         return;
1785     }
1786
1787   /* If pass_all_early_optimizations was not scheduled, the state of
1788      the cgraph will not be properly updated.  Update it now.  */
1789   if (cgraph_state < CGRAPH_STATE_IPA_SSA)
1790     cgraph_state = CGRAPH_STATE_IPA_SSA;
1791
1792   if (!in_lto_p)
1793     {
1794       /* Generate coverage variables and constructors.  */
1795       coverage_finish ();
1796
1797       /* Process new functions added.  */
1798       set_cfun (NULL);
1799       current_function_decl = NULL;
1800       cgraph_process_new_functions ();
1801
1802       execute_ipa_summary_passes
1803         ((struct ipa_opt_pass_d *) all_regular_ipa_passes);
1804     }
1805
1806   /* Some targets need to handle LTO assembler output specially.  */
1807   if (flag_generate_lto)
1808     targetm.asm_out.lto_start ();
1809
1810   execute_ipa_summary_passes ((struct ipa_opt_pass_d *) all_lto_gen_passes);
1811
1812   if (!in_lto_p)
1813     ipa_write_summaries ();
1814
1815   if (flag_generate_lto)
1816     targetm.asm_out.lto_end ();
1817
1818   if (!flag_ltrans)
1819     execute_ipa_pass_list (all_regular_ipa_passes);
1820   invoke_plugin_callbacks (PLUGIN_ALL_IPA_PASSES_END, NULL);
1821
1822   bitmap_obstack_release (NULL);
1823 }
1824
1825
1826 /* Perform simple optimizations based on callgraph.  */
1827
1828 void
1829 cgraph_optimize (void)
1830 {
1831   if (seen_error ())
1832     return;
1833
1834 #ifdef ENABLE_CHECKING
1835   verify_cgraph ();
1836 #endif
1837
1838   /* Frontend may output common variables after the unit has been finalized.
1839      It is safe to deal with them here as they are always zero initialized.  */
1840   varpool_analyze_pending_decls ();
1841
1842   timevar_push (TV_CGRAPHOPT);
1843   if (pre_ipa_mem_report)
1844     {
1845       fprintf (stderr, "Memory consumption before IPA\n");
1846       dump_memory_report (false);
1847     }
1848   if (!quiet_flag)
1849     fprintf (stderr, "Performing interprocedural optimizations\n");
1850   cgraph_state = CGRAPH_STATE_IPA;
1851
1852   /* Don't run the IPA passes if there was any error or sorry messages.  */
1853   if (!seen_error ())
1854     ipa_passes ();
1855
1856   /* Do nothing else if any IPA pass found errors.  */
1857   if (seen_error ())
1858     {
1859       timevar_pop (TV_CGRAPHOPT);
1860       return;
1861     }
1862
1863   /* This pass remove bodies of extern inline functions we never inlined.
1864      Do this later so other IPA passes see what is really going on.  */
1865   cgraph_remove_unreachable_nodes (false, dump_file);
1866   cgraph_global_info_ready = true;
1867   if (cgraph_dump_file)
1868     {
1869       fprintf (cgraph_dump_file, "Optimized ");
1870       dump_cgraph (cgraph_dump_file);
1871       dump_varpool (cgraph_dump_file);
1872     }
1873   if (post_ipa_mem_report)
1874     {
1875       fprintf (stderr, "Memory consumption after IPA\n");
1876       dump_memory_report (false);
1877     }
1878   timevar_pop (TV_CGRAPHOPT);
1879
1880   /* Output everything.  */
1881   (*debug_hooks->assembly_start) ();
1882   if (!quiet_flag)
1883     fprintf (stderr, "Assembling functions:\n");
1884 #ifdef ENABLE_CHECKING
1885   verify_cgraph ();
1886 #endif
1887
1888   cgraph_materialize_all_clones ();
1889   cgraph_mark_functions_to_output ();
1890
1891   cgraph_state = CGRAPH_STATE_EXPANSION;
1892   if (!flag_toplevel_reorder)
1893     cgraph_output_in_order ();
1894   else
1895     {
1896       cgraph_output_pending_asms ();
1897
1898       cgraph_expand_all_functions ();
1899       varpool_remove_unreferenced_decls ();
1900
1901       varpool_assemble_pending_decls ();
1902     }
1903   cgraph_process_new_functions ();
1904   cgraph_state = CGRAPH_STATE_FINISHED;
1905
1906   if (cgraph_dump_file)
1907     {
1908       fprintf (cgraph_dump_file, "\nFinal ");
1909       dump_cgraph (cgraph_dump_file);
1910       dump_varpool (cgraph_dump_file);
1911     }
1912 #ifdef ENABLE_CHECKING
1913   verify_cgraph ();
1914   /* Double check that all inline clones are gone and that all
1915      function bodies have been released from memory.  */
1916   if (!seen_error ())
1917     {
1918       struct cgraph_node *node;
1919       bool error_found = false;
1920
1921       for (node = cgraph_nodes; node; node = node->next)
1922         if (node->analyzed
1923             && (node->global.inlined_to
1924                 || gimple_has_body_p (node->decl)))
1925           {
1926             error_found = true;
1927             dump_cgraph_node (stderr, node);
1928           }
1929       if (error_found)
1930         internal_error ("nodes with unreleased memory found");
1931     }
1932 #endif
1933 }
1934
1935 void
1936 init_cgraph (void)
1937 {
1938   if (!cgraph_dump_file)
1939     cgraph_dump_file = dump_begin (TDI_cgraph, NULL);
1940 }
1941
1942 /* The edges representing the callers of the NEW_VERSION node were
1943    fixed by cgraph_function_versioning (), now the call_expr in their
1944    respective tree code should be updated to call the NEW_VERSION.  */
1945
1946 static void
1947 update_call_expr (struct cgraph_node *new_version)
1948 {
1949   struct cgraph_edge *e;
1950
1951   gcc_assert (new_version);
1952
1953   /* Update the call expr on the edges to call the new version.  */
1954   for (e = new_version->callers; e; e = e->next_caller)
1955     {
1956       struct function *inner_function = DECL_STRUCT_FUNCTION (e->caller->decl);
1957       gimple_call_set_fndecl (e->call_stmt, new_version->decl);
1958       maybe_clean_eh_stmt_fn (inner_function, e->call_stmt);
1959     }
1960 }
1961
1962
1963 /* Create a new cgraph node which is the new version of
1964    OLD_VERSION node.  REDIRECT_CALLERS holds the callers
1965    edges which should be redirected to point to
1966    NEW_VERSION.  ALL the callees edges of OLD_VERSION
1967    are cloned to the new version node.  Return the new
1968    version node.
1969
1970    If non-NULL BLOCK_TO_COPY determine what basic blocks
1971    was copied to prevent duplications of calls that are dead
1972    in the clone.  */
1973
1974 static struct cgraph_node *
1975 cgraph_copy_node_for_versioning (struct cgraph_node *old_version,
1976                                  tree new_decl,
1977                                  VEC(cgraph_edge_p,heap) *redirect_callers,
1978                                  bitmap bbs_to_copy)
1979  {
1980    struct cgraph_node *new_version;
1981    struct cgraph_edge *e;
1982    unsigned i;
1983
1984    gcc_assert (old_version);
1985
1986    new_version = cgraph_node (new_decl);
1987
1988    new_version->analyzed = true;
1989    new_version->local = old_version->local;
1990    new_version->local.externally_visible = false;
1991    new_version->local.local = true;
1992    new_version->local.vtable_method = false;
1993    new_version->global = old_version->global;
1994    new_version->rtl = old_version->rtl;
1995    new_version->reachable = true;
1996    new_version->count = old_version->count;
1997
1998    for (e = old_version->callees; e; e=e->next_callee)
1999      if (!bbs_to_copy
2000          || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
2001        cgraph_clone_edge (e, new_version, e->call_stmt,
2002                           e->lto_stmt_uid, REG_BR_PROB_BASE,
2003                           CGRAPH_FREQ_BASE,
2004                           e->loop_nest, true);
2005    for (e = old_version->indirect_calls; e; e=e->next_callee)
2006      if (!bbs_to_copy
2007          || bitmap_bit_p (bbs_to_copy, gimple_bb (e->call_stmt)->index))
2008        cgraph_clone_edge (e, new_version, e->call_stmt,
2009                           e->lto_stmt_uid, REG_BR_PROB_BASE,
2010                           CGRAPH_FREQ_BASE,
2011                           e->loop_nest, true);
2012    FOR_EACH_VEC_ELT (cgraph_edge_p, redirect_callers, i, e)
2013      {
2014        /* Redirect calls to the old version node to point to its new
2015           version.  */
2016        cgraph_redirect_edge_callee (e, new_version);
2017      }
2018
2019    return new_version;
2020  }
2021
2022  /* Perform function versioning.
2023     Function versioning includes copying of the tree and
2024     a callgraph update (creating a new cgraph node and updating
2025     its callees and callers).
2026
2027     REDIRECT_CALLERS varray includes the edges to be redirected
2028     to the new version.
2029
2030     TREE_MAP is a mapping of tree nodes we want to replace with
2031     new ones (according to results of prior analysis).
2032     OLD_VERSION_NODE is the node that is versioned.
2033     It returns the new version's cgraph node.
2034     If non-NULL ARGS_TO_SKIP determine function parameters to remove
2035     from new version.
2036     If non-NULL BLOCK_TO_COPY determine what basic blocks to copy.
2037     If non_NULL NEW_ENTRY determine new entry BB of the clone.  */
2038
2039 struct cgraph_node *
2040 cgraph_function_versioning (struct cgraph_node *old_version_node,
2041                             VEC(cgraph_edge_p,heap) *redirect_callers,
2042                             VEC (ipa_replace_map_p,gc)* tree_map,
2043                             bitmap args_to_skip,
2044                             bitmap bbs_to_copy,
2045                             basic_block new_entry_block,
2046                             const char *clone_name)
2047 {
2048   tree old_decl = old_version_node->decl;
2049   struct cgraph_node *new_version_node = NULL;
2050   tree new_decl;
2051
2052   if (!tree_versionable_function_p (old_decl))
2053     return NULL;
2054
2055   gcc_assert (old_version_node->local.can_change_signature || !args_to_skip);
2056
2057   /* Make a new FUNCTION_DECL tree node for the
2058      new version. */
2059   if (!args_to_skip)
2060     new_decl = copy_node (old_decl);
2061   else
2062     new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2063
2064   /* Generate a new name for the new version. */
2065   DECL_NAME (new_decl) = clone_function_name (old_decl, clone_name);
2066   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
2067   SET_DECL_RTL (new_decl, NULL);
2068
2069   /* Create the new version's call-graph node.
2070      and update the edges of the new node. */
2071   new_version_node =
2072     cgraph_copy_node_for_versioning (old_version_node, new_decl,
2073                                      redirect_callers, bbs_to_copy);
2074
2075   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
2076   tree_function_versioning (old_decl, new_decl, tree_map, false, args_to_skip,
2077                             bbs_to_copy, new_entry_block);
2078
2079   /* Update the new version's properties.
2080      Make The new version visible only within this translation unit.  Make sure
2081      that is not weak also.
2082      ??? We cannot use COMDAT linkage because there is no
2083      ABI support for this.  */
2084   cgraph_make_decl_local (new_version_node->decl);
2085   DECL_VIRTUAL_P (new_version_node->decl) = 0;
2086   new_version_node->local.externally_visible = 0;
2087   new_version_node->local.local = 1;
2088   new_version_node->lowered = true;
2089
2090   /* Update the call_expr on the edges to call the new version node. */
2091   update_call_expr (new_version_node);
2092
2093   cgraph_call_function_insertion_hooks (new_version_node);
2094   return new_version_node;
2095 }
2096
2097 /* Produce separate function body for inline clones so the offline copy can be
2098    modified without affecting them.  */
2099 struct cgraph_node *
2100 save_inline_function_body (struct cgraph_node *node)
2101 {
2102   struct cgraph_node *first_clone, *n;
2103
2104   gcc_assert (node == cgraph_node (node->decl));
2105
2106   cgraph_lower_function (node);
2107
2108   first_clone = node->clones;
2109
2110   first_clone->decl = copy_node (node->decl);
2111   cgraph_insert_node_to_hashtable (first_clone);
2112   gcc_assert (first_clone == cgraph_node (first_clone->decl));
2113   if (first_clone->next_sibling_clone)
2114     {
2115       for (n = first_clone->next_sibling_clone; n->next_sibling_clone; n = n->next_sibling_clone)
2116         n->clone_of = first_clone;
2117       n->clone_of = first_clone;
2118       n->next_sibling_clone = first_clone->clones;
2119       if (first_clone->clones)
2120         first_clone->clones->prev_sibling_clone = n;
2121       first_clone->clones = first_clone->next_sibling_clone;
2122       first_clone->next_sibling_clone->prev_sibling_clone = NULL;
2123       first_clone->next_sibling_clone = NULL;
2124       gcc_assert (!first_clone->prev_sibling_clone);
2125     }
2126   first_clone->clone_of = NULL;
2127   node->clones = NULL;
2128
2129   if (first_clone->clones)
2130     for (n = first_clone->clones; n != first_clone;)
2131       {
2132         gcc_assert (n->decl == node->decl);
2133         n->decl = first_clone->decl;
2134         if (n->clones)
2135           n = n->clones;
2136         else if (n->next_sibling_clone)
2137           n = n->next_sibling_clone;
2138         else
2139           {
2140             while (n != first_clone && !n->next_sibling_clone)
2141               n = n->clone_of;
2142             if (n != first_clone)
2143               n = n->next_sibling_clone;
2144           }
2145       }
2146
2147   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
2148   tree_function_versioning (node->decl, first_clone->decl, NULL, true, NULL,
2149                             NULL, NULL);
2150
2151   DECL_EXTERNAL (first_clone->decl) = 0;
2152   DECL_COMDAT_GROUP (first_clone->decl) = NULL_TREE;
2153   TREE_PUBLIC (first_clone->decl) = 0;
2154   DECL_COMDAT (first_clone->decl) = 0;
2155   VEC_free (ipa_opt_pass, heap,
2156             first_clone->ipa_transforms_to_apply);
2157   first_clone->ipa_transforms_to_apply = NULL;
2158
2159 #ifdef ENABLE_CHECKING
2160   verify_cgraph_node (first_clone);
2161 #endif
2162   return first_clone;
2163 }
2164
2165 /* Given virtual clone, turn it into actual clone.  */
2166 static void
2167 cgraph_materialize_clone (struct cgraph_node *node)
2168 {
2169   bitmap_obstack_initialize (NULL);
2170   node->former_clone_of = node->clone_of->decl;
2171   if (node->clone_of->former_clone_of)
2172     node->former_clone_of = node->clone_of->former_clone_of;
2173   /* Copy the OLD_VERSION_NODE function tree to the new version.  */
2174   tree_function_versioning (node->clone_of->decl, node->decl,
2175                             node->clone.tree_map, true,
2176                             node->clone.args_to_skip, NULL, NULL);
2177   if (cgraph_dump_file)
2178     {
2179       dump_function_to_file (node->clone_of->decl, cgraph_dump_file, dump_flags);
2180       dump_function_to_file (node->decl, cgraph_dump_file, dump_flags);
2181     }
2182
2183   /* Function is no longer clone.  */
2184   if (node->next_sibling_clone)
2185     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
2186   if (node->prev_sibling_clone)
2187     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
2188   else
2189     node->clone_of->clones = node->next_sibling_clone;
2190   node->next_sibling_clone = NULL;
2191   node->prev_sibling_clone = NULL;
2192   if (!node->clone_of->analyzed && !node->clone_of->clones)
2193     {
2194       cgraph_release_function_body (node->clone_of);
2195       cgraph_node_remove_callees (node->clone_of);
2196       ipa_remove_all_references (&node->clone_of->ref_list);
2197     }
2198   node->clone_of = NULL;
2199   bitmap_obstack_release (NULL);
2200 }
2201
2202 /* If necessary, change the function declaration in the call statement
2203    associated with E so that it corresponds to the edge callee.  */
2204
2205 gimple
2206 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
2207 {
2208   tree decl = gimple_call_fndecl (e->call_stmt);
2209   gimple new_stmt;
2210   gimple_stmt_iterator gsi;
2211   bool gsi_computed = false;
2212 #ifdef ENABLE_CHECKING
2213   struct cgraph_node *node;
2214 #endif
2215
2216   if (e->indirect_unknown_callee
2217       || decl == e->callee->decl
2218       /* Don't update call from same body alias to the real function.  */
2219       || (decl && cgraph_get_node (decl) == cgraph_get_node (e->callee->decl)))
2220     return e->call_stmt;
2221
2222 #ifdef ENABLE_CHECKING
2223   if (decl)
2224     {
2225       node = cgraph_get_node (decl);
2226       gcc_assert (!node || !node->clone.combined_args_to_skip);
2227     }
2228 #endif
2229
2230   if (cgraph_dump_file)
2231     {
2232       fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
2233                cgraph_node_name (e->caller), e->caller->uid,
2234                cgraph_node_name (e->callee), e->callee->uid);
2235       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2236       if (e->callee->clone.combined_args_to_skip)
2237         {
2238           fprintf (cgraph_dump_file, " combined args to skip: ");
2239           dump_bitmap (cgraph_dump_file,
2240                        e->callee->clone.combined_args_to_skip);
2241         }
2242     }
2243
2244   if (e->indirect_info &&
2245       e->indirect_info->thunk_delta != 0
2246       && (!e->callee->clone.combined_args_to_skip
2247           || !bitmap_bit_p (e->callee->clone.combined_args_to_skip, 0)))
2248     {
2249       if (cgraph_dump_file)
2250         fprintf (cgraph_dump_file, "          Thunk delta is "
2251                  HOST_WIDE_INT_PRINT_DEC "\n", e->indirect_info->thunk_delta);
2252       gsi = gsi_for_stmt (e->call_stmt);
2253       gsi_computed = true;
2254       gimple_adjust_this_by_delta (&gsi,
2255                                    build_int_cst (sizetype,
2256                                                e->indirect_info->thunk_delta));
2257       e->indirect_info->thunk_delta = 0;
2258     }
2259
2260   if (e->callee->clone.combined_args_to_skip)
2261     {
2262       int lp_nr;
2263
2264       new_stmt
2265         = gimple_call_copy_skip_args (e->call_stmt,
2266                                       e->callee->clone.combined_args_to_skip);
2267       gimple_call_set_fndecl (new_stmt, e->callee->decl);
2268
2269       if (gimple_vdef (new_stmt)
2270           && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
2271         SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
2272
2273       if (!gsi_computed)
2274         gsi = gsi_for_stmt (e->call_stmt);
2275       gsi_replace (&gsi, new_stmt, false);
2276       /* We need to defer cleaning EH info on the new statement to
2277          fixup-cfg.  We may not have dominator information at this point
2278          and thus would end up with unreachable blocks and have no way
2279          to communicate that we need to run CFG cleanup then.  */
2280       lp_nr = lookup_stmt_eh_lp (e->call_stmt);
2281       if (lp_nr != 0)
2282         {
2283           remove_stmt_from_eh_lp (e->call_stmt);
2284           add_stmt_to_eh_lp (new_stmt, lp_nr);
2285         }
2286     }
2287   else
2288     {
2289       new_stmt = e->call_stmt;
2290       gimple_call_set_fndecl (new_stmt, e->callee->decl);
2291       update_stmt (new_stmt);
2292     }
2293
2294   cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
2295
2296   if (cgraph_dump_file)
2297     {
2298       fprintf (cgraph_dump_file, "  updated to:");
2299       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
2300     }
2301   return new_stmt;
2302 }
2303
2304 /* Once all functions from compilation unit are in memory, produce all clones
2305    and update all calls.  We might also do this on demand if we don't want to
2306    bring all functions to memory prior compilation, but current WHOPR
2307    implementation does that and it is is bit easier to keep everything right in
2308    this order.  */
2309 void
2310 cgraph_materialize_all_clones (void)
2311 {
2312   struct cgraph_node *node;
2313   bool stabilized = false;
2314
2315   if (cgraph_dump_file)
2316     fprintf (cgraph_dump_file, "Materializing clones\n");
2317 #ifdef ENABLE_CHECKING
2318   verify_cgraph ();
2319 #endif
2320
2321   /* We can also do topological order, but number of iterations should be
2322      bounded by number of IPA passes since single IPA pass is probably not
2323      going to create clones of clones it created itself.  */
2324   while (!stabilized)
2325     {
2326       stabilized = true;
2327       for (node = cgraph_nodes; node; node = node->next)
2328         {
2329           if (node->clone_of && node->decl != node->clone_of->decl
2330               && !gimple_has_body_p (node->decl))
2331             {
2332               if (gimple_has_body_p (node->clone_of->decl))
2333                 {
2334                   if (cgraph_dump_file)
2335                     {
2336                       fprintf (cgraph_dump_file, "cloning %s to %s\n",
2337                                cgraph_node_name (node->clone_of),
2338                                cgraph_node_name (node));
2339                       if (node->clone.tree_map)
2340                         {
2341                           unsigned int i;
2342                           fprintf (cgraph_dump_file, "   replace map: ");
2343                           for (i = 0; i < VEC_length (ipa_replace_map_p,
2344                                                       node->clone.tree_map);
2345                                                       i++)
2346                             {
2347                               struct ipa_replace_map *replace_info;
2348                               replace_info = VEC_index (ipa_replace_map_p,
2349                                                         node->clone.tree_map,
2350                                                         i);
2351                               print_generic_expr (cgraph_dump_file, replace_info->old_tree, 0);
2352                               fprintf (cgraph_dump_file, " -> ");
2353                               print_generic_expr (cgraph_dump_file, replace_info->new_tree, 0);
2354                               fprintf (cgraph_dump_file, "%s%s;",
2355                                        replace_info->replace_p ? "(replace)":"",
2356                                        replace_info->ref_p ? "(ref)":"");
2357                             }
2358                           fprintf (cgraph_dump_file, "\n");
2359                         }
2360                       if (node->clone.args_to_skip)
2361                         {
2362                           fprintf (cgraph_dump_file, "   args_to_skip: ");
2363                           dump_bitmap (cgraph_dump_file, node->clone.args_to_skip);
2364                         }
2365                       if (node->clone.args_to_skip)
2366                         {
2367                           fprintf (cgraph_dump_file, "   combined_args_to_skip:");
2368                           dump_bitmap (cgraph_dump_file, node->clone.combined_args_to_skip);
2369                         }
2370                     }
2371                   cgraph_materialize_clone (node);
2372                   stabilized = false;
2373                 }
2374             }
2375         }
2376     }
2377   for (node = cgraph_nodes; node; node = node->next)
2378     if (!node->analyzed && node->callees)
2379       cgraph_node_remove_callees (node);
2380   if (cgraph_dump_file)
2381     fprintf (cgraph_dump_file, "Materialization Call site updates done.\n");
2382 #ifdef ENABLE_CHECKING
2383   verify_cgraph ();
2384 #endif
2385   cgraph_remove_unreachable_nodes (false, cgraph_dump_file);
2386 }
2387
2388 #include "gt-cgraphunit.h"