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