gcc/cgraphunit.c

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