OSDN Git Service

* ipa-reference.c: Do not include c-common.h, include splay-tree.h.
[pf3gnuchains/gcc-fork.git] / gcc / ipa-utils.c
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 "splay-tree.h"
32 #include "ggc.h"
33 #include "ipa-utils.h"
34 #include "ipa-reference.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 \f
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          bool (*ignore_edge) (struct cgraph_edge *))
86 {
87   struct cgraph_edge *edge;
88   struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux;
89   
90   /* mark node as old */
91   v_info->new_node = false;
92   splay_tree_remove (env->nodes_marked_new, v->uid);
93   
94   v_info->dfn_number = env->count;
95   v_info->low_link = env->count;
96   env->count++;
97   env->stack[(env->stack_size)++] = v;
98   v_info->on_stack = true;
99   
100   for (edge = v->callees; edge; edge = edge->next_callee)
101     {
102       struct ipa_dfs_info * w_info;
103       struct cgraph_node *w = edge->callee;
104
105       if (ignore_edge && ignore_edge (edge))
106         continue;
107
108       if (w->aux && cgraph_function_body_availability (edge->callee) > AVAIL_OVERWRITABLE)
109         {
110           w_info = (struct ipa_dfs_info *) w->aux;
111           if (w_info->new_node) 
112             {
113               searchc (env, w, ignore_edge);
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 = (struct ipa_dfs_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
158 ipa_utils_reduced_inorder (struct cgraph_node **order, 
159                            bool reduce, bool allow_overwritable,
160                            bool (*ignore_edge) (struct cgraph_edge *))
161 {
162   struct cgraph_node *node;
163   struct searchc_env env;
164   splay_tree_node result;
165   env.stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
166   env.stack_size = 0;
167   env.result = order;
168   env.order_pos = 0;
169   env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0);
170   env.count = 1;
171   env.reduce = reduce;
172   
173   for (node = cgraph_nodes; node; node = node->next) 
174     {
175       enum availability avail = cgraph_function_body_availability (node);
176
177       if (avail > AVAIL_OVERWRITABLE
178           || (allow_overwritable 
179               && (avail == AVAIL_OVERWRITABLE)))
180         {
181           /* Reuse the info if it is already there.  */
182           struct ipa_dfs_info *info = (struct ipa_dfs_info *) node->aux;
183           if (!info)
184             info = XCNEW (struct ipa_dfs_info);
185           info->new_node = true;
186           info->on_stack = false;
187           info->next_cycle = NULL;
188           node->aux = info;
189           
190           splay_tree_insert (env.nodes_marked_new,
191                              (splay_tree_key)node->uid, 
192                              (splay_tree_value)node);
193         } 
194       else 
195         node->aux = NULL;
196     }
197   result = splay_tree_min (env.nodes_marked_new);
198   while (result)
199     {
200       node = (struct cgraph_node *)result->value;
201       searchc (&env, node, ignore_edge);
202       result = splay_tree_min (env.nodes_marked_new);
203     }
204   splay_tree_delete (env.nodes_marked_new);
205   free (env.stack);
206
207   return env.order_pos;
208 }
209
210
211 /* Given a memory reference T, will return the variable at the bottom
212    of the access.  Unlike get_base_address, this will recurse thru
213    INDIRECT_REFS.  */
214
215 tree
216 get_base_var (tree t)
217 {
218   if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR))
219     return t;
220
221   while (!SSA_VAR_P (t) 
222          && (!CONSTANT_CLASS_P (t))
223          && TREE_CODE (t) != LABEL_DECL
224          && TREE_CODE (t) != FUNCTION_DECL
225          && TREE_CODE (t) != CONST_DECL
226          && TREE_CODE (t) != CONSTRUCTOR)
227     {
228       t = TREE_OPERAND (t, 0);
229     }
230   return t;
231
232