1/* Generic routines for manipulating SSA_NAME expressions 2 Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 2, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING. If not, write to 18the Free Software Foundation, 51 Franklin Street, Fifth Floor, 19Boston, MA 02110-1301, USA. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "tree.h" 26#include "varray.h" 27#include "ggc.h" 28#include "tree-flow.h" 29 30/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, 31 many of which may be thrown away shortly after their creation if jumps 32 were threaded through PHI nodes. 33 34 While our garbage collection mechanisms will handle this situation, it 35 is extremely wasteful to create nodes and throw them away, especially 36 when the nodes can be reused. 37 38 For PR 8361, we can significantly reduce the number of nodes allocated 39 and thus the total amount of memory allocated by managing SSA_NAMEs a 40 little. This additionally helps reduce the amount of work done by the 41 garbage collector. Similar results have been seen on a wider variety 42 of tests (such as the compiler itself). 43 44 Right now we maintain our free list on a per-function basis. It may 45 or may not make sense to maintain the free list for the duration of 46 a compilation unit. 47 48 External code should rely solely upon HIGHEST_SSA_VERSION and the 49 externally defined functions. External code should not know about 50 the details of the free list management. 51 52 External code should also not assume the version number on nodes is 53 monotonically increasing. We reuse the version number when we 54 reuse an SSA_NAME expression. This helps keep arrays and bitmaps 55 more compact. 56 57 We could also use a zone allocator for these objects since they have 58 a very well defined lifetime. If someone wants to experiment with that 59 this is the place to try it. */ 60 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