gcc/ipa-utils.c

   1 /* Utilities for ipa analysis.
   2    Copyright (C) 2005, 2007, 2008 Free Software Foundation, Inc.
   3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
   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 "tree.h"
  26 #include "tree-flow.h"
  27 #include "tree-inline.h"
  28 #include "dumpfile.h"
  29 #include "langhooks.h"
  30 #include "pointer-set.h"
  31 #include "splay-tree.h"
  32 #include "ggc.h"
  33 #include "ipa-utils.h"
  34 #include "ipa-reference.h"
  35 #include "gimple.h"
  36 #include "cgraph.h"
  37 #include "flags.h"
  38 #include "diagnostic.h"
  39 #include "langhooks.h"
  40
  41 /* Debugging function for postorder and inorder code. NOTE is a string
  42    that is printed before the nodes are printed.  ORDER is an array of
  43    cgraph_nodes that has COUNT useful nodes in it.  */
  44
  45 void
  46 ipa_print_order (FILE* out,
  47                  const char * note,
  48                  struct cgraph_node** order,
  49                  int count)
  50 {
  51   int i;
  52   fprintf (out, "\n\n ordered call graph: %s\n", note);
  53
  54   for (i = count - 1; i >= 0; i--)
  55     dump_cgraph_node(dump_file, order[i]);
  56   fprintf (out, "\n");
  57   fflush(out);
  58 }
  59
  60 \f
  61 struct searchc_env {
  62   struct cgraph_node **stack;
  63   int stack_size;
  64   struct cgraph_node **result;
  65   int order_pos;
  66   splay_tree nodes_marked_new;
  67   bool reduce;
  68   bool allow_overwritable;
  69   int count;
  70 };
  71
  72 /* This is an implementation of Tarjan's strongly connected region
  73    finder as reprinted in Aho Hopcraft and Ullman's The Design and
  74    Analysis of Computer Programs (1975) pages 192-193.  This version
  75    has been customized for cgraph_nodes.  The env parameter is because
  76    it is recursive and there are no nested functions here.  This
  77    function should only be called from itself or
  78    ipa_reduced_postorder.  ENV is a stack env and would be
  79    unnecessary if C had nested functions.  V is the node to start
  80    searching from.  */
  81
  82 static void
  83 searchc (struct searchc_env* env, struct cgraph_node *v,
  84          bool (*ignore_edge) (struct cgraph_edge *))
  85 {
  86   struct cgraph_edge *edge;
  87   struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->symbol.aux;
  88
  89   /* mark node as old */
  90   v_info->new_node = false;
  91   splay_tree_remove (env->nodes_marked_new, v->uid);
  92
  93   v_info->dfn_number = env->count;
  94   v_info->low_link = env->count;
  95   env->count++;
  96   env->stack[(env->stack_size)++] = v;
  97   v_info->on_stack = true;
  98
  99   for (edge = v->callees; edge; edge = edge->next_callee)
 100     {
 101       struct ipa_dfs_info * w_info;
 102       enum availability avail;
 103       struct cgraph_node *w = cgraph_function_or_thunk_node (edge->callee, &avail);
 104
 105       if (!w || (ignore_edge && ignore_edge (edge)))
 106         continue;
 107
 108       if (w->symbol.aux
 109           && (avail > AVAIL_OVERWRITABLE
 110               || (env->allow_overwritable && avail == AVAIL_OVERWRITABLE)))
 111         {
 112           w_info = (struct ipa_dfs_info *) w->symbol.aux;
 113           if (w_info->new_node)
 114             {
 115               searchc (env, w, ignore_edge);
 116               v_info->low_link =
 117                 (v_info->low_link < w_info->low_link) ?
 118                 v_info->low_link : w_info->low_link;
 119             }
 120           else
 121             if ((w_info->dfn_number < v_info->dfn_number)
 122                 && (w_info->on_stack))
 123               v_info->low_link =
 124                 (w_info->dfn_number < v_info->low_link) ?
 125                 w_info->dfn_number : v_info->low_link;
 126         }
 127     }
 128
 129
 130   if (v_info->low_link == v_info->dfn_number)
 131     {
 132       struct cgraph_node *last = NULL;
 133       struct cgraph_node *x;
 134       struct ipa_dfs_info *x_info;
 135       do {
 136         x = env->stack[--(env->stack_size)];
 137         x_info = (struct ipa_dfs_info *) x->symbol.aux;
 138         x_info->on_stack = false;
 139         x_info->scc_no = v_info->dfn_number;
 140
 141         if (env->reduce)
 142           {
 143             x_info->next_cycle = last;
 144             last = x;
 145           }
 146         else
 147           env->result[env->order_pos++] = x;
 148       }
 149       while (v != x);
 150       if (env->reduce)
 151         env->result[env->order_pos++] = v;
 152     }
 153 }
 154
 155 /* Topsort the call graph by caller relation.  Put the result in ORDER.
 156
 157    The REDUCE flag is true if you want the cycles reduced to single nodes.  Set
 158    ALLOW_OVERWRITABLE if nodes with such availability should be included.
 159    IGNORE_EDGE, if non-NULL is a hook that may make some edges insignificant
 160    for the topological sort.   */
 161
 162 int
 163 ipa_reduced_postorder (struct cgraph_node **order,
 164                        bool reduce, bool allow_overwritable,
 165                        bool (*ignore_edge) (struct cgraph_edge *))
 166 {
 167   struct cgraph_node *node;
 168   struct searchc_env env;
 169   splay_tree_node result;
 170   env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 171   env.stack_size = 0;
 172   env.result = order;
 173   env.order_pos = 0;
 174   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
 175   env.count = 1;
 176   env.reduce = reduce;
 177   env.allow_overwritable = allow_overwritable;
 178
 179   FOR_EACH_DEFINED_FUNCTION (node)
 180     {
 181       enum availability avail = cgraph_function_body_availability (node);
 182
 183       if (avail > AVAIL_OVERWRITABLE
 184           || (allow_overwritable
 185               && (avail == AVAIL_OVERWRITABLE)))
 186         {
 187           /* Reuse the info if it is already there.  */
 188           struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->symbol.aux;
 189           if (!info)
 190             info = XCNEW (struct ipa_dfs_info);
 191           info->new_node = true;
 192           info->on_stack = false;
 193           info->next_cycle = NULL;
 194           node->symbol.aux = info;
 195
 196           splay_tree_insert (env.nodes_marked_new,
 197                              (splay_tree_key)node->uid,
 198                              (splay_tree_value)node);
 199         }
 200       else
 201         node->symbol.aux = NULL;
 202     }
 203   result = splay_tree_min (env.nodes_marked_new);
 204   while (result)
 205     {
 206       node = (struct cgraph_node *)result->value;
 207       searchc (&env, node, ignore_edge);
 208       result = splay_tree_min (env.nodes_marked_new);
 209     }
 210   splay_tree_delete (env.nodes_marked_new);
 211   free (env.stack);
 212
 213   return env.order_pos;
 214 }
 215
 216 /* Deallocate all ipa_dfs_info structures pointed to by the aux pointer of call
 217    graph nodes.  */
 218
 219 void
 220 ipa_free_postorder_info (void)
 221 {
 222   struct cgraph_node *node;
 223   FOR_EACH_DEFINED_FUNCTION (node)
 224     {
 225       /* Get rid of the aux information.  */
 226       if (node->symbol.aux)
 227         {
 228           free (node->symbol.aux);
 229           node->symbol.aux = NULL;
 230         }
 231     }
 232 }
 233
 234 struct postorder_stack
 235 {
 236   struct cgraph_node *node;
 237   struct cgraph_edge *edge;
 238   int ref;
 239 };
 240
 241 /* Fill array order with all nodes with output flag set in the reverse
 242    topological order.  Return the number of elements in the array.
 243    FIXME: While walking, consider aliases, too.  */
 244
 245 int
 246 ipa_reverse_postorder (struct cgraph_node **order)
 247 {
 248   struct cgraph_node *node, *node2;
 249   int stack_size = 0;
 250   int order_pos = 0;
 251   struct cgraph_edge *edge;
 252   int pass;
 253   struct ipa_ref *ref;
 254
 255   struct postorder_stack *stack =
 256     XCNEWVEC (struct postorder_stack, cgraph_n_nodes);
 257
 258   /* We have to deal with cycles nicely, so use a depth first traversal
 259      output algorithm.  Ignore the fact that some functions won't need
 260      to be output and put them into order as well, so we get dependencies
 261      right through inline functions.  */
 262   FOR_EACH_FUNCTION (node)
 263     node->symbol.aux = NULL;
 264   for (pass = 0; pass < 2; pass++)
 265     FOR_EACH_FUNCTION (node)
 266       if (!node->symbol.aux
 267           && (pass
 268               || (!node->symbol.address_taken
 269                   && !node->global.inlined_to
 270                   && !node->alias && !node->thunk.thunk_p
 271                   && !cgraph_only_called_directly_p (node))))
 272         {
 273           stack_size = 0;
 274           stack[stack_size].node = node;
 275           stack[stack_size].edge = node->callers;
 276           stack[stack_size].ref = 0;
 277           node->symbol.aux = (void *)(size_t)1;
 278           while (stack_size >= 0)
 279             {
 280               while (true)
 281                 {
 282                   node2 = NULL;
 283                   while (stack[stack_size].edge && !node2)
 284                     {
 285                       edge = stack[stack_size].edge;
 286                       node2 = edge->caller;
 287                       stack[stack_size].edge = edge->next_caller;
 288                       /* Break possible cycles involving always-inline
 289                          functions by ignoring edges from always-inline
 290                          functions to non-always-inline functions.  */
 291                       if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->symbol.decl)
 292                           && !DECL_DISREGARD_INLINE_LIMITS
 293                             (cgraph_function_node (edge->callee, NULL)->symbol.decl))
 294                         node2 = NULL;
 295                     }
 296                   for (;ipa_ref_list_referring_iterate (&stack[stack_size].node->symbol.ref_list,
 297                                                        stack[stack_size].ref,
 298                                                        ref) && !node2;
 299                        stack[stack_size].ref++)
 300                     {
 301                       if (ref->use == IPA_REF_ALIAS)
 302                         node2 = ipa_ref_referring_node (ref);
 303                     }
 304                   if (!node2)
 305                     break;
 306                   if (!node2->symbol.aux)
 307                     {
 308                       stack[++stack_size].node = node2;
 309                       stack[stack_size].edge = node2->callers;
 310                       stack[stack_size].ref = 0;
 311                       node2->symbol.aux = (void *)(size_t)1;
 312                     }
 313                 }
 314               order[order_pos++] = stack[stack_size--].node;
 315             }
 316         }
 317   free (stack);
 318   FOR_EACH_FUNCTION (node)
 319     node->symbol.aux = NULL;
 320   return order_pos;
 321 }
 322
 323
 324
 325 /* Given a memory reference T, will return the variable at the bottom
 326    of the access.  Unlike get_base_address, this will recurse through
 327    INDIRECT_REFS.  */
 328
 329 tree
 330 get_base_var (tree t)
 331 {
 332   while (!SSA_VAR_P (t)
 333          && (!CONSTANT_CLASS_P (t))
 334          && TREE_CODE (t) != LABEL_DECL
 335          && TREE_CODE (t) != FUNCTION_DECL
 336          && TREE_CODE (t) != CONST_DECL
 337          && TREE_CODE (t) != CONSTRUCTOR)
 338     {
 339       t = TREE_OPERAND (t, 0);
 340     }
 341   return t;
 342 }
 343
 344
 345 /* Create a new cgraph node set.  */
 346
 347 cgraph_node_set
 348 cgraph_node_set_new (void)
 349 {
 350   cgraph_node_set new_node_set;
 351
 352   new_node_set = XCNEW (struct cgraph_node_set_def);
 353   new_node_set->map = pointer_map_create ();
 354   new_node_set->nodes = NULL;
 355   return new_node_set;
 356 }
 357
 358
 359 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 360
 361 void
 362 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 363 {
 364   void **slot;
 365
 366   slot = pointer_map_insert (set->map, node);
 367
 368   if (*slot)
 369     {
 370       int index = (size_t) *slot - 1;
 371       gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index)
 372                            == node));
 373       return;
 374     }
 375
 376   *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1);
 377
 378   /* Insert into node vector.  */
 379   VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node);
 380 }
 381
 382
 383 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 384
 385 void
 386 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 387 {
 388   void **slot, **last_slot;
 389   int index;
 390   struct cgraph_node *last_node;
 391
 392   slot = pointer_map_contains (set->map, node);
 393   if (slot == NULL || !*slot)
 394     return;
 395
 396   index = (size_t) *slot - 1;
 397   gcc_checking_assert (VEC_index (cgraph_node_ptr, set->nodes, index)
 398                        == node);
 399
 400   /* Remove from vector. We do this by swapping node with the last element
 401      of the vector.  */
 402   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 403   if (last_node != node)
 404     {
 405       last_slot = pointer_map_contains (set->map, last_node);
 406       gcc_checking_assert (last_slot && *last_slot);
 407       *last_slot = (void *)(size_t) (index + 1);
 408
 409       /* Move the last element to the original spot of NODE.  */
 410       VEC_replace (cgraph_node_ptr, set->nodes, index, last_node);
 411     }
 412
 413   /* Remove element from hash table.  */
 414   *slot = NULL;
 415 }
 416
 417
 418 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 419    is returned if NODE is not in SET.  */
 420
 421 cgraph_node_set_iterator
 422 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 423 {
 424   void **slot;
 425   cgraph_node_set_iterator csi;
 426
 427   slot = pointer_map_contains (set->map, node);
 428   if (slot == NULL || !*slot)
 429     csi.index = (unsigned) ~0;
 430   else
 431     csi.index = (size_t)*slot - 1;
 432   csi.set = set;
 433
 434   return csi;
 435 }
 436
 437
 438 /* Dump content of SET to file F.  */
 439
 440 void
 441 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 442 {
 443   cgraph_node_set_iterator iter;
 444
 445   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 446     {
 447       struct cgraph_node *node = csi_node (iter);
 448       fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
 449     }
 450   fprintf (f, "\n");
 451 }
 452
 453
 454 /* Dump content of SET to stderr.  */
 455
 456 DEBUG_FUNCTION void
 457 debug_cgraph_node_set (cgraph_node_set set)
 458 {
 459   dump_cgraph_node_set (stderr, set);
 460 }
 461
 462
 463 /* Free varpool node set.  */
 464
 465 void
 466 free_cgraph_node_set (cgraph_node_set set)
 467 {
 468   VEC_free (cgraph_node_ptr, heap, set->nodes);
 469   pointer_map_destroy (set->map);
 470   free (set);
 471 }
 472
 473
 474 /* Create a new varpool node set.  */
 475
 476 varpool_node_set
 477 varpool_node_set_new (void)
 478 {
 479   varpool_node_set new_node_set;
 480
 481   new_node_set = XCNEW (struct varpool_node_set_def);
 482   new_node_set->map = pointer_map_create ();
 483   new_node_set->nodes = NULL;
 484   return new_node_set;
 485 }
 486
 487
 488 /* Add varpool_node NODE to varpool_node_set SET.  */
 489
 490 void
 491 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
 492 {
 493   void **slot;
 494
 495   slot = pointer_map_insert (set->map, node);
 496
 497   if (*slot)
 498     {
 499       int index = (size_t) *slot - 1;
 500       gcc_checking_assert ((VEC_index (varpool_node_ptr, set->nodes, index)
 501                            == node));
 502       return;
 503     }
 504
 505   *slot = (void *)(size_t) (VEC_length (varpool_node_ptr, set->nodes) + 1);
 506
 507   /* Insert into node vector.  */
 508   VEC_safe_push (varpool_node_ptr, heap, set->nodes, node);
 509 }
 510
 511
 512 /* Remove varpool_node NODE from varpool_node_set SET.  */
 513
 514 void
 515 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
 516 {
 517   void **slot, **last_slot;
 518   int index;
 519   struct varpool_node *last_node;
 520
 521   slot = pointer_map_contains (set->map, node);
 522   if (slot == NULL || !*slot)
 523     return;
 524
 525   index = (size_t) *slot - 1;
 526   gcc_checking_assert (VEC_index (varpool_node_ptr, set->nodes, index)
 527                        == node);
 528
 529   /* Remove from vector. We do this by swapping node with the last element
 530      of the vector.  */
 531   last_node = VEC_pop (varpool_node_ptr, set->nodes);
 532   if (last_node != node)
 533     {
 534       last_slot = pointer_map_contains (set->map, last_node);
 535       gcc_checking_assert (last_slot && *last_slot);
 536       *last_slot = (void *)(size_t) (index + 1);
 537
 538       /* Move the last element to the original spot of NODE.  */
 539       VEC_replace (varpool_node_ptr, set->nodes, index, last_node);
 540     }
 541
 542   /* Remove element from hash table.  */
 543   *slot = NULL;
 544 }
 545
 546
 547 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 548    is returned if NODE is not in SET.  */
 549
 550 varpool_node_set_iterator
 551 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
 552 {
 553   void **slot;
 554   varpool_node_set_iterator vsi;
 555
 556   slot = pointer_map_contains (set->map, node);
 557   if (slot == NULL || !*slot)
 558     vsi.index = (unsigned) ~0;
 559   else
 560     vsi.index = (size_t)*slot - 1;
 561   vsi.set = set;
 562
 563   return vsi;
 564 }
 565
 566
 567 /* Dump content of SET to file F.  */
 568
 569 void
 570 dump_varpool_node_set (FILE *f, varpool_node_set set)
 571 {
 572   varpool_node_set_iterator iter;
 573
 574   for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
 575     {
 576       struct varpool_node *node = vsi_node (iter);
 577       fprintf (f, " %s", varpool_node_name (node));
 578     }
 579   fprintf (f, "\n");
 580 }
 581
 582
 583 /* Free varpool node set.  */
 584
 585 void
 586 free_varpool_node_set (varpool_node_set set)
 587 {
 588   VEC_free (varpool_node_ptr, heap, set->nodes);
 589   pointer_map_destroy (set->map);
 590   free (set);
 591 }
 592
 593
 594 /* Dump content of SET to stderr.  */
 595
 596 DEBUG_FUNCTION void
 597 debug_varpool_node_set (varpool_node_set set)
 598 {
 599   dump_varpool_node_set (stderr, set);
 600 }