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