gcc/ipa.c

   1 /* Basic IPA optimizations and utilities.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation,
   3    Inc.
   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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "cgraph.h"
  26 #include "tree-pass.h"
  27 #include "timevar.h"
  28 #include "gimple.h"
  29 #include "ggc.h"
  30
  31 /* Fill array order with all nodes with output flag set in the reverse
  32    topological order.  */
  33
  34 int
  35 cgraph_postorder (struct cgraph_node **order)
  36 {
  37   struct cgraph_node *node, *node2;
  38   int stack_size = 0;
  39   int order_pos = 0;
  40   struct cgraph_edge *edge, last;
  41
  42   struct cgraph_node **stack =
  43     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
  44
  45   /* We have to deal with cycles nicely, so use a depth first traversal
  46      output algorithm.  Ignore the fact that some functions won't need
  47      to be output and put them into order as well, so we get dependencies
  48      right through inline functions.  */
  49   for (node = cgraph_nodes; node; node = node->next)
  50     node->aux = NULL;
  51   for (node = cgraph_nodes; node; node = node->next)
  52     if (!node->aux)
  53       {
  54         node2 = node;
  55         if (!node->callers)
  56           node->aux = &last;
  57         else
  58           node->aux = node->callers;
  59         while (node2)
  60           {
  61             while (node2->aux != &last)
  62               {
  63                 edge = (struct cgraph_edge *) node2->aux;
  64                 if (edge->next_caller)
  65                   node2->aux = edge->next_caller;
  66                 else
  67                   node2->aux = &last;
  68                 if (!edge->caller->aux)
  69                   {
  70                     if (!edge->caller->callers)
  71                       edge->caller->aux = &last;
  72                     else
  73                       edge->caller->aux = edge->caller->callers;
  74                     stack[stack_size++] = node2;
  75                     node2 = edge->caller;
  76                     break;
  77                   }
  78               }
  79             if (node2->aux == &last)
  80               {
  81                 order[order_pos++] = node2;
  82                 if (stack_size)
  83                   node2 = stack[--stack_size];
  84                 else
  85                   node2 = NULL;
  86               }
  87           }
  88       }
  89   free (stack);
  90   for (node = cgraph_nodes; node; node = node->next)
  91     node->aux = NULL;
  92   return order_pos;
  93 }
  94
  95 /* Look for all functions inlined to NODE and update their inlined_to pointers
  96    to INLINED_TO.  */
  97
  98 static void
  99 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
 100 {
 101   struct cgraph_edge *e;
 102   for (e = node->callees; e; e = e->next_callee)
 103     if (e->callee->global.inlined_to)
 104       {
 105         e->callee->global.inlined_to = inlined_to;
 106         update_inlined_to_pointer (e->callee, inlined_to);
 107       }
 108 }
 109
 110 /* Perform reachability analysis and reclaim all unreachable nodes.
 111    If BEFORE_INLINING_P is true this function is called before inlining
 112    decisions has been made.  If BEFORE_INLINING_P is false this function also
 113    removes unneeded bodies of extern inline functions.  */
 114
 115 bool
 116 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 117 {
 118   struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
 119   struct cgraph_node *node, *next;
 120   bool changed = false;
 121
 122 #ifdef ENABLE_CHECKING
 123   verify_cgraph ();
 124 #endif
 125   if (file)
 126     fprintf (file, "\nReclaiming functions:");
 127 #ifdef ENABLE_CHECKING
 128   for (node = cgraph_nodes; node; node = node->next)
 129     gcc_assert (!node->aux);
 130 #endif
 131   for (node = cgraph_nodes; node; node = node->next)
 132     if (node->needed && !node->global.inlined_to
 133         && ((!DECL_EXTERNAL (node->decl))
 134             || !node->analyzed
 135             || before_inlining_p))
 136       {
 137         node->aux = first;
 138         first = node;
 139       }
 140     else
 141       gcc_assert (!node->aux);
 142
 143   /* Perform reachability analysis.  As a special case do not consider
 144      extern inline functions not inlined as live because we won't output
 145      them at all.  */
 146   while (first != (void *) 1)
 147     {
 148       struct cgraph_edge *e;
 149       node = first;
 150       first = (struct cgraph_node *) first->aux;
 151
 152       for (e = node->callees; e; e = e->next_callee)
 153         if (!e->callee->aux
 154             && node->analyzed
 155             && (!e->inline_failed || !e->callee->analyzed
 156                 || (!DECL_EXTERNAL (e->callee->decl))
 157                 || before_inlining_p))
 158           {
 159             e->callee->aux = first;
 160             first = e->callee;
 161           }
 162       while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
 163         {
 164           node = node->clone_of;
 165           node->aux = first;
 166           first = node;
 167         }
 168     }
 169
 170   /* Remove unreachable nodes.  Extern inline functions need special care;
 171      Unreachable extern inline functions shall be removed.
 172      Reachable extern inline functions we never inlined shall get their bodies
 173      eliminated.
 174      Reachable extern inline functions we sometimes inlined will be turned into
 175      unanalyzed nodes so they look like for true extern functions to the rest
 176      of code.  Body of such functions is released via remove_node once the
 177      inline clones are eliminated.  */
 178   for (node = cgraph_nodes; node; node = next)
 179     {
 180       next = node->next;
 181       if (!node->aux)
 182         {
 183           node->global.inlined_to = NULL;
 184           if (file)
 185             fprintf (file, " %s", cgraph_node_name (node));
 186           if (!node->analyzed || !DECL_EXTERNAL (node->decl)
 187               || before_inlining_p)
 188             cgraph_remove_node (node);
 189           else
 190             {
 191               struct cgraph_edge *e;
 192
 193               /* See if there is reachable caller.  */
 194               for (e = node->callers; e; e = e->next_caller)
 195                 if (e->caller->aux)
 196                   break;
 197
 198               /* If so, we need to keep node in the callgraph.  */
 199               if (e || node->needed)
 200                 {
 201                   struct cgraph_node *clone;
 202
 203                   /* If there are still clones, we must keep body around.
 204                      Otherwise we can just remove the body but keep the clone.  */
 205                   for (clone = node->clones; clone;
 206                        clone = clone->next_sibling_clone)
 207                     if (clone->aux)
 208                       break;
 209                   if (!clone)
 210                     {
 211                       cgraph_release_function_body (node);
 212                       cgraph_node_remove_callees (node);
 213                       node->analyzed = false;
 214                       node->local.inlinable = false;
 215                     }
 216                 }
 217               else
 218                 cgraph_remove_node (node);
 219             }
 220           changed = true;
 221         }
 222     }
 223   for (node = cgraph_nodes; node; node = node->next)
 224     {
 225       /* Inline clones might be kept around so their materializing allows further
 226          cloning.  If the function the clone is inlined into is removed, we need
 227          to turn it into normal cone.  */
 228       if (node->global.inlined_to
 229           && !node->callers)
 230         {
 231           gcc_assert (node->clones);
 232           node->global.inlined_to = NULL;
 233           update_inlined_to_pointer (node, node);
 234         }
 235       node->aux = NULL;
 236     }
 237 #ifdef ENABLE_CHECKING
 238   verify_cgraph ();
 239 #endif
 240   return changed;
 241 }
 242
 243 /* Mark visibility of all functions.
 244
 245    A local function is one whose calls can occur only in the current
 246    compilation unit and all its calls are explicit, so we can change
 247    its calling convention.  We simply mark all static functions whose
 248    address is not taken as local.
 249
 250    We also change the TREE_PUBLIC flag of all declarations that are public
 251    in language point of view but we want to overwrite this default
 252    via visibilities for the backend point of view.  */
 253
 254 static unsigned int
 255 function_and_variable_visibility (void)
 256 {
 257   struct cgraph_node *node;
 258   struct varpool_node *vnode;
 259
 260   for (node = cgraph_nodes; node; node = node->next)
 261     {
 262       if (node->reachable
 263           && (DECL_COMDAT (node->decl)
 264               || (!flag_whole_program
 265                   && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
 266         node->local.externally_visible = true;
 267       if (!node->local.externally_visible && node->analyzed
 268           && !DECL_EXTERNAL (node->decl))
 269         {
 270           gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
 271           TREE_PUBLIC (node->decl) = 0;
 272         }
 273       node->local.local = (!node->needed
 274                            && node->analyzed
 275                            && !DECL_EXTERNAL (node->decl)
 276                            && !node->local.externally_visible);
 277     }
 278   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 279     {
 280       if (vnode->needed
 281           && !flag_whole_program
 282           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
 283         vnode->externally_visible = 1;
 284       if (!vnode->externally_visible)
 285         {
 286           gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl));
 287           TREE_PUBLIC (vnode->decl) = 0;
 288         }
 289      gcc_assert (TREE_STATIC (vnode->decl));
 290     }
 291
 292   if (dump_file)
 293     {
 294       fprintf (dump_file, "\nMarking local functions:");
 295       for (node = cgraph_nodes; node; node = node->next)
 296         if (node->local.local)
 297           fprintf (dump_file, " %s", cgraph_node_name (node));
 298       fprintf (dump_file, "\n\n");
 299       fprintf (dump_file, "\nMarking externally visible functions:");
 300       for (node = cgraph_nodes; node; node = node->next)
 301         if (node->local.externally_visible)
 302           fprintf (dump_file, " %s", cgraph_node_name (node));
 303       fprintf (dump_file, "\n\n");
 304     }
 305   cgraph_function_flags_ready = true;
 306   return 0;
 307 }
 308
 309 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
 310 {
 311  {
 312   SIMPLE_IPA_PASS,
 313   "visibility",                         /* name */
 314   NULL,                                 /* gate */
 315   function_and_variable_visibility,     /* execute */
 316   NULL,                                 /* sub */
 317   NULL,                                 /* next */
 318   0,                                    /* static_pass_number */
 319   TV_CGRAPHOPT,                         /* tv_id */
 320   0,                                    /* properties_required */
 321   0,                                    /* properties_provided */
 322   0,                                    /* properties_destroyed */
 323   0,                                    /* todo_flags_start */
 324   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
 325  }
 326 };
 327
 328
 329 /* Hash a cgraph node set element.  */
 330
 331 static hashval_t
 332 hash_cgraph_node_set_element (const void *p)
 333 {
 334   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
 335   return htab_hash_pointer (element->node);
 336 }
 337
 338 /* Compare two cgraph node set elements.  */
 339
 340 static int
 341 eq_cgraph_node_set_element (const void *p1, const void *p2)
 342 {
 343   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
 344   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
 345
 346   return e1->node == e2->node;
 347 }
 348
 349 /* Create a new cgraph node set.  */
 350
 351 cgraph_node_set
 352 cgraph_node_set_new (void)
 353 {
 354   cgraph_node_set new_node_set;
 355
 356   new_node_set = GGC_NEW (struct cgraph_node_set_def);
 357   new_node_set->hashtab = htab_create_ggc (10,
 358                                            hash_cgraph_node_set_element,
 359                                            eq_cgraph_node_set_element,
 360                                            NULL);
 361   new_node_set->nodes = NULL;
 362   return new_node_set;
 363 }
 364
 365 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 366
 367 void
 368 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 369 {
 370   void **slot;
 371   cgraph_node_set_element element;
 372   struct cgraph_node_set_element_def dummy;
 373
 374   dummy.node = node;
 375   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
 376
 377   if (*slot != HTAB_EMPTY_ENTRY)
 378     {
 379       element = (cgraph_node_set_element) *slot;
 380       gcc_assert (node == element->node
 381                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 382                       == node));
 383       return;
 384     }
 385
 386   /* Insert node into hash table.  */
 387   element =
 388     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
 389   element->node = node;
 390   element->index = VEC_length (cgraph_node_ptr, set->nodes);
 391   *slot = element;
 392
 393   /* Insert into node vector.  */
 394   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
 395 }
 396
 397 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 398
 399 void
 400 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 401 {
 402   void **slot, **last_slot;
 403   cgraph_node_set_element element, last_element;
 404   struct cgraph_node *last_node;
 405   struct cgraph_node_set_element_def dummy;
 406
 407   dummy.node = node;
 408   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 409   if (slot == NULL)
 410     return;
 411
 412   element = (cgraph_node_set_element) *slot;
 413   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 414               == node);
 415
 416   /* Remove from vector. We do this by swapping node with the last element
 417      of the vector.  */
 418   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 419   if (last_node != node)
 420     {
 421       dummy.node = last_node;
 422       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 423       last_element = (cgraph_node_set_element) *last_slot;
 424       gcc_assert (last_element);
 425
 426       /* Move the last element to the original spot of NODE.  */
 427       last_element->index = element->index;
 428       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
 429                    last_node);
 430     }
 431
 432   /* Remove element from hash table.  */
 433   htab_clear_slot (set->hashtab, slot);
 434   ggc_free (element);
 435 }
 436
 437 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 438    is returned if NODE is not in SET.  */
 439
 440 cgraph_node_set_iterator
 441 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 442 {
 443   void **slot;
 444   struct cgraph_node_set_element_def dummy;
 445   cgraph_node_set_element element;
 446   cgraph_node_set_iterator csi;
 447
 448   dummy.node = node;
 449   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 450   if (slot == NULL)
 451     csi.index = (unsigned) ~0;
 452   else
 453     {
 454       element = (cgraph_node_set_element) *slot;
 455       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 456                   == node);
 457       csi.index = element->index;
 458     }
 459   csi.set = set;
 460
 461   return csi;
 462 }
 463
 464 /* Dump content of SET to file F.  */
 465
 466 void
 467 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 468 {
 469   cgraph_node_set_iterator iter;
 470
 471   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 472     {
 473       struct cgraph_node *node = csi_node (iter);
 474       dump_cgraph_node (f, node);
 475     }
 476 }
 477
 478 /* Dump content of SET to stderr.  */
 479
 480 void
 481 debug_cgraph_node_set (cgraph_node_set set)
 482 {
 483   dump_cgraph_node_set (stderr, set);
 484 }
 485