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