1 /* Utilities for ipa analysis.
2 Copyright (C) 2005 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-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
49 void
ipa_utils_print_order(FILE * out,const char * note,struct cgraph_node ** order,int count)50 ipa_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
65 struct 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 cgraph_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
85 static void
searchc(struct searchc_env * env,struct cgraph_node * v)86 searchc (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
157 int
ipa_utils_reduced_inorder(struct cgraph_node ** order,bool reduce,bool allow_overwritable)158 ipa_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
212 tree
get_base_var(tree t)213 get_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