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