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    FIXME: While walking, consider aliases, too.  */
 239
 240 int
 241 ipa_reverse_postorder (struct cgraph_node **order)
 242 {
 243   struct cgraph_node *node, *node2;
 244   int stack_size = 0;
 245   int order_pos = 0;
 246   struct cgraph_edge *edge, last;
 247   int pass;
 248
 249   struct cgraph_node **stack =
 250     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 251
 252   /* We have to deal with cycles nicely, so use a depth first traversal
 253      output algorithm.  Ignore the fact that some functions won't need
 254      to be output and put them into order as well, so we get dependencies
 255      right through inline functions.  */
 256   for (node = cgraph_nodes; node; node = node->next)
 257     node->aux = NULL;
 258   for (pass = 0; pass < 2; pass++)
 259     for (node = cgraph_nodes; node; node = node->next)
 260       if (!node->aux
 261           && (pass
 262               || (!node->address_taken
 263                   && !node->global.inlined_to
 264                   && !cgraph_only_called_directly_or_aliased_p (node))))
 265         {
 266           node2 = node;
 267           if (!node->callers)
 268             node->aux = &last;
 269           else
 270             node->aux = node->callers;
 271           while (node2)
 272             {
 273               while (node2->aux != &last)
 274                 {
 275                   edge = (struct cgraph_edge *) node2->aux;
 276                   if (edge->next_caller)
 277                     node2->aux = edge->next_caller;
 278                   else
 279                     node2->aux = &last;
 280                   /* Break possible cycles involving always-inline
 281                      functions by ignoring edges from always-inline
 282                      functions to non-always-inline functions.  */
 283                   if (DECL_DISREGARD_INLINE_LIMITS (edge->caller->decl)
 284                       && !DECL_DISREGARD_INLINE_LIMITS (edge->callee->decl))
 285                     continue;
 286                   if (!edge->caller->aux)
 287                     {
 288                       if (!edge->caller->callers)
 289                         edge->caller->aux = &last;
 290                       else
 291                         edge->caller->aux = edge->caller->callers;
 292                       stack[stack_size++] = node2;
 293                       node2 = edge->caller;
 294                       break;
 295                     }
 296                 }
 297               if (node2->aux == &last)
 298                 {
 299                   order[order_pos++] = node2;
 300                   if (stack_size)
 301                     node2 = stack[--stack_size];
 302                   else
 303                     node2 = NULL;
 304                 }
 305             }
 306         }
 307   free (stack);
 308   for (node = cgraph_nodes; node; node = node->next)
 309     node->aux = NULL;
 310   return order_pos;
 311 }
 312
 313
 314
 315 /* Given a memory reference T, will return the variable at the bottom
 316    of the access.  Unlike get_base_address, this will recurse thru
 317    INDIRECT_REFS.  */
 318
 319 tree
 320 get_base_var (tree t)
 321 {
 322   while (!SSA_VAR_P (t)
 323          && (!CONSTANT_CLASS_P (t))
 324          && TREE_CODE (t) != LABEL_DECL
 325          && TREE_CODE (t) != FUNCTION_DECL
 326          && TREE_CODE (t) != CONST_DECL
 327          && TREE_CODE (t) != CONSTRUCTOR)
 328     {
 329       t = TREE_OPERAND (t, 0);
 330     }
 331   return t;
 332 }
 333
 334
 335 /* Create a new cgraph node set.  */
 336
 337 cgraph_node_set
 338 cgraph_node_set_new (void)
 339 {
 340   cgraph_node_set new_node_set;
 341
 342   new_node_set = XCNEW (struct cgraph_node_set_def);
 343   new_node_set->map = pointer_map_create ();
 344   new_node_set->nodes = NULL;
 345   return new_node_set;
 346 }
 347
 348
 349 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 350
 351 void
 352 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 353 {
 354   void **slot;
 355
 356   slot = pointer_map_insert (set->map, node);
 357
 358   if (*slot)
 359     {
 360       int index = (size_t) *slot - 1;
 361       gcc_checking_assert ((VEC_index (cgraph_node_ptr, set->nodes, index)
 362                            == node));
 363       return;
 364     }
 365
 366   *slot = (void *)(size_t) (VEC_length (cgraph_node_ptr, set->nodes) + 1);
 367
 368   /* Insert into node vector.  */
 369   VEC_safe_push (cgraph_node_ptr, heap, set->nodes, node);
 370 }
 371
 372
 373 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 374
 375 void
 376 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 377 {
 378   void **slot, **last_slot;
 379   int index;
 380   struct cgraph_node *last_node;
 381
 382   slot = pointer_map_contains (set->map, node);
 383   if (slot == NULL || !*slot)
 384     return;
 385
 386   index = (size_t) *slot - 1;
 387   gcc_checking_assert (VEC_index (cgraph_node_ptr, set->nodes, index)
 388                        == node);
 389
 390   /* Remove from vector. We do this by swapping node with the last element
 391      of the vector.  */
 392   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 393   if (last_node != node)
 394     {
 395       last_slot = pointer_map_contains (set->map, last_node);
 396       gcc_checking_assert (last_slot && *last_slot);
 397       *last_slot = (void *)(size_t) (index + 1);
 398
 399       /* Move the last element to the original spot of NODE.  */
 400       VEC_replace (cgraph_node_ptr, set->nodes, index, last_node);
 401     }
 402
 403   /* Remove element from hash table.  */
 404   *slot = NULL;
 405 }
 406
 407
 408 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 409    is returned if NODE is not in SET.  */
 410
 411 cgraph_node_set_iterator
 412 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 413 {
 414   void **slot;
 415   cgraph_node_set_iterator csi;
 416
 417   slot = pointer_map_contains (set->map, node);
 418   if (slot == NULL || !*slot)
 419     csi.index = (unsigned) ~0;
 420   else
 421     csi.index = (size_t)*slot - 1;
 422   csi.set = set;
 423
 424   return csi;
 425 }
 426
 427
 428 /* Dump content of SET to file F.  */
 429
 430 void
 431 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 432 {
 433   cgraph_node_set_iterator iter;
 434
 435   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 436     {
 437       struct cgraph_node *node = csi_node (iter);
 438       fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
 439     }
 440   fprintf (f, "\n");
 441 }
 442
 443
 444 /* Dump content of SET to stderr.  */
 445
 446 DEBUG_FUNCTION void
 447 debug_cgraph_node_set (cgraph_node_set set)
 448 {
 449   dump_cgraph_node_set (stderr, set);
 450 }
 451
 452
 453 /* Free varpool node set.  */
 454
 455 void
 456 free_cgraph_node_set (cgraph_node_set set)
 457 {
 458   VEC_free (cgraph_node_ptr, heap, set->nodes);
 459   pointer_map_destroy (set->map);
 460   free (set);
 461 }
 462
 463
 464 /* Create a new varpool node set.  */
 465
 466 varpool_node_set
 467 varpool_node_set_new (void)
 468 {
 469   varpool_node_set new_node_set;
 470
 471   new_node_set = XCNEW (struct varpool_node_set_def);
 472   new_node_set->map = pointer_map_create ();
 473   new_node_set->nodes = NULL;
 474   return new_node_set;
 475 }
 476
 477
 478 /* Add varpool_node NODE to varpool_node_set SET.  */
 479
 480 void
 481 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
 482 {
 483   void **slot;
 484
 485   slot = pointer_map_insert (set->map, node);
 486
 487   if (*slot)
 488     {
 489       int index = (size_t) *slot - 1;
 490       gcc_checking_assert ((VEC_index (varpool_node_ptr, set->nodes, index)
 491                            == node));
 492       return;
 493     }
 494
 495   *slot = (void *)(size_t) (VEC_length (varpool_node_ptr, set->nodes) + 1);
 496
 497   /* Insert into node vector.  */
 498   VEC_safe_push (varpool_node_ptr, heap, set->nodes, node);
 499 }
 500
 501
 502 /* Remove varpool_node NODE from varpool_node_set SET.  */
 503
 504 void
 505 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
 506 {
 507   void **slot, **last_slot;
 508   int index;
 509   struct varpool_node *last_node;
 510
 511   slot = pointer_map_contains (set->map, node);
 512   if (slot == NULL || !*slot)
 513     return;
 514
 515   index = (size_t) *slot - 1;
 516   gcc_checking_assert (VEC_index (varpool_node_ptr, set->nodes, index)
 517                        == node);
 518
 519   /* Remove from vector. We do this by swapping node with the last element
 520      of the vector.  */
 521   last_node = VEC_pop (varpool_node_ptr, set->nodes);
 522   if (last_node != node)
 523     {
 524       last_slot = pointer_map_contains (set->map, last_node);
 525       gcc_checking_assert (last_slot && *last_slot);
 526       *last_slot = (void *)(size_t) (index + 1);
 527
 528       /* Move the last element to the original spot of NODE.  */
 529       VEC_replace (varpool_node_ptr, set->nodes, index, last_node);
 530     }
 531
 532   /* Remove element from hash table.  */
 533   *slot = NULL;
 534 }
 535
 536
 537 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 538    is returned if NODE is not in SET.  */
 539
 540 varpool_node_set_iterator
 541 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
 542 {
 543   void **slot;
 544   varpool_node_set_iterator vsi;
 545
 546   slot = pointer_map_contains (set->map, node);
 547   if (slot == NULL || !*slot)
 548     vsi.index = (unsigned) ~0;
 549   else
 550     vsi.index = (size_t)*slot - 1;
 551   vsi.set = set;
 552
 553   return vsi;
 554 }
 555
 556
 557 /* Dump content of SET to file F.  */
 558
 559 void
 560 dump_varpool_node_set (FILE *f, varpool_node_set set)
 561 {
 562   varpool_node_set_iterator iter;
 563
 564   for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
 565     {
 566       struct varpool_node *node = vsi_node (iter);
 567       fprintf (f, " %s", varpool_node_name (node));
 568     }
 569   fprintf (f, "\n");
 570 }
 571
 572
 573 /* Free varpool node set.  */
 574
 575 void
 576 free_varpool_node_set (varpool_node_set set)
 577 {
 578   VEC_free (varpool_node_ptr, heap, set->nodes);
 579   pointer_map_destroy (set->map);
 580   free (set);
 581 }
 582
 583
 584 /* Dump content of SET to stderr.  */
 585
 586 DEBUG_FUNCTION void
 587 debug_varpool_node_set (varpool_node_set set)
 588 {
 589   dump_varpool_node_set (stderr, set);
 590 }