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