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
  29 /* Fill array order with all nodes with output flag set in the reverse
  30    topological order.  */
  31
  32 int
  33 cgraph_postorder (struct cgraph_node **order)
  34 {
  35   struct cgraph_node *node, *node2;
  36   int stack_size = 0;
  37   int order_pos = 0;
  38   struct cgraph_edge *edge, last;
  39
  40   struct cgraph_node **stack =
  41     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
  42
  43   /* We have to deal with cycles nicely, so use a depth first traversal
  44      output algorithm.  Ignore the fact that some functions won't need
  45      to be output and put them into order as well, so we get dependencies
  46      right through inline functions.  */
  47   for (node = cgraph_nodes; node; node = node->next)
  48     node->aux = NULL;
  49   for (node = cgraph_nodes; node; node = node->next)
  50     if (!node->aux)
  51       {
  52         node2 = node;
  53         if (!node->callers)
  54           node->aux = &last;
  55         else
  56           node->aux = node->callers;
  57         while (node2)
  58           {
  59             while (node2->aux != &last)
  60               {
  61                 edge = (struct cgraph_edge *) node2->aux;
  62                 if (edge->next_caller)
  63                   node2->aux = edge->next_caller;
  64                 else
  65                   node2->aux = &last;
  66                 if (!edge->caller->aux)
  67                   {
  68                     if (!edge->caller->callers)
  69                       edge->caller->aux = &last;
  70                     else
  71                       edge->caller->aux = edge->caller->callers;
  72                     stack[stack_size++] = node2;
  73                     node2 = edge->caller;
  74                     break;
  75                   }
  76               }
  77             if (node2->aux == &last)
  78               {
  79                 order[order_pos++] = node2;
  80                 if (stack_size)
  81                   node2 = stack[--stack_size];
  82                 else
  83                   node2 = NULL;
  84               }
  85           }
  86       }
  87   free (stack);
  88   for (node = cgraph_nodes; node; node = node->next)
  89     node->aux = NULL;
  90   return order_pos;
  91 }
  92
  93 /* Perform reachability analysis and reclaim all unreachable nodes.
  94    If BEFORE_INLINING_P is true this function is called before inlining
  95    decisions has been made.  If BEFORE_INLINING_P is false this function also
  96    removes unneeded bodies of extern inline functions.  */
  97
  98 bool
  99 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 100 {
 101   struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
 102   struct cgraph_node *node, *next;
 103   bool changed = false;
 104
 105 #ifdef ENABLE_CHECKING
 106   verify_cgraph ();
 107 #endif
 108   if (file)
 109     fprintf (file, "\nReclaiming functions:");
 110 #ifdef ENABLE_CHECKING
 111   for (node = cgraph_nodes; node; node = node->next)
 112     gcc_assert (!node->aux);
 113 #endif
 114   for (node = cgraph_nodes; node; node = node->next)
 115     if (node->needed && !node->global.inlined_to
 116         && ((!DECL_EXTERNAL (node->decl))
 117             || !node->analyzed
 118             || before_inlining_p))
 119       {
 120         node->aux = first;
 121         first = node;
 122       }
 123     else
 124       gcc_assert (!node->aux);
 125
 126   /* Perform reachability analysis.  As a special case do not consider
 127      extern inline functions not inlined as live because we won't output
 128      them at all.  */
 129   while (first != (void *) 1)
 130     {
 131       struct cgraph_edge *e;
 132       node = first;
 133       first = (struct cgraph_node *) first->aux;
 134
 135       for (e = node->callees; e; e = e->next_callee)
 136         if (!e->callee->aux
 137             && node->analyzed
 138             && (!e->inline_failed || !e->callee->analyzed
 139                 || (!DECL_EXTERNAL (e->callee->decl))
 140                 || before_inlining_p))
 141           {
 142             e->callee->aux = first;
 143             first = e->callee;
 144           }
 145     }
 146
 147   /* Remove unreachable nodes.  Extern inline functions need special care;
 148      Unreachable extern inline functions shall be removed.
 149      Reachable extern inline functions we never inlined shall get their bodies
 150      eliminated.
 151      Reachable extern inline functions we sometimes inlined will be turned into
 152      unanalyzed nodes so they look like for true extern functions to the rest
 153      of code.  Body of such functions is released via remove_node once the
 154      inline clones are eliminated.  */
 155   for (node = cgraph_nodes; node; node = next)
 156     {
 157       next = node->next;
 158       if (!node->aux)
 159         {
 160           node->global.inlined_to = NULL;
 161           if (file)
 162             fprintf (file, " %s", cgraph_node_name (node));
 163           if (!node->analyzed || !DECL_EXTERNAL (node->decl)
 164               || before_inlining_p)
 165             cgraph_remove_node (node);
 166           else
 167             {
 168               struct cgraph_edge *e;
 169
 170               for (e = node->callers; e; e = e->next_caller)
 171                 if (e->caller->aux)
 172                   break;
 173               if (e || node->needed)
 174                 {
 175                   struct cgraph_node *clone;
 176
 177                   for (clone = node->next_clone; clone;
 178                        clone = clone->next_clone)
 179                     if (clone->aux)
 180                       break;
 181                   if (!clone)
 182                     {
 183                       cgraph_release_function_body (node);
 184                       node->analyzed = false;
 185                     }
 186                   cgraph_node_remove_callees (node);
 187                   node->analyzed = false;
 188                   node->local.inlinable = false;
 189                 }
 190               else
 191                 cgraph_remove_node (node);
 192             }
 193           changed = true;
 194         }
 195     }
 196   for (node = cgraph_nodes; node; node = node->next)
 197     node->aux = NULL;
 198 #ifdef ENABLE_CHECKING
 199   verify_cgraph ();
 200 #endif
 201   return changed;
 202 }
 203
 204 /* Mark visibility of all functions.
 205
 206    A local function is one whose calls can occur only in the current
 207    compilation unit and all its calls are explicit, so we can change
 208    its calling convention.  We simply mark all static functions whose
 209    address is not taken as local.
 210
 211    We also change the TREE_PUBLIC flag of all declarations that are public
 212    in language point of view but we want to overwrite this default
 213    via visibilities for the backend point of view.  */
 214
 215 static unsigned int
 216 function_and_variable_visibility (void)
 217 {
 218   struct cgraph_node *node;
 219   struct varpool_node *vnode;
 220
 221   for (node = cgraph_nodes; node; node = node->next)
 222     {
 223       if (node->reachable
 224           && (DECL_COMDAT (node->decl)
 225               || (!flag_whole_program
 226                   && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
 227         node->local.externally_visible = true;
 228       if (!node->local.externally_visible && node->analyzed
 229           && !DECL_EXTERNAL (node->decl))
 230         {
 231           gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
 232           TREE_PUBLIC (node->decl) = 0;
 233         }
 234       node->local.local = (!node->needed
 235                            && node->analyzed
 236                            && !DECL_EXTERNAL (node->decl)
 237                            && !node->local.externally_visible);
 238     }
 239   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 240     {
 241       if (vnode->needed
 242           && !flag_whole_program
 243           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
 244         vnode->externally_visible = 1;
 245       if (!vnode->externally_visible)
 246         {
 247           gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl));
 248           TREE_PUBLIC (vnode->decl) = 0;
 249         }
 250      gcc_assert (TREE_STATIC (vnode->decl));
 251     }
 252
 253   if (dump_file)
 254     {
 255       fprintf (dump_file, "\nMarking local functions:");
 256       for (node = cgraph_nodes; node; node = node->next)
 257         if (node->local.local)
 258           fprintf (dump_file, " %s", cgraph_node_name (node));
 259       fprintf (dump_file, "\n\n");
 260       fprintf (dump_file, "\nMarking externally visible functions:");
 261       for (node = cgraph_nodes; node; node = node->next)
 262         if (node->local.externally_visible)
 263           fprintf (dump_file, " %s", cgraph_node_name (node));
 264       fprintf (dump_file, "\n\n");
 265     }
 266   cgraph_function_flags_ready = true;
 267   return 0;
 268 }
 269
 270 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
 271 {
 272  {
 273   SIMPLE_IPA_PASS,
 274   "visibility",                         /* name */
 275   NULL,                                 /* gate */
 276   function_and_variable_visibility,     /* execute */
 277   NULL,                                 /* sub */
 278   NULL,                                 /* next */
 279   0,                                    /* static_pass_number */
 280   TV_CGRAPHOPT,                         /* tv_id */
 281   0,                                    /* properties_required */
 282   0,                                    /* properties_provided */
 283   0,                                    /* properties_destroyed */
 284   0,                                    /* todo_flags_start */
 285   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
 286  }
 287 };