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