gcc/cgraphunit.c

   1 /* Callgraph handling code.
   2    Copyright (C) 2003 Free Software Foundation, Inc.
   3    Contributed by Jan Hubicka
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "tree.h"
  27 #include "tree-inline.h"
  28 #include "langhooks.h"
  29 #include "hashtab.h"
  30 #include "toplev.h"
  31 #include "flags.h"
  32 #include "ggc.h"
  33 #include "debug.h"
  34 #include "target.h"
  35 #include "cgraph.h"
  36 #include "diagnostic.h"
  37
  38 static void cgraph_expand_functions PARAMS ((void));
  39 static void cgraph_mark_functions_to_output PARAMS ((void));
  40 static void cgraph_expand_function PARAMS ((struct cgraph_node *));
  41 static tree record_call_1 PARAMS ((tree *, int *, void *));
  42 static void cgraph_mark_local_functions PARAMS ((void));
  43 static void cgraph_mark_functions_to_inline_once PARAMS ((void));
  44 static void cgraph_optimize_function PARAMS ((struct cgraph_node *));
  45
  46 /* Analyze function once it is parsed.  Set up the local information
  47    available - create cgraph edges for function calles via BODY.  */
  48
  49 void
  50 cgraph_finalize_function (decl, body)
  51      tree decl;
  52      tree body ATTRIBUTE_UNUSED;
  53 {
  54   struct cgraph_node *node = cgraph_node (decl);
  55
  56   node->decl = decl;
  57
  58   node->local.can_inline_once = tree_inlinable_function_p (decl, 1);
  59   if (flag_inline_trees)
  60     node->local.inline_many = tree_inlinable_function_p (decl, 0);
  61   else
  62     node->local.inline_many = 0;
  63
  64   (*debug_hooks->deferred_inline_function) (decl);
  65 }
  66
  67 static struct cgraph_node *queue = NULL;
  68
  69 /* Notify finalize_compilation_unit that given node is reachable
  70    or needed.  */
  71
  72 void
  73 cgraph_mark_needed_node (node, needed)
  74      struct cgraph_node *node;
  75      int needed;
  76 {
  77   if (needed)
  78     {
  79       if (DECL_SAVED_TREE (node->decl))
  80         announce_function (node->decl);
  81       node->needed = 1;
  82     }
  83   if (!node->reachable)
  84     {
  85       node->reachable = 1;
  86       if (DECL_SAVED_TREE (node->decl))
  87         {
  88           node->aux = queue;
  89           queue = node;
  90         }
  91     }
  92 }
  93
  94 /* Walk tree and record all calls.  Called via walk_tree.  */
  95 static tree
  96 record_call_1 (tp, walk_subtrees, data)
  97      tree *tp;
  98      int *walk_subtrees;
  99      void *data;
 100 {
 101   /* Record dereferences to the functions.  This makes the functions
 102      reachable unconditionally.  */
 103   if (TREE_CODE (*tp) == ADDR_EXPR)
 104     {
 105       tree decl = TREE_OPERAND (*tp, 0);
 106       if (TREE_CODE (decl) == FUNCTION_DECL)
 107         cgraph_mark_needed_node (cgraph_node (decl), 1);
 108     }
 109   else if (TREE_CODE (*tp) == CALL_EXPR)
 110     {
 111       /* We cannot use get_callee_fndecl here because it actually tries
 112          too hard to get the function declaration, looking for indirect
 113          references and stripping NOPS.  As a result, get_callee_fndecl
 114          finds calls that shouldn't be in the call graph.  */
 115
 116       tree decl = TREE_OPERAND (*tp, 0);
 117       if (TREE_CODE (decl) == ADDR_EXPR)
 118         decl = TREE_OPERAND (decl, 0);
 119       if (TREE_CODE (decl) == FUNCTION_DECL)
 120         {
 121           if (DECL_BUILT_IN (decl))
 122             return NULL;
 123           cgraph_record_call (data, decl);
 124
 125           /* When we see a function call, we don't want to look at the
 126              function reference in the ADDR_EXPR that is hanging from
 127              the CALL_EXPR we're examining here, because we would
 128              conclude incorrectly that the function's address could be
 129              taken by something that is not a function call.  So only
 130              walk the function parameter list, skip the other subtrees.  */
 131
 132           walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
 133           *walk_subtrees = 0;
 134         }
 135     }
 136   return NULL;
 137 }
 138
 139 /* Create cgraph edges for function calls inside BODY from DECL.  */
 140
 141 void
 142 cgraph_create_edges (decl, body)
 143      tree decl;
 144      tree body;
 145 {
 146   /* The nodes we're interested in are never shared, so walk
 147      the tree ignoring duplicates.  */
 148   walk_tree_without_duplicates (&body, record_call_1, decl);
 149 }
 150
 151 /* Analyze the whole compilation unit once it is parsed completely.  */
 152
 153 void
 154 cgraph_finalize_compilation_unit ()
 155 {
 156   struct cgraph_node *node;
 157   struct cgraph_edge *edge;
 158
 159   /* Collect entry points to the unit.  */
 160
 161   if (!quiet_flag)
 162     fprintf (stderr, "\n\nUnit entry points:");
 163
 164   for (node = cgraph_nodes; node; node = node->next)
 165     {
 166       tree decl = node->decl;
 167
 168       if (!DECL_SAVED_TREE (decl))
 169         continue;
 170       if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
 171           || (DECL_ASSEMBLER_NAME_SET_P (decl)
 172               && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
 173         {
 174           /* This function can be called from outside this compliation
 175              unit, so it most definitely is needed.  */
 176           cgraph_mark_needed_node (node, 1);
 177         }
 178     }
 179
 180   /* Propagate reachability flag and lower representation of all reachable
 181      functions.  In the future, lowering will introduce new functions and
 182      new entry points on the way (by template instantiation and virtual
 183      method table generation for instance).  */
 184   while (queue)
 185     {
 186       tree decl = queue->decl;
 187
 188       node = queue;
 189       queue = queue->aux;
 190       if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
 191         abort ();
 192
 193       /* At the moment frontend automatically emits all nested functions.  */
 194       if (node->nested)
 195         {
 196           struct cgraph_node *node2;
 197
 198           for (node2 = node->nested; node2; node2 = node2->next_nested)
 199             if (!node2->reachable)
 200               cgraph_mark_needed_node (node2, 0);
 201         }
 202
 203       if (lang_hooks.callgraph.lower_function)
 204         (*lang_hooks.callgraph.lower_function) (decl);
 205
 206       /* First kill forward declaration so reverse inling works properly.  */
 207       cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
 208
 209       for (edge = node->callees; edge; edge = edge->next_callee)
 210         {
 211           if (!edge->callee->reachable)
 212             cgraph_mark_needed_node (edge->callee, 0);
 213         }
 214       node->lowered = true;
 215     }
 216
 217   if (!quiet_flag)
 218     fprintf (stderr, "\n\nReclaiming functions:");
 219
 220   for (node = cgraph_nodes; node; node = node->next)
 221     {
 222       tree decl = node->decl;
 223
 224       if (!node->reachable && DECL_SAVED_TREE (decl))
 225         {
 226           cgraph_remove_node (node);
 227           announce_function (decl);
 228         }
 229     }
 230   ggc_collect ();
 231 }
 232
 233 /* Figure out what functions we want to assemble.  */
 234
 235 static void
 236 cgraph_mark_functions_to_output ()
 237 {
 238   struct cgraph_node *node;
 239
 240   for (node = cgraph_nodes; node; node = node->next)
 241     {
 242       tree decl = node->decl;
 243
 244       /* We need to output all local functions that are used and not
 245          always inlined, as well as those that are reachable from
 246          outside the current compilation unit.  */
 247       if (DECL_SAVED_TREE (decl)
 248           && (node->needed
 249               || (!node->local.inline_many && !node->global.inline_once
 250                   && node->reachable)
 251               || TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
 252           && !TREE_ASM_WRITTEN (decl) && !node->origin
 253           && !DECL_EXTERNAL (decl))
 254         node->output = 1;
 255     }
 256 }
 257
 258 /* Optimize the function before expansion.  */
 259
 260 static void
 261 cgraph_optimize_function (node)
 262      struct cgraph_node *node;
 263 {
 264   tree decl = node->decl;
 265
 266   if (flag_inline_trees)
 267     optimize_inline_calls (decl);
 268   if (node->nested)
 269     {
 270       for (node = node->nested; node; node = node->next_nested)
 271         cgraph_optimize_function (node);
 272     }
 273 }
 274
 275 /* Expand function specified by NODE.  */
 276
 277 static void
 278 cgraph_expand_function (node)
 279      struct cgraph_node *node;
 280 {
 281   tree decl = node->decl;
 282
 283   announce_function (decl);
 284
 285   cgraph_optimize_function (node);
 286
 287   /* Generate RTL for the body of DECL.  Nested functions are expanded
 288      via lang_expand_decl_stmt.  */
 289   (*lang_hooks.callgraph.expand_function) (decl);
 290
 291   /* When we decided to inline the function once, we never ever should
 292      need to output it separately.  */
 293   if (node->global.inline_once)
 294     abort ();
 295   if (!node->local.inline_many
 296       || !node->callers)
 297     DECL_SAVED_TREE (decl) = NULL;
 298   current_function_decl = NULL;
 299 }
 300
 301
 302 /* Expand all functions that must be output.
 303
 304    Attempt to topologically sort the nodes so function is output when
 305    all called functions are already assembled to allow data to be
 306    propagated accross the callgraph.  Use a stack to get smaller distance
 307    between a function and it's callees (later we may choose to use a more
 308    sophisticated algorithm for function reordering; we will likely want
 309    to use subsections to make the output functions appear in top-down
 310    order.  */
 311
 312 static void
 313 cgraph_expand_functions ()
 314 {
 315   struct cgraph_node *node, *node2;
 316   struct cgraph_node **stack =
 317     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 318   struct cgraph_node **order =
 319     xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
 320   int stack_size = 0;
 321   int order_pos = 0;
 322   struct cgraph_edge *edge, last;
 323   int i;
 324
 325   cgraph_mark_functions_to_output ();
 326
 327   /* We have to deal with cycles nicely, so use a depth first traversal
 328      output algorithm.  Ignore the fact that some functions won't need
 329      to be output and put them into order as well, so we get dependencies
 330      right through intline functions.  */
 331   for (node = cgraph_nodes; node; node = node->next)
 332     node->aux = NULL;
 333   for (node = cgraph_nodes; node; node = node->next)
 334     if (node->output && !node->aux)
 335       {
 336         node2 = node;
 337         if (!node->callers)
 338           node->aux = &last;
 339         else
 340           node->aux = node->callers;
 341         while (node2)
 342           {
 343             while (node2->aux != &last)
 344               {
 345                 edge = node2->aux;
 346                 if (edge->next_caller)
 347                   node2->aux = edge->next_caller;
 348                 else
 349                   node2->aux = &last;
 350                 if (!edge->caller->aux)
 351                   {
 352                     if (!edge->caller->callers)
 353                       edge->caller->aux = &last;
 354                     else
 355                       edge->caller->aux = edge->caller->callers;
 356                     stack[stack_size++] = node2;
 357                     node2 = edge->caller;
 358                     break;
 359                   }
 360               }
 361             if (node2->aux == &last)
 362               {
 363                 order[order_pos++] = node2;
 364                 if (stack_size)
 365                   node2 = stack[--stack_size];
 366                 else
 367                   node2 = NULL;
 368               }
 369           }
 370       }
 371   for (i = order_pos - 1; i >= 0; i--)
 372     {
 373       node = order[i];
 374       if (node->output)
 375         {
 376           if (!node->reachable)
 377             abort ();
 378           node->output = 0;
 379           cgraph_expand_function (node);
 380         }
 381     }
 382   free (stack);
 383   free (order);
 384 }
 385
 386 /* Mark all local functions.
 387    We can not use node->needed directly as it is modified during
 388    execution of cgraph_optimize.  */
 389
 390 static void
 391 cgraph_mark_local_functions ()
 392 {
 393   struct cgraph_node *node;
 394
 395   if (!quiet_flag)
 396     fprintf (stderr, "\n\nMarking local functions:");
 397
 398   /* Figure out functions we want to assemble.  */
 399   for (node = cgraph_nodes; node; node = node->next)
 400     {
 401       node->local.local = (!node->needed
 402                            && DECL_SAVED_TREE (node->decl)
 403                            && !TREE_PUBLIC (node->decl));
 404       if (node->local.local)
 405         announce_function (node->decl);
 406     }
 407 }
 408
 409 /* Decide what function should be inlined because they are invoked once
 410    (so inlining won't result in duplication of the code).  */
 411
 412 static void
 413 cgraph_mark_functions_to_inline_once ()
 414 {
 415   struct cgraph_node *node, *node1;
 416
 417   if (!quiet_flag)
 418     fprintf (stderr, "\n\nMarking functions to inline once:");
 419
 420   /* Now look for function called only once and mark them to inline.
 421      From this point number of calls to given function won't grow.  */
 422   for (node = cgraph_nodes; node; node = node->next)
 423     {
 424       if (node->callers && !node->callers->next_caller && !node->needed
 425           && node->local.can_inline_once)
 426         {
 427           bool ok = true;
 428
 429           /* Verify that we won't duplicate the caller.  */
 430           for (node1 = node->callers->caller;
 431                node1->local.inline_many
 432                && node1->callers
 433                && ok;
 434                node1 = node1->callers->caller)
 435             if (node1->callers->next_caller || node1->needed)
 436               ok = false;
 437           if (ok)
 438             {
 439               node->global.inline_once = true;
 440               announce_function (node->decl);
 441             }
 442         }
 443     }
 444 }
 445
 446
 447 /* Perform simple optimizations based on callgraph.  */
 448
 449 void
 450 cgraph_optimize ()
 451 {
 452   struct cgraph_node *node;
 453   bool changed = true;
 454
 455   cgraph_mark_local_functions ();
 456
 457   cgraph_mark_functions_to_inline_once ();
 458
 459   cgraph_global_info_ready = true;
 460   if (!quiet_flag)
 461     fprintf (stderr, "\n\nAssembling functions:");
 462
 463   /* Output everything.
 464      ??? Our inline heuristic may decide to not inline functions previously
 465      marked as inlinable thus adding new function bodies that must be output.
 466      Later we should move all inlining decisions to callgraph code to make
 467      this impossible.  */
 468   cgraph_expand_functions ();
 469   if (!quiet_flag)
 470     fprintf (stderr, "\n\nAssembling functions that failed to inline:");
 471   while (changed && !errorcount && !sorrycount)
 472     {
 473       changed = false;
 474       for (node = cgraph_nodes; node; node = node->next)
 475         {
 476           tree decl = node->decl;
 477           if (!node->origin
 478               && !TREE_ASM_WRITTEN (decl)
 479               && DECL_SAVED_TREE (decl)
 480               && !DECL_EXTERNAL (decl))
 481             {
 482               struct cgraph_edge *edge;
 483
 484               for (edge = node->callers; edge; edge = edge->next_caller)
 485                 if (TREE_ASM_WRITTEN (edge->caller->decl))
 486                   {
 487                     changed = true;
 488                     cgraph_expand_function (node);
 489                     break;
 490                   }
 491             }
 492         }
 493     }
 494 }