gcc/ipa-utils.c

   1 /* Utilities for ipa analysis.
   2    Copyright (C) 2005, 2007 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 "ggc.h"
  32 #include "ipa-utils.h"
  33 #include "ipa-reference.h"
  34 #include "c-common.h"
  35 #include "tree-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_utils_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    cgraph_reduced_inorder.  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 {
  86   struct cgraph_edge *edge;
  87   struct ipa_dfs_info *v_info = v->aux;
  88
  89   /* mark node as old */
  90   v_info->new = false;
  91   splay_tree_remove (env->nodes_marked_new, v->uid);
  92
  93   v_info->dfn_number = env->count;
  94   v_info->low_link = env->count;
  95   env->count++;
  96   env->stack[(env->stack_size)++] = v;
  97   v_info->on_stack = true;
  98
  99   for (edge = v->callees; edge; edge = edge->next_callee)
 100     {
 101       struct ipa_dfs_info * w_info;
 102       struct cgraph_node *w = edge->callee;
 103       /* Bypass the clones and only look at the master node.  Skip
 104          external and other bogus nodes.  */
 105       w = cgraph_master_clone (w);
 106       if (w && w->aux)
 107         {
 108           w_info = w->aux;
 109           if (w_info->new)
 110             {
 111               searchc (env, w);
 112               v_info->low_link =
 113                 (v_info->low_link < w_info->low_link) ?
 114                 v_info->low_link : w_info->low_link;
 115             }
 116           else
 117             if ((w_info->dfn_number < v_info->dfn_number)
 118                 && (w_info->on_stack))
 119               v_info->low_link =
 120                 (w_info->dfn_number < v_info->low_link) ?
 121                 w_info->dfn_number : v_info->low_link;
 122         }
 123     }
 124
 125
 126   if (v_info->low_link == v_info->dfn_number)
 127     {
 128       struct cgraph_node *last = NULL;
 129       struct cgraph_node *x;
 130       struct ipa_dfs_info *x_info;
 131       do {
 132         x = env->stack[--(env->stack_size)];
 133         x_info = x->aux;
 134         x_info->on_stack = false;
 135
 136         if (env->reduce)
 137           {
 138             x_info->next_cycle = last;
 139             last = x;
 140           }
 141         else
 142           env->result[env->order_pos++] = x;
 143       }
 144       while (v != x);
 145       if (env->reduce)
 146         env->result[env->order_pos++] = v;
 147     }
 148 }
 149
 150 /* Topsort the call graph by caller relation.  Put the result in ORDER.
 151
 152    The REDUCE flag is true if you want the cycles reduced to single
 153    nodes.  Only consider nodes that have the output bit set. */
 154
 155 int
 156 ipa_utils_reduced_inorder (struct cgraph_node **order,
 157                            bool reduce, bool allow_overwritable)
 158 {
 159   struct cgraph_node *node;
 160   struct searchc_env env;
 161   splay_tree_node result;
 162   env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 163   env.stack_size = 0;
 164   env.result = order;
 165   env.order_pos = 0;
 166   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
 167   env.count = 1;
 168   env.reduce = reduce;
 169
 170   for (node = cgraph_nodes; node; node = node->next)
 171     if ((node->analyzed)
 172         && (cgraph_is_master_clone (node)
 173          || (allow_overwritable
 174              && (cgraph_function_body_availability (node) ==
 175                  AVAIL_OVERWRITABLE))))
 176       {
 177         /* Reuse the info if it is already there.  */
 178         struct ipa_dfs_info *info = node->aux;
 179         if (!info)
 180           info = xcalloc (1, sizeof (struct ipa_dfs_info));
 181         info->new = true;
 182         info->on_stack = false;
 183         info->next_cycle = NULL;
 184         node->aux = info;
 185
 186         splay_tree_insert (env.nodes_marked_new,
 187                            (splay_tree_key)node->uid,
 188                            (splay_tree_value)node);
 189       }
 190     else
 191       node->aux = NULL;
 192   result = splay_tree_min (env.nodes_marked_new);
 193   while (result)
 194     {
 195       node = (struct cgraph_node *)result->value;
 196       searchc (&env, node);
 197       result = splay_tree_min (env.nodes_marked_new);
 198     }
 199   splay_tree_delete (env.nodes_marked_new);
 200   free (env.stack);
 201
 202   return env.order_pos;
 203 }
 204
 205
 206 /* Given a memory reference T, will return the variable at the bottom
 207    of the access.  Unlike get_base_address, this will recurse thru
 208    INDIRECT_REFS.  */
 209
 210 tree
 211 get_base_var (tree t)
 212 {
 213   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
 214     return t;
 215
 216   while (!SSA_VAR_P (t)
 217          && (!CONSTANT_CLASS_P (t))
 218          && TREE_CODE (t) != LABEL_DECL
 219          && TREE_CODE (t) != FUNCTION_DECL
 220          && TREE_CODE (t) != CONST_DECL)
 221     {
 222       t = TREE_OPERAND (t, 0);
 223     }
 224   return t;
 225 }
 226