Mercurial > hg > CbC > CbC_gcc
annotate gcc/ipa-utils.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
| author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 22 Mar 2011 17:18:12 +0900 |
| parents | 77e2b8dfacca |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 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" | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
31 #include "splay-tree.h" |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
47 void |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
48 ipa_utils_print_order (FILE* out, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
49 const char * note, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
50 struct cgraph_node** order, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
51 int count) |
| 0 | 52 { |
| 53 int i; | |
| 54 fprintf (out, "\n\n ordered call graph: %s\n", note); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
55 |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
84 searchc (struct searchc_env* env, struct cgraph_node *v, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
85 bool (*ignore_edge) (struct cgraph_edge *)) |
| 0 | 86 { |
| 87 struct cgraph_edge *edge; | |
| 88 struct ipa_dfs_info *v_info = (struct ipa_dfs_info *) v->aux; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
89 |
| 0 | 90 /* mark node as old */ |
| 91 v_info->new_node = false; | |
| 92 splay_tree_remove (env->nodes_marked_new, v->uid); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
93 |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
99 |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
105 if (ignore_edge && ignore_edge (edge)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
106 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
107 |
| 0 | 108 if (w->aux && cgraph_function_body_availability (edge->callee) > AVAIL_OVERWRITABLE) |
| 109 { | |
| 110 w_info = (struct ipa_dfs_info *) w->aux; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
111 if (w_info->new_node) |
| 0 | 112 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 searchc (env, w, ignore_edge); |
| 0 | 114 v_info->low_link = |
| 115 (v_info->low_link < w_info->low_link) ? | |
| 116 v_info->low_link : w_info->low_link; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
117 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
118 else |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
119 if ((w_info->dfn_number < v_info->dfn_number) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
120 && (w_info->on_stack)) |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
128 if (v_info->low_link == v_info->dfn_number) |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
137 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
138 if (env->reduce) |
| 0 | 139 { |
| 140 x_info->next_cycle = last; | |
| 141 last = x; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
142 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
143 else |
| 0 | 144 env->result[env->order_pos++] = x; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
145 } |
| 0 | 146 while (v != x); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
147 if (env->reduce) |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
158 ipa_utils_reduced_inorder (struct cgraph_node **order, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
159 bool reduce, bool allow_overwritable, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
160 bool (*ignore_edge) (struct cgraph_edge *)) |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
172 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
173 for (node = cgraph_nodes; node; node = node->next) |
| 0 | 174 { |
| 175 enum availability avail = cgraph_function_body_availability (node); | |
| 176 | |
| 177 if (avail > AVAIL_OVERWRITABLE | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
178 || (allow_overwritable |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
189 |
| 0 | 190 splay_tree_insert (env.nodes_marked_new, |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
191 (splay_tree_key)node->uid, |
| 0 | 192 (splay_tree_value)node); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
193 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
194 else |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
201 searchc (&env, node, ignore_edge); |
| 0 | 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 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
218 while (!SSA_VAR_P (t) |
| 0 | 219 && (!CONSTANT_CLASS_P (t)) |
| 220 && TREE_CODE (t) != LABEL_DECL | |
| 221 && TREE_CODE (t) != FUNCTION_DECL | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
222 && TREE_CODE (t) != CONST_DECL |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
223 && TREE_CODE (t) != CONSTRUCTOR) |
| 0 | 224 { |
| 225 t = TREE_OPERAND (t, 0); | |
| 226 } | |
| 227 return t; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 } |
| 0 | 229 |