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_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    ipa_utils_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          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
 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                            bool (*ignore_edge) (struct cgraph_edge *))
 161 {
 162   struct cgraph_node *node;
 163   struct searchc_env env;
 164   splay_tree_node result;
 165   env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 166   env.stack_size = 0;
 167   env.result = order;
 168   env.order_pos = 0;
 169   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
 170   env.count = 1;
 171   env.reduce = reduce;
 172
 173   for (node = cgraph_nodes; node; node = node->next)
 174     {
 175       enum availability avail = cgraph_function_body_availability (node);
 176
 177       if (avail > AVAIL_OVERWRITABLE
 178           || (allow_overwritable
 179               && (avail == AVAIL_OVERWRITABLE)))
 180         {
 181           /* Reuse the info if it is already there.  */
 182           struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
 183           if (!info)
 184             info = XCNEW (struct ipa_dfs_info);
 185           info->new_node = true;
 186           info->on_stack = false;
 187           info->next_cycle = NULL;
 188           node->aux = info;
 189
 190           splay_tree_insert (env.nodes_marked_new,
 191                              (splay_tree_key)node->uid,
 192                              (splay_tree_value)node);
 193         }
 194       else
 195         node->aux = NULL;
 196     }
 197   result = splay_tree_min (env.nodes_marked_new);
 198   while (result)
 199     {
 200       node = (struct cgraph_node *)result->value;
 201       searchc (&env, node, ignore_edge);
 202       result = splay_tree_min (env.nodes_marked_new);
 203     }
 204   splay_tree_delete (env.nodes_marked_new);
 205   free (env.stack);
 206
 207   return env.order_pos;
 208 }
 209
 210
 211 /* Given a memory reference T, will return the variable at the bottom
 212    of the access.  Unlike get_base_address, this will recurse thru
 213    INDIRECT_REFS.  */
 214
 215 tree
 216 get_base_var (tree 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          && TREE_CODE (t) != CONSTRUCTOR)
 224     {
 225       t = TREE_OPERAND (t, 0);
 226     }
 227   return t;
 228 }
 229