gcc/ipa.c

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