1 /* Generic routines for manipulating SSA_NAME expressions 2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 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. 11 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. 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-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 31 were threaded through PHI nodes. 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 45 a compilation unit. 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; 89 90 SYMS_TO_RENAME (fn) = BITMAP_GGC_ALLOC (); 91 } 92 93 /* Finalize management of SSA_NAMEs. */ 94 95 void 96 fini_ssanames (void) 97 { 98 VEC_free (tree, gc, SSANAMES (cfun)); 99 VEC_free (tree, gc, FREE_SSANAMES (cfun)); 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 (!VEC_empty (tree, FREE_SSANAMES (fn))) 128 { 129 t = VEC_pop (tree, FREE_SSANAMES (fn)); 130 #ifdef GATHER_STATISTICS 131 ssa_name_nodes_reused++; 132 #endif 133 134 /* The node was cleared out when we put it on the free list, so 135 there is no need to do so again here. */ 136 gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL); 137 VEC_replace (tree, SSANAMES (fn), SSA_NAME_VERSION (t), t); 138 } 139 else 140 { 141 t = make_node (SSA_NAME); 142 SSA_NAME_VERSION (t) = VEC_length (tree, SSANAMES (fn)); 143 VEC_safe_push (tree, gc, SSANAMES (fn), t); 144 #ifdef GATHER_STATISTICS 145 ssa_name_nodes_created++; 146 #endif 147 } 148 149 TREE_TYPE (t) = TREE_TYPE (var); 150 SSA_NAME_VAR (t) = var; 151 SSA_NAME_DEF_STMT (t) = stmt; 152 SSA_NAME_PTR_INFO (t) = NULL; 153 SSA_NAME_IN_FREE_LIST (t) = 0; 154 SSA_NAME_IS_DEFAULT_DEF (t) = 0; 155 imm = &(SSA_NAME_IMM_USE_NODE (t)); 156 imm->use = NULL; 157 imm->prev = imm; 158 imm->next = imm; 159 imm->loc.ssa_name = t; 160 161 return t; 162 } 163 164 165 /* We no longer need the SSA_NAME expression VAR, release it so that 166 it may be reused. 167 168 Note it is assumed that no calls to make_ssa_name will be made 169 until all uses of the ssa name are released and that the only 170 use of the SSA_NAME expression is to check its SSA_NAME_VAR. All 171 other fields must be assumed clobbered. */ 172 173 void 174 release_ssa_name (tree var) 175 { 176 if (!var) 177 return; 178 179 /* Never release the default definition for a symbol. It's a 180 special SSA name that should always exist once it's created. */ 181 if (SSA_NAME_IS_DEFAULT_DEF (var)) 182 return; 183 184 /* If VAR has been registered for SSA updating, don't remove it. 185 After update_ssa has run, the name will be released. */ 186 if (name_registered_for_update_p (var)) 187 { 188 release_ssa_name_after_update_ssa (var); 189 return; 190 } 191 192 /* release_ssa_name can be called multiple times on a single SSA_NAME. 193 However, it should only end up on our free list one time. We 194 keep a status bit in the SSA_NAME node itself to indicate it has 195 been put on the free list. 196 197 Note that once on the freelist you can not reference the SSA_NAME's 198 defining statement. */ 199 if (! SSA_NAME_IN_FREE_LIST (var)) 200 { 201 tree saved_ssa_name_var = SSA_NAME_VAR (var); 202 int saved_ssa_name_version = SSA_NAME_VERSION (var); 203 use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); 204 205 if (MAY_HAVE_DEBUG_STMTS) 206 insert_debug_temp_for_var_def (NULL, var); 207 208 #ifdef ENABLE_CHECKING 209 verify_imm_links (stderr, var); 210 #endif 211 while (imm->next != imm) 212 delink_imm_use (imm->next); 213 214 VEC_replace (tree, SSANAMES (cfun), 215 SSA_NAME_VERSION (var), NULL_TREE); 216 memset (var, 0, tree_size (var)); 217 218 imm->prev = imm; 219 imm->next = imm; 220 imm->loc.ssa_name = var; 221 222 /* First put back the right tree node so that the tree checking 223 macros do not complain. */ 224 TREE_SET_CODE (var, SSA_NAME); 225 226 /* Restore the version number. */ 227 SSA_NAME_VERSION (var) = saved_ssa_name_version; 228 229 /* Hopefully this can go away once we have the new incremental 230 SSA updating code installed. */ 231 SSA_NAME_VAR (var) = saved_ssa_name_var; 232 233 /* Note this SSA_NAME is now in the first list. */ 234 SSA_NAME_IN_FREE_LIST (var) = 1; 235 236 /* And finally put it on the free list. */ 237 VEC_safe_push (tree, gc, FREE_SSANAMES (cfun), var); 238 } 239 } 240 241 242 /* Return the alias information associated with pointer T. It creates a 243 new instance if none existed. */ 244 245 struct ptr_info_def * 246 get_ptr_info (tree t) 247 { 248 struct ptr_info_def *pi; 249 250 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); 251 252 pi = SSA_NAME_PTR_INFO (t); 253 if (pi == NULL) 254 { 255 pi = ggc_alloc_cleared_ptr_info_def (); 256 pt_solution_reset (&pi->pt); 257 pi->align = 1; 258 pi->misalign = 0; 259 SSA_NAME_PTR_INFO (t) = pi; 260 } 261 262 return pi; 263 } 264 265 /* Creates a duplicate of the ptr_info_def at PTR_INFO for use by 266 the SSA name NAME. */ 267 268 void 269 duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) 270 { 271 struct ptr_info_def *new_ptr_info; 272 273 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); 274 gcc_assert (!SSA_NAME_PTR_INFO (name)); 275 276 if (!ptr_info) 277 return; 278 279 new_ptr_info = ggc_alloc_ptr_info_def (); 280 *new_ptr_info = *ptr_info; 281 282 SSA_NAME_PTR_INFO (name) = new_ptr_info; 283 } 284 285 286 /* Creates a duplicate of a ssa name NAME tobe defined by statement STMT. */ 287 288 tree 289 duplicate_ssa_name (tree name, gimple stmt) 290 { 291 tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt); 292 struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); 293 294 if (old_ptr_info) 295 duplicate_ssa_name_ptr_info (new_name, old_ptr_info); 296 297 return new_name; 298 } 299 300 301 /* Release all the SSA_NAMEs created by STMT. */ 302 303 void 304 release_defs (gimple stmt) 305 { 306 tree def; 307 ssa_op_iter iter; 308 309 /* Make sure that we are in SSA. Otherwise, operand cache may point 310 to garbage. */ 311 gcc_assert (gimple_in_ssa_p (cfun)); 312 313 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 314 if (TREE_CODE (def) == SSA_NAME) 315 release_ssa_name (def); 316 } 317 318 319 /* Replace the symbol associated with SSA_NAME with SYM. */ 320 321 void 322 replace_ssa_name_symbol (tree ssa_name, tree sym) 323 { 324 SSA_NAME_VAR (ssa_name) = sym; 325 TREE_TYPE (ssa_name) = TREE_TYPE (sym); 326 } 327 328 /* Return SSA names that are unused to GGC memory. This is used to keep 329 footprint of compiler during interprocedural optimization. 330 As a side effect the SSA_NAME_VERSION number reuse is reduced 331 so this function should not be used too often. */ 332 static unsigned int 333 release_dead_ssa_names (void) 334 { 335 tree t; 336 int n = VEC_length (tree, FREE_SSANAMES (cfun)); 337 referenced_var_iterator rvi; 338 339 /* Current defs point to various dead SSA names that in turn point to 340 eventually dead variables so a bunch of memory is held live. */ 341 FOR_EACH_REFERENCED_VAR (cfun, t, rvi) 342 set_current_def (t, NULL); 343 /* Now release the freelist. */ 344 VEC_free (tree, gc, FREE_SSANAMES (cfun)); 345 FREE_SSANAMES (cfun) = NULL; 346 347 statistics_counter_event (cfun, "SSA names released", n); 348 if (dump_file) 349 fprintf (dump_file, "Released %i names, %.2f%%\n", 350 n, n * 100.0 / num_ssa_names); 351 return 0; 352 } 353 354 struct gimple_opt_pass pass_release_ssa_names = 355 { 356 { 357 GIMPLE_PASS, 358 "release_ssa", /* name */ 359 NULL, /* gate */ 360 release_dead_ssa_names, /* execute */ 361 NULL, /* sub */ 362 NULL, /* next */ 363 0, /* static_pass_number */ 364 TV_TREE_SSA_OTHER, /* tv_id */ 365 PROP_ssa, /* properties_required */ 366 0, /* properties_provided */ 367 0, /* properties_destroyed */ 368 0, /* todo_flags_start */ 369 0 /* todo_flags_finish */ 370 } 371 }; 372