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