Mercurial > hg > CbC > CbC_gcc

comparison gcc/ipa-utils.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
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 "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
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