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   return changed;
 244 }
 245
 246 /* Mark visibility of all functions.
 247
 248    A local function is one whose calls can occur only in the current
 249    compilation unit and all its calls are explicit, so we can change
 250    its calling convention.  We simply mark all static functions whose
 251    address is not taken as local.
 252
 253    We also change the TREE_PUBLIC flag of all declarations that are public
 254    in language point of view but we want to overwrite this default
 255    via visibilities for the backend point of view.  */
 256
 257 static unsigned int
 258 function_and_variable_visibility (void)
 259 {
 260   struct cgraph_node *node;
 261   struct varpool_node *vnode;
 262
 263   for (node = cgraph_nodes; node; node = node->next)
 264     {
 265       if (node->reachable
 266           && (DECL_COMDAT (node->decl)
 267               || (!flag_whole_program
 268                   && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
 269         node->local.externally_visible = true;
 270       if (!node->local.externally_visible && node->analyzed
 271           && !DECL_EXTERNAL (node->decl))
 272         {
 273           gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
 274           TREE_PUBLIC (node->decl) = 0;
 275         }
 276       node->local.local = (!node->needed
 277                            && node->analyzed
 278                            && !DECL_EXTERNAL (node->decl)
 279                            && !node->local.externally_visible);
 280     }
 281   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 282     {
 283       if (vnode->needed
 284           && !flag_whole_program
 285           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
 286         vnode->externally_visible = 1;
 287       if (!vnode->externally_visible)
 288         {
 289           gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl));
 290           TREE_PUBLIC (vnode->decl) = 0;
 291         }
 292      gcc_assert (TREE_STATIC (vnode->decl));
 293     }
 294
 295   if (dump_file)
 296     {
 297       fprintf (dump_file, "\nMarking local functions:");
 298       for (node = cgraph_nodes; node; node = node->next)
 299         if (node->local.local)
 300           fprintf (dump_file, " %s", cgraph_node_name (node));
 301       fprintf (dump_file, "\n\n");
 302       fprintf (dump_file, "\nMarking externally visible functions:");
 303       for (node = cgraph_nodes; node; node = node->next)
 304         if (node->local.externally_visible)
 305           fprintf (dump_file, " %s", cgraph_node_name (node));
 306       fprintf (dump_file, "\n\n");
 307     }
 308   cgraph_function_flags_ready = true;
 309   return 0;
 310 }
 311
 312 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
 313 {
 314  {
 315   SIMPLE_IPA_PASS,
 316   "visibility",                         /* name */
 317   NULL,                                 /* gate */
 318   function_and_variable_visibility,     /* execute */
 319   NULL,                                 /* sub */
 320   NULL,                                 /* next */
 321   0,                                    /* static_pass_number */
 322   TV_CGRAPHOPT,                         /* tv_id */
 323   0,                                    /* properties_required */
 324   0,                                    /* properties_provided */
 325   0,                                    /* properties_destroyed */
 326   0,                                    /* todo_flags_start */
 327   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
 328  }
 329 };
 330
 331
 332 /* Hash a cgraph node set element.  */
 333
 334 static hashval_t
 335 hash_cgraph_node_set_element (const void *p)
 336 {
 337   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
 338   return htab_hash_pointer (element->node);
 339 }
 340
 341 /* Compare two cgraph node set elements.  */
 342
 343 static int
 344 eq_cgraph_node_set_element (const void *p1, const void *p2)
 345 {
 346   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
 347   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
 348
 349   return e1->node == e2->node;
 350 }
 351
 352 /* Create a new cgraph node set.  */
 353
 354 cgraph_node_set
 355 cgraph_node_set_new (void)
 356 {
 357   cgraph_node_set new_node_set;
 358
 359   new_node_set = GGC_NEW (struct cgraph_node_set_def);
 360   new_node_set->hashtab = htab_create_ggc (10,
 361                                            hash_cgraph_node_set_element,
 362                                            eq_cgraph_node_set_element,
 363                                            NULL);
 364   new_node_set->nodes = NULL;
 365   return new_node_set;
 366 }
 367
 368 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 369
 370 void
 371 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 372 {
 373   void **slot;
 374   cgraph_node_set_element element;
 375   struct cgraph_node_set_element_def dummy;
 376
 377   dummy.node = node;
 378   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
 379
 380   if (*slot != HTAB_EMPTY_ENTRY)
 381     {
 382       element = (cgraph_node_set_element) *slot;
 383       gcc_assert (node == element->node
 384                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 385                       == node));
 386       return;
 387     }
 388
 389   /* Insert node into hash table.  */
 390   element =
 391     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
 392   element->node = node;
 393   element->index = VEC_length (cgraph_node_ptr, set->nodes);
 394   *slot = element;
 395
 396   /* Insert into node vector.  */
 397   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
 398 }
 399
 400 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 401
 402 void
 403 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 404 {
 405   void **slot, **last_slot;
 406   cgraph_node_set_element element, last_element;
 407   struct cgraph_node *last_node;
 408   struct cgraph_node_set_element_def dummy;
 409
 410   dummy.node = node;
 411   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 412   if (slot == NULL)
 413     return;
 414
 415   element = (cgraph_node_set_element) *slot;
 416   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 417               == node);
 418
 419   /* Remove from vector. We do this by swapping node with the last element
 420      of the vector.  */
 421   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 422   if (last_node != node)
 423     {
 424       dummy.node = last_node;
 425       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 426       last_element = (cgraph_node_set_element) *last_slot;
 427       gcc_assert (last_element);
 428
 429       /* Move the last element to the original spot of NODE.  */
 430       last_element->index = element->index;
 431       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
 432                    last_node);
 433     }
 434
 435   /* Remove element from hash table.  */
 436   htab_clear_slot (set->hashtab, slot);
 437   ggc_free (element);
 438 }
 439
 440 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 441    is returned if NODE is not in SET.  */
 442
 443 cgraph_node_set_iterator
 444 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 445 {
 446   void **slot;
 447   struct cgraph_node_set_element_def dummy;
 448   cgraph_node_set_element element;
 449   cgraph_node_set_iterator csi;
 450
 451   dummy.node = node;
 452   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 453   if (slot == NULL)
 454     csi.index = (unsigned) ~0;
 455   else
 456     {
 457       element = (cgraph_node_set_element) *slot;
 458       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 459                   == node);
 460       csi.index = element->index;
 461     }
 462   csi.set = set;
 463
 464   return csi;
 465 }
 466
 467 /* Dump content of SET to file F.  */
 468
 469 void
 470 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 471 {
 472   cgraph_node_set_iterator iter;
 473
 474   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 475     {
 476       struct cgraph_node *node = csi_node (iter);
 477       dump_cgraph_node (f, node);
 478     }
 479 }
 480
 481 /* Dump content of SET to stderr.  */
 482
 483 void
 484 debug_cgraph_node_set (cgraph_node_set set)
 485 {
 486   dump_cgraph_node_set (stderr, set);
 487 }
 488