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