|
0
|
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
|
