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