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 "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 {
  86   struct cgraph_edge *edge;
  87   struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
  88
  89   /* mark node as old */
  90   v_info->new_node = 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
 104       if (w->aux && cgraph_function_body_availability (edge->callee) > AVAIL_OVERWRITABLE)
 105         {
 106           w_info = (struct ipa_dfs_info *) w->aux;
 107           if (w_info->new_node)
 108             {
 109               searchc (env, w);
 110               v_info->low_link =
 111                 (v_info->low_link < w_info->low_link) ?
 112                 v_info->low_link : w_info->low_link;
 113             }
 114           else
 115             if ((w_info->dfn_number < v_info->dfn_number)
 116                 && (w_info->on_stack))
 117               v_info->low_link =
 118                 (w_info->dfn_number < v_info->low_link) ?
 119                 w_info->dfn_number : v_info->low_link;
 120         }
 121     }
 122
 123
 124   if (v_info->low_link == v_info->dfn_number)
 125     {
 126       struct cgraph_node *last = NULL;
 127       struct cgraph_node *x;
 128       struct ipa_dfs_info *x_info;
 129       do {
 130         x = env->stack[--(env->stack_size)];
 131         x_info = (struct ipa_dfs_info *) x->aux;
 132         x_info->on_stack = false;
 133
 134         if (env->reduce)
 135           {
 136             x_info->next_cycle = last;
 137             last = x;
 138           }
 139         else
 140           env->result[env->order_pos++] = x;
 141       }
 142       while (v != x);
 143       if (env->reduce)
 144         env->result[env->order_pos++] = v;
 145     }
 146 }
 147
 148 /* Topsort the call graph by caller relation.  Put the result in ORDER.
 149
 150    The REDUCE flag is true if you want the cycles reduced to single
 151    nodes.  Only consider nodes that have the output bit set. */
 152
 153 int
 154 ipa_utils_reduced_inorder (struct cgraph_node **order,
 155                            bool reduce, bool allow_overwritable)
 156 {
 157   struct cgraph_node *node;
 158   struct searchc_env env;
 159   splay_tree_node result;
 160   env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
 161   env.stack_size = 0;
 162   env.result = order;
 163   env.order_pos = 0;
 164   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
 165   env.count = 1;
 166   env.reduce = reduce;
 167
 168   for (node = cgraph_nodes; node; node = node->next)
 169     {
 170       enum availability avail = cgraph_function_body_availability (node);
 171
 172       if (avail > AVAIL_OVERWRITABLE
 173           || (allow_overwritable
 174               && (avail == AVAIL_OVERWRITABLE)))
 175         {
 176           /* Reuse the info if it is already there.  */
 177           struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
 178           if (!info)
 179             info = XCNEW (struct ipa_dfs_info);
 180           info->new_node = true;
 181           info->on_stack = false;
 182           info->next_cycle = NULL;
 183           node->aux = info;
 184
 185           splay_tree_insert (env.nodes_marked_new,
 186                              (splay_tree_key)node->uid,
 187                              (splay_tree_value)node);
 188         }
 189       else
 190         node->aux = NULL;
 191     }
 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