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
  56               || (!cgraph_only_called_directly_p (node)
  57                   && !node->address_taken)))
  58         {
  59           node2 = node;
  60           if (!node->callers)
  61             node->aux = &last;
  62           else
  63             node->aux = node->callers;
  64           while (node2)
  65             {
  66               while (node2->aux != &last)
  67                 {
  68                   edge = (struct cgraph_edge *) node2->aux;
  69                   if (edge->next_caller)
  70                     node2->aux = edge->next_caller;
  71                   else
  72                     node2->aux = &last;
  73                   if (!edge->caller->aux)
  74                     {
  75                       if (!edge->caller->callers)
  76                         edge->caller->aux = &last;
  77                       else
  78                         edge->caller->aux = edge->caller->callers;
  79                       stack[stack_size++] = node2;
  80                       node2 = edge->caller;
  81                       break;
  82                     }
  83                 }
  84               if (node2->aux == &last)
  85                 {
  86                   order[order_pos++] = node2;
  87                   if (stack_size)
  88                     node2 = stack[--stack_size];
  89                   else
  90                     node2 = NULL;
  91                 }
  92             }
  93         }
  94   free (stack);
  95   for (node = cgraph_nodes; node; node = node->next)
  96     node->aux = NULL;
  97   return order_pos;
  98 }
  99
 100 /* Look for all functions inlined to NODE and update their inlined_to pointers
 101    to INLINED_TO.  */
 102
 103 static void
 104 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
 105 {
 106   struct cgraph_edge *e;
 107   for (e = node->callees; e; e = e->next_callee)
 108     if (e->callee->global.inlined_to)
 109       {
 110         e->callee->global.inlined_to = inlined_to;
 111         update_inlined_to_pointer (e->callee, inlined_to);
 112       }
 113 }
 114
 115 /* Perform reachability analysis and reclaim all unreachable nodes.
 116    If BEFORE_INLINING_P is true this function is called before inlining
 117    decisions has been made.  If BEFORE_INLINING_P is false this function also
 118    removes unneeded bodies of extern inline functions.  */
 119
 120 bool
 121 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 122 {
 123   struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
 124   struct cgraph_node *node, *next;
 125   bool changed = false;
 126
 127 #ifdef ENABLE_CHECKING
 128   verify_cgraph ();
 129 #endif
 130   if (file)
 131     fprintf (file, "\nReclaiming functions:");
 132 #ifdef ENABLE_CHECKING
 133   for (node = cgraph_nodes; node; node = node->next)
 134     gcc_assert (!node->aux);
 135 #endif
 136   for (node = cgraph_nodes; node; node = node->next)
 137     if (!cgraph_can_remove_if_no_direct_calls_p (node)
 138         && ((!DECL_EXTERNAL (node->decl))
 139             || !node->analyzed
 140             || before_inlining_p))
 141       {
 142         gcc_assert (!node->global.inlined_to);
 143         node->aux = first;
 144         first = node;
 145       }
 146     else
 147       gcc_assert (!node->aux);
 148
 149   /* Perform reachability analysis.  As a special case do not consider
 150      extern inline functions not inlined as live because we won't output
 151      them at all.  */
 152   while (first != (void *) 1)
 153     {
 154       struct cgraph_edge *e;
 155       node = first;
 156       first = (struct cgraph_node *) first->aux;
 157
 158       for (e = node->callees; e; e = e->next_callee)
 159         if (!e->callee->aux
 160             && node->analyzed
 161             && (!e->inline_failed || !e->callee->analyzed
 162                 || (!DECL_EXTERNAL (e->callee->decl))
 163                 || before_inlining_p))
 164           {
 165             e->callee->aux = first;
 166             first = e->callee;
 167           }
 168       while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
 169         {
 170           node = node->clone_of;
 171           node->aux = first;
 172           first = node;
 173         }
 174     }
 175
 176   /* Remove unreachable nodes.  Extern inline functions need special care;
 177      Unreachable extern inline functions shall be removed.
 178      Reachable extern inline functions we never inlined shall get their bodies
 179      eliminated.
 180      Reachable extern inline functions we sometimes inlined will be turned into
 181      unanalyzed nodes so they look like for true extern functions to the rest
 182      of code.  Body of such functions is released via remove_node once the
 183      inline clones are eliminated.  */
 184   for (node = cgraph_nodes; node; node = next)
 185     {
 186       next = node->next;
 187       if (!node->aux)
 188         {
 189           node->global.inlined_to = NULL;
 190           if (file)
 191             fprintf (file, " %s", cgraph_node_name (node));
 192           if (!node->analyzed || !DECL_EXTERNAL (node->decl)
 193               || before_inlining_p)
 194             cgraph_remove_node (node);
 195           else
 196             {
 197               struct cgraph_edge *e;
 198
 199               /* See if there is reachable caller.  */
 200               for (e = node->callers; e; e = e->next_caller)
 201                 if (e->caller->aux)
 202                   break;
 203
 204               /* If so, we need to keep node in the callgraph.  */
 205               if (e || node->needed)
 206                 {
 207                   struct cgraph_node *clone;
 208
 209                   /* If there are still clones, we must keep body around.
 210                      Otherwise we can just remove the body but keep the clone.  */
 211                   for (clone = node->clones; clone;
 212                        clone = clone->next_sibling_clone)
 213                     if (clone->aux)
 214                       break;
 215                   if (!clone)
 216                     {
 217                       cgraph_release_function_body (node);
 218                       cgraph_node_remove_callees (node);
 219                       node->analyzed = false;
 220                       node->local.inlinable = false;
 221                     }
 222                 }
 223               else
 224                 cgraph_remove_node (node);
 225             }
 226           changed = true;
 227         }
 228     }
 229   for (node = cgraph_nodes; node; node = node->next)
 230     {
 231       /* Inline clones might be kept around so their materializing allows further
 232          cloning.  If the function the clone is inlined into is removed, we need
 233          to turn it into normal cone.  */
 234       if (node->global.inlined_to
 235           && !node->callers)
 236         {
 237           gcc_assert (node->clones);
 238           node->global.inlined_to = NULL;
 239           update_inlined_to_pointer (node, node);
 240         }
 241       node->aux = NULL;
 242     }
 243 #ifdef ENABLE_CHECKING
 244   verify_cgraph ();
 245 #endif
 246
 247   /* Reclaim alias pairs for functions that have disappeared from the
 248      call graph.  */
 249   remove_unreachable_alias_pairs ();
 250
 251   return changed;
 252 }
 253
 254 static bool
 255 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program)
 256 {
 257   if (!DECL_COMDAT (node->decl)
 258       && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
 259     return false;
 260   if (!whole_program)
 261     return true;
 262   /* COMDAT functions must be shared only if they have address taken,
 263      otherwise we can produce our own private implementation with
 264      -fwhole-program.  */
 265   if (DECL_COMDAT (node->decl) && (node->address_taken || !node->analyzed))
 266     return true;
 267   if (MAIN_NAME_P (DECL_NAME (node->decl)))
 268     return true;
 269   if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
 270     return true;
 271   return false;
 272 }
 273
 274 /* Mark visibility of all functions.
 275
 276    A local function is one whose calls can occur only in the current
 277    compilation unit and all its calls are explicit, so we can change
 278    its calling convention.  We simply mark all static functions whose
 279    address is not taken as local.
 280
 281    We also change the TREE_PUBLIC flag of all declarations that are public
 282    in language point of view but we want to overwrite this default
 283    via visibilities for the backend point of view.  */
 284
 285 static unsigned int
 286 function_and_variable_visibility (bool whole_program)
 287 {
 288   struct cgraph_node *node;
 289   struct varpool_node *vnode;
 290
 291   for (node = cgraph_nodes; node; node = node->next)
 292     {
 293       if (cgraph_externally_visible_p (node, whole_program))
 294         {
 295           gcc_assert (!node->global.inlined_to);
 296           node->local.externally_visible = true;
 297         }
 298       else
 299         node->local.externally_visible = false;
 300       if (!node->local.externally_visible && node->analyzed
 301           && !DECL_EXTERNAL (node->decl))
 302         {
 303           gcc_assert (whole_program || !TREE_PUBLIC (node->decl));
 304           TREE_PUBLIC (node->decl) = 0;
 305           DECL_COMDAT (node->decl) = 0;
 306           DECL_WEAK (node->decl) = 0;
 307         }
 308       node->local.local = (cgraph_only_called_directly_p (node)
 309                            && node->analyzed
 310                            && !DECL_EXTERNAL (node->decl)
 311                            && !node->local.externally_visible);
 312     }
 313   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 314     {
 315       if (vnode->needed
 316           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
 317           && (!whole_program
 318               || lookup_attribute ("externally_visible",
 319                                    DECL_ATTRIBUTES (vnode->decl))))
 320         vnode->externally_visible = true;
 321       else
 322         vnode->externally_visible = false;
 323       if (!vnode->externally_visible)
 324         {
 325           gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl));
 326           TREE_PUBLIC (vnode->decl) = 0;
 327         }
 328      gcc_assert (TREE_STATIC (vnode->decl));
 329     }
 330
 331   if (dump_file)
 332     {
 333       fprintf (dump_file, "\nMarking local functions:");
 334       for (node = cgraph_nodes; node; node = node->next)
 335         if (node->local.local)
 336           fprintf (dump_file, " %s", cgraph_node_name (node));
 337       fprintf (dump_file, "\n\n");
 338       fprintf (dump_file, "\nMarking externally visible functions:");
 339       for (node = cgraph_nodes; node; node = node->next)
 340         if (node->local.externally_visible)
 341           fprintf (dump_file, " %s", cgraph_node_name (node));
 342       fprintf (dump_file, "\n\n");
 343     }
 344   cgraph_function_flags_ready = true;
 345   return 0;
 346 }
 347
 348 /* Local function pass handling visibilities.  This happens before LTO streaming
 349    so in particular -fwhole-program should be ignored at this level.  */
 350
 351 static unsigned int
 352 local_function_and_variable_visibility (void)
 353 {
 354   return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
 355 }
 356
 357 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
 358 {
 359  {
 360   SIMPLE_IPA_PASS,
 361   "visibility",                         /* name */
 362   NULL,                                 /* gate */
 363   local_function_and_variable_visibility,/* execute */
 364   NULL,                                 /* sub */
 365   NULL,                                 /* next */
 366   0,                                    /* static_pass_number */
 367   TV_CGRAPHOPT,                         /* tv_id */
 368   0,                                    /* properties_required */
 369   0,                                    /* properties_provided */
 370   0,                                    /* properties_destroyed */
 371   0,                                    /* todo_flags_start */
 372   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
 373  }
 374 };
 375
 376 /* Do not re-run on ltrans stage.  */
 377
 378 static bool
 379 gate_whole_program_function_and_variable_visibility (void)
 380 {
 381   return !flag_ltrans;
 382 }
 383
 384 /* Bring functionss local at LTO time whith -fwhole-program.  */
 385
 386 static unsigned int
 387 whole_program_function_and_variable_visibility (void)
 388 {
 389   struct cgraph_node *node;
 390   struct varpool_node *vnode;
 391
 392   function_and_variable_visibility (flag_whole_program);
 393
 394   for (node = cgraph_nodes; node; node = node->next)
 395     if (node->local.externally_visible)
 396       cgraph_mark_needed_node (node);
 397   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 398     if (vnode->externally_visible)
 399       varpool_mark_needed_node (vnode);
 400   return 0;
 401 }
 402
 403 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
 404 {
 405  {
 406   IPA_PASS,
 407   "whole-program",                      /* name */
 408   gate_whole_program_function_and_variable_visibility,/* gate */
 409   whole_program_function_and_variable_visibility,/* execute */
 410   NULL,                                 /* sub */
 411   NULL,                                 /* next */
 412   0,                                    /* static_pass_number */
 413   TV_CGRAPHOPT,                         /* tv_id */
 414   0,                                    /* properties_required */
 415   0,                                    /* properties_provided */
 416   0,                                    /* properties_destroyed */
 417   0,                                    /* todo_flags_start */
 418   TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */
 419  },
 420  NULL,                                  /* generate_summary */
 421  NULL,                                  /* write_summary */
 422  NULL,                                  /* read_summary */
 423  NULL,                                  /* function_read_summary */
 424  0,                                     /* TODOs */
 425  NULL,                                  /* function_transform */
 426  NULL,                                  /* variable_transform */
 427 };
 428
 429 /* Hash a cgraph node set element.  */
 430
 431 static hashval_t
 432 hash_cgraph_node_set_element (const void *p)
 433 {
 434   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
 435   return htab_hash_pointer (element->node);
 436 }
 437
 438 /* Compare two cgraph node set elements.  */
 439
 440 static int
 441 eq_cgraph_node_set_element (const void *p1, const void *p2)
 442 {
 443   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
 444   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
 445
 446   return e1->node == e2->node;
 447 }
 448
 449 /* Create a new cgraph node set.  */
 450
 451 cgraph_node_set
 452 cgraph_node_set_new (void)
 453 {
 454   cgraph_node_set new_node_set;
 455
 456   new_node_set = GGC_NEW (struct cgraph_node_set_def);
 457   new_node_set->hashtab = htab_create_ggc (10,
 458                                            hash_cgraph_node_set_element,
 459                                            eq_cgraph_node_set_element,
 460                                            NULL);
 461   new_node_set->nodes = NULL;
 462   return new_node_set;
 463 }
 464
 465 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 466
 467 void
 468 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 469 {
 470   void **slot;
 471   cgraph_node_set_element element;
 472   struct cgraph_node_set_element_def dummy;
 473
 474   dummy.node = node;
 475   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
 476
 477   if (*slot != HTAB_EMPTY_ENTRY)
 478     {
 479       element = (cgraph_node_set_element) *slot;
 480       gcc_assert (node == element->node
 481                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 482                       == node));
 483       return;
 484     }
 485
 486   /* Insert node into hash table.  */
 487   element =
 488     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
 489   element->node = node;
 490   element->index = VEC_length (cgraph_node_ptr, set->nodes);
 491   *slot = element;
 492
 493   /* Insert into node vector.  */
 494   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
 495 }
 496
 497 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 498
 499 void
 500 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 501 {
 502   void **slot, **last_slot;
 503   cgraph_node_set_element element, last_element;
 504   struct cgraph_node *last_node;
 505   struct cgraph_node_set_element_def dummy;
 506
 507   dummy.node = node;
 508   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 509   if (slot == NULL)
 510     return;
 511
 512   element = (cgraph_node_set_element) *slot;
 513   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 514               == node);
 515
 516   /* Remove from vector. We do this by swapping node with the last element
 517      of the vector.  */
 518   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 519   if (last_node != node)
 520     {
 521       dummy.node = last_node;
 522       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 523       last_element = (cgraph_node_set_element) *last_slot;
 524       gcc_assert (last_element);
 525
 526       /* Move the last element to the original spot of NODE.  */
 527       last_element->index = element->index;
 528       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
 529                    last_node);
 530     }
 531
 532   /* Remove element from hash table.  */
 533   htab_clear_slot (set->hashtab, slot);
 534   ggc_free (element);
 535 }
 536
 537 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 538    is returned if NODE is not in SET.  */
 539
 540 cgraph_node_set_iterator
 541 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 542 {
 543   void **slot;
 544   struct cgraph_node_set_element_def dummy;
 545   cgraph_node_set_element element;
 546   cgraph_node_set_iterator csi;
 547
 548   dummy.node = node;
 549   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 550   if (slot == NULL)
 551     csi.index = (unsigned) ~0;
 552   else
 553     {
 554       element = (cgraph_node_set_element) *slot;
 555       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 556                   == node);
 557       csi.index = element->index;
 558     }
 559   csi.set = set;
 560
 561   return csi;
 562 }
 563
 564 /* Dump content of SET to file F.  */
 565
 566 void
 567 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 568 {
 569   cgraph_node_set_iterator iter;
 570
 571   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 572     {
 573       struct cgraph_node *node = csi_node (iter);
 574       dump_cgraph_node (f, node);
 575     }
 576 }
 577
 578 /* Dump content of SET to stderr.  */
 579
 580 void
 581 debug_cgraph_node_set (cgraph_node_set set)
 582 {
 583   dump_cgraph_node_set (stderr, set);
 584 }
 585