1/* Utilities for ipa analysis.
2   Copyright (C) 2005 Free Software Foundation, Inc.
3   Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-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
49void
50ipa_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
65struct 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   ipa_utils_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
85static void
86searchc (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
157int
158ipa_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
212tree
213get_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
229