Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssanames.c @ 63:b7f97abdc517 gcc-4.6-20100522
update gcc from gcc-4.5.0 to gcc-4.6
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 24 May 2010 12:47:05 +0900 |
| parents | 77e2b8dfacca |
| children | f6334be47118 |
| rev | line source |
|---|---|
| 0 | 1 /* Generic routines for manipulating SSA_NAME expressions |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 Free Software Foundation, Inc. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
4 |
| 0 | 5 This file is part of GCC. |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
6 |
| 0 | 7 GCC is free software; you can redistribute it and/or modify |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 3, or (at your option) | |
| 10 any later version. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
11 |
| 0 | 12 GCC is distributed in the hope that it will be useful, |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
16 |
| 0 | 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-pass.h" | |
| 28 | |
| 29 /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, | |
| 30 many of which may be thrown away shortly after their creation if jumps | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
31 were threaded through PHI nodes. |
| 0 | 32 |
| 33 While our garbage collection mechanisms will handle this situation, it | |
| 34 is extremely wasteful to create nodes and throw them away, especially | |
| 35 when the nodes can be reused. | |
| 36 | |
| 37 For PR 8361, we can significantly reduce the number of nodes allocated | |
| 38 and thus the total amount of memory allocated by managing SSA_NAMEs a | |
| 39 little. This additionally helps reduce the amount of work done by the | |
| 40 garbage collector. Similar results have been seen on a wider variety | |
| 41 of tests (such as the compiler itself). | |
| 42 | |
| 43 Right now we maintain our free list on a per-function basis. It may | |
| 44 or may not make sense to maintain the free list for the duration of | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
45 a compilation unit. |
| 0 | 46 |
| 47 External code should rely solely upon HIGHEST_SSA_VERSION and the | |
| 48 externally defined functions. External code should not know about | |
| 49 the details of the free list management. | |
| 50 | |
| 51 External code should also not assume the version number on nodes is | |
| 52 monotonically increasing. We reuse the version number when we | |
| 53 reuse an SSA_NAME expression. This helps keep arrays and bitmaps | |
| 54 more compact. | |
| 55 | |
| 56 We could also use a zone allocator for these objects since they have | |
| 57 a very well defined lifetime. If someone wants to experiment with that | |
| 58 this is the place to try it. */ | |
| 59 | |
| 60 /* Version numbers with special meanings. We start allocating new version | |
| 61 numbers after the special ones. */ | |
| 62 #define UNUSED_NAME_VERSION 0 | |
| 63 | |
| 64 #ifdef GATHER_STATISTICS | |
| 65 unsigned int ssa_name_nodes_reused; | |
| 66 unsigned int ssa_name_nodes_created; | |
| 67 #endif | |
| 68 | |
| 69 /* Initialize management of SSA_NAMEs to default SIZE. If SIZE is | |
| 70 zero use default. */ | |
| 71 | |
| 72 void | |
| 73 init_ssanames (struct function *fn, int size) | |
| 74 { | |
| 75 if (size < 50) | |
| 76 size = 50; | |
| 77 | |
| 78 SSANAMES (fn) = VEC_alloc (tree, gc, size); | |
| 79 | |
| 80 /* Version 0 is special, so reserve the first slot in the table. Though | |
| 81 currently unused, we may use version 0 in alias analysis as part of | |
| 82 the heuristics used to group aliases when the alias sets are too | |
| 83 large. | |
| 84 | |
| 85 We use VEC_quick_push here because we know that SSA_NAMES has at | |
| 86 least 50 elements reserved in it. */ | |
| 87 VEC_quick_push (tree, SSANAMES (fn), NULL_TREE); | |
| 88 FREE_SSANAMES (fn) = NULL; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
89 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
90 SYMS_TO_RENAME (fn) = BITMAP_GGC_ALLOC (); |
| 0 | 91 } |
| 92 | |
| 93 /* Finalize management of SSA_NAMEs. */ | |
| 94 | |
| 95 void | |
| 96 fini_ssanames (void) | |
| 97 { | |
| 98 VEC_free (tree, gc, SSANAMES (cfun)); | |
| 99 FREE_SSANAMES (cfun) = NULL; | |
| 100 } | |
| 101 | |
| 102 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ | |
| 103 | |
| 104 #ifdef GATHER_STATISTICS | |
| 105 void | |
| 106 ssanames_print_statistics (void) | |
| 107 { | |
| 108 fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); | |
| 109 fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); | |
| 110 } | |
| 111 #endif | |
| 112 | |
| 113 /* Return an SSA_NAME node for variable VAR defined in statement STMT | |
| 114 in function FN. STMT may be an empty statement for artificial | |
| 115 references (e.g., default definitions created when a variable is | |
| 116 used without a preceding definition). */ | |
| 117 | |
| 118 tree | |
| 119 make_ssa_name_fn (struct function *fn, tree var, gimple stmt) | |
| 120 { | |
| 121 tree t; | |
| 122 use_operand_p imm; | |
| 123 | |
| 124 gcc_assert (DECL_P (var)); | |
| 125 | |
| 126 /* If our free list has an element, then use it. */ | |
| 127 if (FREE_SSANAMES (fn)) | |
| 128 { | |
| 129 t = FREE_SSANAMES (fn); | |
| 130 FREE_SSANAMES (fn) = TREE_CHAIN (FREE_SSANAMES (fn)); | |
| 131 #ifdef GATHER_STATISTICS | |
| 132 ssa_name_nodes_reused++; | |
| 133 #endif | |
| 134 | |
| 135 /* The node was cleared out when we put it on the free list, so | |
| 136 there is no need to do so again here. */ | |
| 137 gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL); | |
| 138 VEC_replace (tree, SSANAMES (fn), SSA_NAME_VERSION (t), t); | |
| 139 } | |
| 140 else | |
| 141 { | |
| 142 t = make_node (SSA_NAME); | |
| 143 SSA_NAME_VERSION (t) = VEC_length (tree, SSANAMES (fn)); | |
| 144 VEC_safe_push (tree, gc, SSANAMES (fn), t); | |
| 145 #ifdef GATHER_STATISTICS | |
| 146 ssa_name_nodes_created++; | |
| 147 #endif | |
| 148 } | |
| 149 | |
| 150 TREE_TYPE (t) = TREE_TYPE (var); | |
| 151 SSA_NAME_VAR (t) = var; | |
| 152 SSA_NAME_DEF_STMT (t) = stmt; | |
| 153 SSA_NAME_PTR_INFO (t) = NULL; | |
| 154 SSA_NAME_IN_FREE_LIST (t) = 0; | |
| 155 SSA_NAME_IS_DEFAULT_DEF (t) = 0; | |
| 156 imm = &(SSA_NAME_IMM_USE_NODE (t)); | |
| 157 imm->use = NULL; | |
| 158 imm->prev = imm; | |
| 159 imm->next = imm; | |
| 160 imm->loc.ssa_name = t; | |
| 161 | |
| 162 return t; | |
| 163 } | |
| 164 | |
| 165 | |
| 166 /* We no longer need the SSA_NAME expression VAR, release it so that | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
167 it may be reused. |
| 0 | 168 |
| 169 Note it is assumed that no calls to make_ssa_name will be made | |
| 170 until all uses of the ssa name are released and that the only | |
| 171 use of the SSA_NAME expression is to check its SSA_NAME_VAR. All | |
| 172 other fields must be assumed clobbered. */ | |
| 173 | |
| 174 void | |
| 175 release_ssa_name (tree var) | |
| 176 { | |
| 177 if (!var) | |
| 178 return; | |
| 179 | |
| 180 /* Never release the default definition for a symbol. It's a | |
| 181 special SSA name that should always exist once it's created. */ | |
| 182 if (SSA_NAME_IS_DEFAULT_DEF (var)) | |
| 183 return; | |
| 184 | |
| 185 /* If VAR has been registered for SSA updating, don't remove it. | |
| 186 After update_ssa has run, the name will be released. */ | |
| 187 if (name_registered_for_update_p (var)) | |
| 188 { | |
| 189 release_ssa_name_after_update_ssa (var); | |
| 190 return; | |
| 191 } | |
| 192 | |
| 193 /* release_ssa_name can be called multiple times on a single SSA_NAME. | |
| 194 However, it should only end up on our free list one time. We | |
| 195 keep a status bit in the SSA_NAME node itself to indicate it has | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
196 been put on the free list. |
| 0 | 197 |
| 198 Note that once on the freelist you can not reference the SSA_NAME's | |
| 199 defining statement. */ | |
| 200 if (! SSA_NAME_IN_FREE_LIST (var)) | |
| 201 { | |
| 202 tree saved_ssa_name_var = SSA_NAME_VAR (var); | |
| 203 int saved_ssa_name_version = SSA_NAME_VERSION (var); | |
| 204 use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); | |
| 205 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 if (MAY_HAVE_DEBUG_STMTS) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
207 insert_debug_temp_for_var_def (NULL, var); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
208 |
| 0 | 209 #ifdef ENABLE_CHECKING |
| 210 verify_imm_links (stderr, var); | |
| 211 #endif | |
| 212 while (imm->next != imm) | |
| 213 delink_imm_use (imm->next); | |
| 214 | |
| 215 VEC_replace (tree, SSANAMES (cfun), | |
| 216 SSA_NAME_VERSION (var), NULL_TREE); | |
| 217 memset (var, 0, tree_size (var)); | |
| 218 | |
| 219 imm->prev = imm; | |
| 220 imm->next = imm; | |
| 221 imm->loc.ssa_name = var; | |
| 222 | |
| 223 /* First put back the right tree node so that the tree checking | |
| 224 macros do not complain. */ | |
| 225 TREE_SET_CODE (var, SSA_NAME); | |
| 226 | |
| 227 /* Restore the version number. */ | |
| 228 SSA_NAME_VERSION (var) = saved_ssa_name_version; | |
| 229 | |
| 230 /* Hopefully this can go away once we have the new incremental | |
| 231 SSA updating code installed. */ | |
| 232 SSA_NAME_VAR (var) = saved_ssa_name_var; | |
| 233 | |
| 234 /* Note this SSA_NAME is now in the first list. */ | |
| 235 SSA_NAME_IN_FREE_LIST (var) = 1; | |
| 236 | |
| 237 /* And finally link it into the free list. */ | |
| 238 TREE_CHAIN (var) = FREE_SSANAMES (cfun); | |
| 239 FREE_SSANAMES (cfun) = var; | |
| 240 } | |
| 241 } | |
| 242 | |
| 243 /* Creates a duplicate of a ssa name NAME defined in statement STMT. */ | |
| 244 | |
| 245 tree | |
| 246 duplicate_ssa_name (tree name, gimple stmt) | |
| 247 { | |
| 248 tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt); | |
| 249 struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); | |
| 250 | |
| 251 if (old_ptr_info) | |
| 252 duplicate_ssa_name_ptr_info (new_name, old_ptr_info); | |
| 253 | |
| 254 return new_name; | |
| 255 } | |
| 256 | |
| 257 | |
| 258 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by | |
| 259 the SSA name NAME. */ | |
| 260 | |
| 261 void | |
| 262 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) | |
| 263 { | |
| 264 struct ptr_info_def *new_ptr_info; | |
| 265 | |
| 266 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); | |
| 267 gcc_assert (!SSA_NAME_PTR_INFO (name)); | |
| 268 | |
| 269 if (!ptr_info) | |
| 270 return; | |
| 271 | |
| 272 new_ptr_info = GGC_NEW (struct ptr_info_def); | |
| 273 *new_ptr_info = *ptr_info; | |
| 274 | |
| 275 SSA_NAME_PTR_INFO (name) = new_ptr_info; | |
| 276 } | |
| 277 | |
| 278 | |
| 279 /* Release all the SSA_NAMEs created by STMT. */ | |
| 280 | |
| 281 void | |
| 282 release_defs (gimple stmt) | |
| 283 { | |
| 284 tree def; | |
| 285 ssa_op_iter iter; | |
| 286 | |
| 287 /* Make sure that we are in SSA. Otherwise, operand cache may point | |
| 288 to garbage. */ | |
| 289 gcc_assert (gimple_in_ssa_p (cfun)); | |
| 290 | |
| 291 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) | |
| 292 if (TREE_CODE (def) == SSA_NAME) | |
| 293 release_ssa_name (def); | |
| 294 } | |
| 295 | |
| 296 | |
| 297 /* Replace the symbol associated with SSA_NAME with SYM. */ | |
| 298 | |
| 299 void | |
| 300 replace_ssa_name_symbol (tree ssa_name, tree sym) | |
| 301 { | |
| 302 SSA_NAME_VAR (ssa_name) = sym; | |
| 303 TREE_TYPE (ssa_name) = TREE_TYPE (sym); | |
| 304 } | |
| 305 | |
| 306 /* Return SSA names that are unused to GGC memory. This is used to keep | |
| 307 footprint of compiler during interprocedural optimization. | |
| 308 As a side effect the SSA_NAME_VERSION number reuse is reduced | |
| 309 so this function should not be used too often. */ | |
| 310 static unsigned int | |
| 311 release_dead_ssa_names (void) | |
| 312 { | |
| 313 tree t, next; | |
| 314 int n = 0; | |
| 315 referenced_var_iterator rvi; | |
| 316 | |
| 317 /* Current defs point to various dead SSA names that in turn points to dead | |
| 318 statements so bunch of dead memory is held from releasing. */ | |
| 319 FOR_EACH_REFERENCED_VAR (t, rvi) | |
| 320 set_current_def (t, NULL); | |
| 321 /* Now release the freelist. */ | |
| 322 for (t = FREE_SSANAMES (cfun); t; t = next) | |
| 323 { | |
| 324 next = TREE_CHAIN (t); | |
| 325 /* Dangling pointers might make GGC to still see dead SSA names, so it is | |
| 326 important to unlink the list and avoid GGC from seeing all subsequent | |
| 327 SSA names. In longer run we want to have all dangling pointers here | |
| 328 removed (since they usually go through dead statements that consume | |
| 329 considerable amounts of memory). */ | |
| 330 TREE_CHAIN (t) = NULL_TREE; | |
| 331 n++; | |
| 332 } | |
| 333 FREE_SSANAMES (cfun) = NULL; | |
| 334 | |
| 335 /* Cgraph edges has been invalidated and point to dead statement. We need to | |
| 336 remove them now and will rebuild it before next IPA pass. */ | |
| 337 cgraph_node_remove_callees (cgraph_node (current_function_decl)); | |
| 338 | |
| 339 if (dump_file) | |
| 340 fprintf (dump_file, "Released %i names, %.2f%%\n", n, n * 100.0 / num_ssa_names); | |
| 341 return 0; | |
| 342 } | |
| 343 | |
| 344 struct gimple_opt_pass pass_release_ssa_names = | |
| 345 { | |
| 346 { | |
| 347 GIMPLE_PASS, | |
| 348 "release_ssa", /* name */ | |
| 349 NULL, /* gate */ | |
| 350 release_dead_ssa_names, /* execute */ | |
| 351 NULL, /* sub */ | |
| 352 NULL, /* next */ | |
| 353 0, /* static_pass_number */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
354 TV_NONE, /* tv_id */ |
| 0 | 355 PROP_ssa, /* properties_required */ |
| 356 0, /* properties_provided */ | |
| 357 0, /* properties_destroyed */ | |
| 358 0, /* todo_flags_start */ | |
| 359 TODO_dump_func /* todo_flags_finish */ | |
| 360 } | |
| 361 }; |