1132720Skan/* Generic routines for manipulating SSA_NAME expressions 2132720Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3132720Skan 4132720SkanThis file is part of GCC. 5132720Skan 6132720SkanGCC is free software; you can redistribute it and/or modify 7132720Skanit under the terms of the GNU General Public License as published by 8132720Skanthe Free Software Foundation; either version 2, or (at your option) 9132720Skanany later version. 10132720Skan 11132720SkanGCC is distributed in the hope that it will be useful, 12132720Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13132720SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14132720SkanGNU General Public License for more details. 15132720Skan 16132720SkanYou should have received a copy of the GNU General Public License 17132720Skanalong with GCC; see the file COPYING. If not, write to 18169691Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19132720SkanBoston, MA 02110-1301, USA. */ 20132720Skan 21132720Skan#include "config.h" 22132720Skan#include "system.h" 23132720Skan#include "coretypes.h" 24132720Skan#include "tm.h" 25132720Skan#include "tree.h" 26132720Skan#include "varray.h" 27132720Skan#include "ggc.h" 28132720Skan#include "tree-flow.h" 29132720Skan 30132720Skan/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, 31132720Skan many of which may be thrown away shortly after their creation if jumps 32132720Skan were threaded through PHI nodes. 33132720Skan 34132720Skan While our garbage collection mechanisms will handle this situation, it 35132720Skan is extremely wasteful to create nodes and throw them away, especially 36169691Skan when the nodes can be reused. 37169691Skan 38169691Skan For PR 8361, we can significantly reduce the number of nodes allocated 39132720Skan and thus the total amount of memory allocated by managing SSA_NAMEs a 40132720Skan little. This additionally helps reduce the amount of work done by the 41132720Skan garbage collector. Similar results have been seen on a wider variety 42132720Skan of tests (such as the compiler itself). 43132720Skan 44132720Skan Right now we maintain our free list on a per-function basis. It may 45132720Skan or may not make sense to maintain the free list for the duration of 46132720Skan a compilation unit. 47132720Skan 48132720Skan External code should rely solely upon HIGHEST_SSA_VERSION and the 49132720Skan externally defined functions. External code should not know about 50132720Skan the details of the free list management. 51132720Skan 52132720Skan External code should also not assume the version number on nodes is 53132720Skan monotonically increasing. We reuse the version number when we 54132720Skan reuse an SSA_NAME expression. This helps keep arrays and bitmaps 55132720Skan more compact. 56132720Skan 57132720Skan We could also use a zone allocator for these objects since they have 58132720Skan a very well defined lifetime. If someone wants to experiment with that 59169691Skan this is the place to try it. */ 60169691Skan 61/* Array of all SSA_NAMEs used in the function. */ 62VEC(tree,gc) *ssa_names; 63 64/* Free list of SSA_NAMEs. This list is wiped at the end of each function 65 after we leave SSA form. */ 66static GTY (()) tree free_ssanames; 67 68/* Version numbers with special meanings. We start allocating new version 69 numbers after the special ones. */ 70#define UNUSED_NAME_VERSION 0 71 72#ifdef GATHER_STATISTICS 73unsigned int ssa_name_nodes_reused; 74unsigned int ssa_name_nodes_created; 75#endif 76 77/* Initialize management of SSA_NAMEs. */ 78 79void 80init_ssanames (void) 81{ 82 ssa_names = VEC_alloc (tree, gc, 50); 83 84 /* Version 0 is special, so reserve the first slot in the table. Though 85 currently unused, we may use version 0 in alias analysis as part of 86 the heuristics used to group aliases when the alias sets are too 87 large. 88 89 We use VEC_quick_push here because we know that SSA_NAMES has at 90 least 50 elements reserved in it. */ 91 VEC_quick_push (tree, ssa_names, NULL_TREE); 92 free_ssanames = NULL; 93} 94 95/* Finalize management of SSA_NAMEs. */ 96 97void 98fini_ssanames (void) 99{ 100 VEC_free (tree, gc, ssa_names); 101 free_ssanames = NULL; 102} 103 104/* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ 105 106#ifdef GATHER_STATISTICS 107void 108ssanames_print_statistics (void) 109{ 110 fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); 111 fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); 112} 113#endif 114 115/* Return an SSA_NAME node for variable VAR defined in statement STMT. 116 STMT may be an empty statement for artificial references (e.g., default 117 definitions created when a variable is used without a preceding 118 definition). */ 119 120tree 121make_ssa_name (tree var, tree stmt) 122{ 123 tree t; 124 use_operand_p imm; 125 126 gcc_assert (DECL_P (var) 127 || TREE_CODE (var) == INDIRECT_REF); 128 129 gcc_assert (!stmt || EXPR_P (stmt) || TREE_CODE (stmt) == PHI_NODE); 130 131 /* If our free list has an element, then use it. */ 132 if (free_ssanames) 133 { 134 t = free_ssanames; 135 free_ssanames = TREE_CHAIN (free_ssanames); 136#ifdef GATHER_STATISTICS 137 ssa_name_nodes_reused++; 138#endif 139 140 /* The node was cleared out when we put it on the free list, so 141 there is no need to do so again here. */ 142 gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL); 143 VEC_replace (tree, ssa_names, SSA_NAME_VERSION (t), t); 144 } 145 else 146 { 147 t = make_node (SSA_NAME); 148 SSA_NAME_VERSION (t) = num_ssa_names; 149 VEC_safe_push (tree, gc, ssa_names, t); 150#ifdef GATHER_STATISTICS 151 ssa_name_nodes_created++; 152#endif 153 } 154 155 TREE_TYPE (t) = TREE_TYPE (var); 156 SSA_NAME_VAR (t) = var; 157 SSA_NAME_DEF_STMT (t) = stmt; 158 SSA_NAME_PTR_INFO (t) = NULL; 159 SSA_NAME_IN_FREE_LIST (t) = 0; 160 imm = &(SSA_NAME_IMM_USE_NODE (t)); 161 imm->use = NULL; 162 imm->prev = imm; 163 imm->next = imm; 164 imm->stmt = t; 165 166 return t; 167} 168 169 170/* We no longer need the SSA_NAME expression VAR, release it so that 171 it may be reused. 172 173 Note it is assumed that no calls to make_ssa_name will be made 174 until all uses of the ssa name are released and that the only 175 use of the SSA_NAME expression is to check its SSA_NAME_VAR. All 176 other fields must be assumed clobbered. */ 177 178void 179release_ssa_name (tree var) 180{ 181 if (!var) 182 return; 183 184 /* Never release the default definition for a symbol. It's a 185 special SSA name that should always exist once it's created. */ 186 if (var == default_def (SSA_NAME_VAR (var))) 187 return; 188 189 /* If VAR has been registered for SSA updating, don't remove it. 190 After update_ssa has run, the name will be released. */ 191 if (name_registered_for_update_p (var)) 192 { 193 release_ssa_name_after_update_ssa (var); 194 return; 195 } 196 197 /* release_ssa_name can be called multiple times on a single SSA_NAME. 198 However, it should only end up on our free list one time. We 199 keep a status bit in the SSA_NAME node itself to indicate it has 200 been put on the free list. 201 202 Note that once on the freelist you can not reference the SSA_NAME's 203 defining statement. */ 204 if (! SSA_NAME_IN_FREE_LIST (var)) 205 { 206 tree saved_ssa_name_var = SSA_NAME_VAR (var); 207 int saved_ssa_name_version = SSA_NAME_VERSION (var); 208 use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); 209 210#ifdef ENABLE_CHECKING 211 verify_imm_links (stderr, var); 212#endif 213 while (imm->next != imm) 214 delink_imm_use (imm->next); 215 216 VEC_replace (tree, ssa_names, SSA_NAME_VERSION (var), NULL_TREE); 217 memset (var, 0, tree_size (var)); 218 219 imm->prev = imm; 220 imm->next = imm; 221 imm->stmt = var; 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 link it into the free list. */ 237 TREE_CHAIN (var) = free_ssanames; 238 free_ssanames = var; 239 } 240} 241 242/* Creates a duplicate of a ssa name NAME defined in statement STMT. */ 243 244tree 245duplicate_ssa_name (tree name, tree stmt) 246{ 247 tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt); 248 struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); 249 250 if (old_ptr_info) 251 duplicate_ssa_name_ptr_info (new_name, old_ptr_info); 252 253 return new_name; 254} 255 256 257/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by 258 the SSA name NAME. */ 259 260void 261duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) 262{ 263 struct ptr_info_def *new_ptr_info; 264 265 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); 266 gcc_assert (!SSA_NAME_PTR_INFO (name)); 267 268 if (!ptr_info) 269 return; 270 271 new_ptr_info = ggc_alloc (sizeof (struct ptr_info_def)); 272 *new_ptr_info = *ptr_info; 273 274 if (ptr_info->pt_vars) 275 { 276 new_ptr_info->pt_vars = BITMAP_GGC_ALLOC (); 277 bitmap_copy (new_ptr_info->pt_vars, ptr_info->pt_vars); 278 } 279 280 SSA_NAME_PTR_INFO (name) = new_ptr_info; 281} 282 283 284/* Release all the SSA_NAMEs created by STMT. */ 285 286void 287release_defs (tree stmt) 288{ 289 tree def; 290 ssa_op_iter iter; 291 292 /* Make sure that we are in SSA. Otherwise, operand cache may point 293 to garbage. */ 294 gcc_assert (in_ssa_p); 295 296 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 297 if (TREE_CODE (def) == SSA_NAME) 298 release_ssa_name (def); 299} 300 301 302/* Replace the symbol associated with SSA_NAME with SYM. */ 303 304void 305replace_ssa_name_symbol (tree ssa_name, tree sym) 306{ 307 SSA_NAME_VAR (ssa_name) = sym; 308 TREE_TYPE (ssa_name) = TREE_TYPE (sym); 309} 310 311#include "gt-tree-ssanames.h" 312