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