Daily bump.
[official-gcc.git] / gcc / ipa-utils.c
blob2a9562935c3f52aa6ddaf769f380bf1597bcff3e
1 /* Utilities for ipa analysis.
2 Copyright (C) 2005, 2007 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
5 This file is part of GCC.
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.
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.
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/>. */
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"
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. */
47 void
48 ipa_utils_print_order (FILE* out,
49 const char * note,
50 struct cgraph_node** order,
51 int count)
53 int i;
54 fprintf (out, "\n\n ordered call graph: %s\n", note);
56 for (i = count - 1; i >= 0; i--)
57 dump_cgraph_node(dump_file, order[i]);
58 fprintf (out, "\n");
59 fflush(out);
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;
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. */
83 static void
84 searchc (struct searchc_env* env, struct cgraph_node *v)
86 struct cgraph_edge *edge;
87 struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
89 /* mark node as old */
90 v_info->new_node = false;
91 splay_tree_remove (env->nodes_marked_new, v->uid);
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;
99 for (edge = v->callees; edge; edge = edge->next_callee)
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)
108 w_info = (struct ipa_dfs_info *) w->aux;
109 if (w_info->new_node)
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;
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;
126 if (v_info->low_link == v_info->dfn_number)
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 = (struct ipa_dfs_info *) x->aux;
134 x_info->on_stack = false;
136 if (env->reduce)
138 x_info->next_cycle = last;
139 last = x;
141 else
142 env->result[env->order_pos++] = x;
144 while (v != x);
145 if (env->reduce)
146 env->result[env->order_pos++] = v;
150 /* Topsort the call graph by caller relation. Put the result in ORDER.
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. */
156 ipa_utils_reduced_inorder (struct cgraph_node **order,
157 bool reduce, bool allow_overwritable)
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;
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))))
177 /* Reuse the info if it is already there. */
178 struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
179 if (!info)
180 info = XCNEW (struct ipa_dfs_info);
181 info->new_node = true;
182 info->on_stack = false;
183 info->next_cycle = NULL;
184 node->aux = info;
186 splay_tree_insert (env.nodes_marked_new,
187 (splay_tree_key)node->uid,
188 (splay_tree_value)node);
190 else
191 node->aux = NULL;
192 result = splay_tree_min (env.nodes_marked_new);
193 while (result)
195 node = (struct cgraph_node *)result->value;
196 searchc (&env, node);
197 result = splay_tree_min (env.nodes_marked_new);
199 splay_tree_delete (env.nodes_marked_new);
200 free (env.stack);
202 return env.order_pos;
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. */
210 tree
211 get_base_var (tree t)
213 if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
214 return t;
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)
222 t = TREE_OPERAND (t, 0);
224 return t;