gcc/ipa-utils.c

   1 /* Utilities for ipa analysis.
   2    Copyright (C) 2005 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 2, 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 COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.
  21 */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "tm.h"
  27 #include "tree.h"
  28 #include "tree-flow.h"
  29 #include "tree-inline.h"
  30 #include "tree-pass.h"
  31 #include "langhooks.h"
  32 #include "pointer-set.h"
  33 #include "ggc.h"
  34 #include "ipa-utils.h"
  35 #include "ipa-reference.h"
  36 #include "c-common.h"
  37 #include "tree-gimple.h"
  38 #include "cgraph.h"
  39 #include "output.h"
  40 #include "flags.h"
  41 #include "timevar.h"
  42 #include "diagnostic.h"
  43 #include "langhooks.h"
  44
  45 /* Debugging function for postorder and inorder code. NOTE is a string
  46    that is printed before the nodes are printed.  ORDER is an array of
  47    cgraph_nodes that has COUNT useful nodes in it.  */
  48
  49 void
  50 ipa_utils_print_order (FILE* out,
  51                        const char * note,
  52                        struct cgraph_node** order,
  53                        int count)
  54 {
  55   int i;
  56   fprintf (out, "\n\n ordered call graph: %s\n", note);
  57
  58   for (i = count - 1; i >= 0; i--)
  59     dump_cgraph_node(dump_file, order[i]);
  60   fprintf (out, "\n");
  61   fflush(out);
  62 }
  63
  64 \f
  65 struct searchc_env {
  66   struct cgraph_node **stack;
  67   int stack_size;
  68   struct cgraph_node **result;
  69   int order_pos;
  70   splay_tree nodes_marked_new;
  71   bool reduce;
  72   int count;
  73 };
  74
  75 /* This is an implementation of Tarjan's strongly connected region
  76    finder as reprinted in Aho Hopcraft and Ullman's The Design and
  77    Analysis of Computer Programs (1975) pages 192-193.  This version
  78    has been customized for cgraph_nodes.  The env parameter is because
  79    it is recursive and there are no nested functions here.  This
  80    function should only be called from itself or
  81    cgraph_reduced_inorder.  ENV is a stack env and would be
  82    unnecessary if C had nested functions.  V is the node to start
  83    searching from.  */
  84
  85 static void
  86 searchc (struct searchc_env* env, struct cgraph_node *v)
  87 {
  88   struct cgraph_edge *edge;
  89   struct ipa_dfs_info *v_info = v->aux;
  90
  91   /* mark node as old */
  92   v_info->new = 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       struct cgraph_node *w = edge->callee;
 105       /* Bypass the clones and only look at the master node.  Skip
 106          external and other bogus nodes.  */
 107       w = cgraph_master_clone (w);
 108       if (w && w->aux)
 109         {
 110           w_info = w->aux;
 111           if (w_info->new)
 112             {
 113               searchc (env, w);
 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 = 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
 155    nodes.  Only consider nodes that have the output bit set. */
 156
 157 int
 158 ipa_utils_reduced_inorder (struct cgraph_node **order,
 159                            bool reduce, bool allow_overwritable)
 160 {
 161   struct cgraph_node *node;
 162   struct searchc_env env;
 163   splay_tree_node result;
 164   env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 165   env.stack_size = 0;
 166   env.result = order;
 167   env.order_pos = 0;
 168   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
 169   env.count = 1;
 170   env.reduce = reduce;
 171
 172   for (node = cgraph_nodes; node; node = node->next)
 173     if ((node->analyzed)
 174         && (cgraph_is_master_clone (node)
 175          || (allow_overwritable
 176              && (cgraph_function_body_availability (node) ==
 177                  AVAIL_OVERWRITABLE))))
 178       {
 179         /* Reuse the info if it is already there.  */
 180         struct ipa_dfs_info *info = node->aux;
 181         if (!info)
 182           info = xcalloc (1, sizeof (struct ipa_dfs_info));
 183         info->new = true;
 184         info->on_stack = false;
 185         info->next_cycle = NULL;
 186         node->aux = info;
 187
 188         splay_tree_insert (env.nodes_marked_new,
 189                            (splay_tree_key)node->uid,
 190                            (splay_tree_value)node);
 191       }
 192     else
 193       node->aux = NULL;
 194   result = splay_tree_min (env.nodes_marked_new);
 195   while (result)
 196     {
 197       node = (struct cgraph_node *)result->value;
 198       searchc (&env, node);
 199       result = splay_tree_min (env.nodes_marked_new);
 200     }
 201   splay_tree_delete (env.nodes_marked_new);
 202   free (env.stack);
 203
 204   return env.order_pos;
 205 }
 206
 207
 208 /* Given a memory reference T, will return the variable at the bottom
 209    of the access.  Unlike get_base_address, this will recurse thru
 210    INDIRECT_REFS.  */
 211
 212 tree
 213 get_base_var (tree t)
 214 {
 215   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
 216     return t;
 217
 218   while (!SSA_VAR_P (t)
 219          && (!CONSTANT_CLASS_P (t))
 220          && TREE_CODE (t) != LABEL_DECL
 221          && TREE_CODE (t) != FUNCTION_DECL
 222          && TREE_CODE (t) != CONST_DECL)
 223     {
 224       t = TREE_OPERAND (t, 0);
 225     }
 226   return t;
 227 }
 228