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   int insns = 0;
 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           int local_insns;
 161           tree decl = node->decl;
 162
 163           node->global.inlined_to = NULL;
 164           if (DECL_STRUCT_FUNCTION (decl))
 165             local_insns = node->local.self_insns;
 166           else
 167             local_insns = 0;
 168           if (file)
 169             fprintf (file, " %s", cgraph_node_name (node));
 170           if (!node->analyzed || !DECL_EXTERNAL (node->decl)
 171               || before_inlining_p)
 172             cgraph_remove_node (node);
 173           else
 174             {
 175               struct cgraph_edge *e;
 176
 177               for (e = node->callers; e; e = e->next_caller)
 178                 if (e->caller->aux)
 179                   break;
 180               if (e || node->needed)
 181                 {
 182                   struct cgraph_node *clone;
 183
 184                   for (clone = node->next_clone; clone;
 185                        clone = clone->next_clone)
 186                     if (clone->aux)
 187                       break;
 188                   if (!clone)
 189                     {
 190                       cgraph_release_function_body (node);
 191                       node->analyzed = false;
 192                     }
 193                   cgraph_node_remove_callees (node);
 194                   node->analyzed = false;
 195                 }
 196               else
 197                 cgraph_remove_node (node);
 198             }
 199           if (!DECL_SAVED_TREE (decl))
 200             insns += local_insns;
 201           changed = true;
 202         }
 203     }
 204   for (node = cgraph_nodes; node; node = node->next)
 205     node->aux = NULL;
 206   if (file)
 207     fprintf (file, "\nReclaimed %i insns", insns);
 208 #ifdef ENABLE_CHECKING
 209   verify_cgraph ();
 210 #endif
 211   return changed;
 212 }
 213
 214 /* Mark visibility of all functions.
 215
 216    A local function is one whose calls can occur only in the current
 217    compilation unit and all its calls are explicit, so we can change
 218    its calling convention.  We simply mark all static functions whose
 219    address is not taken as local.
 220
 221    We also change the TREE_PUBLIC flag of all declarations that are public
 222    in language point of view but we want to overwrite this default
 223    via visibilities for the backend point of view.  */
 224
 225 static unsigned int
 226 function_and_variable_visibility (void)
 227 {
 228   struct cgraph_node *node;
 229   struct varpool_node *vnode;
 230
 231   for (node = cgraph_nodes; node; node = node->next)
 232     {
 233       if (node->reachable
 234           && (DECL_COMDAT (node->decl)
 235               || (!flag_whole_program
 236                   && TREE_PUBLIC (node->decl) && !DECL_EXTERNAL (node->decl))))
 237         node->local.externally_visible = true;
 238       if (!node->local.externally_visible && node->analyzed
 239           && !DECL_EXTERNAL (node->decl))
 240         {
 241           gcc_assert (flag_whole_program || !TREE_PUBLIC (node->decl));
 242           TREE_PUBLIC (node->decl) = 0;
 243         }
 244       node->local.local = (!node->needed
 245                            && node->analyzed
 246                            && !DECL_EXTERNAL (node->decl)
 247                            && !node->local.externally_visible);
 248     }
 249   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 250     {
 251       if (vnode->needed
 252           && !flag_whole_program
 253           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl)))
 254         vnode->externally_visible = 1;
 255       if (!vnode->externally_visible)
 256         {
 257           gcc_assert (flag_whole_program || !TREE_PUBLIC (vnode->decl));
 258           TREE_PUBLIC (vnode->decl) = 0;
 259         }
 260      gcc_assert (TREE_STATIC (vnode->decl));
 261     }
 262
 263   if (dump_file)
 264     {
 265       fprintf (dump_file, "\nMarking local functions:");
 266       for (node = cgraph_nodes; node; node = node->next)
 267         if (node->local.local)
 268           fprintf (dump_file, " %s", cgraph_node_name (node));
 269       fprintf (dump_file, "\n\n");
 270       fprintf (dump_file, "\nMarking externally visible functions:");
 271       for (node = cgraph_nodes; node; node = node->next)
 272         if (node->local.externally_visible)
 273           fprintf (dump_file, " %s", cgraph_node_name (node));
 274       fprintf (dump_file, "\n\n");
 275     }
 276   cgraph_function_flags_ready = true;
 277   return 0;
 278 }
 279
 280 struct tree_opt_pass pass_ipa_function_and_variable_visibility =
 281 {
 282   "visibility",                         /* name */
 283   NULL,                                 /* gate */
 284   function_and_variable_visibility,     /* execute */
 285   NULL,                                 /* sub */
 286   NULL,                                 /* next */
 287   0,                                    /* static_pass_number */
 288   TV_CGRAPHOPT,                         /* tv_id */
 289   0,                                    /* properties_required */
 290   0,                                    /* properties_provided */
 291   0,                                    /* properties_destroyed */
 292   0,                                    /* todo_flags_start */
 293   TODO_remove_functions | TODO_dump_cgraph,/* todo_flags_finish */
 294   0                                     /* letter */
 295 };