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