11045Sfyuan/* Generic routines for manipulating SSA_NAME expressions 21045Sfyuan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 31045Sfyuan 41045SfyuanThis file is part of GCC. 51045Sfyuan 61045SfyuanGCC is free software; you can redistribute it and/or modify 71045Sfyuanit under the terms of the GNU General Public License as published by 81045Sfyuanthe Free Software Foundation; either version 2, or (at your option) 91045Sfyuanany later version. 101045Sfyuan 111045SfyuanGCC is distributed in the hope that it will be useful, 121045Sfyuanbut WITHOUT ANY WARRANTY; without even the implied warranty of 131045SfyuanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 141045SfyuanGNU General Public License for more details. 151045Sfyuan 161045SfyuanYou should have received a copy of the GNU General Public License 171045Sfyuanalong with GCC; see the file COPYING. If not, write to 181045Sfyuanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 191045SfyuanBoston, MA 02110-1301, USA. */ 201045Sfyuan 211045Sfyuan#include "config.h" 221045Sfyuan#include "system.h" 231045Sfyuan#include "coretypes.h" 241045Sfyuan#include "tm.h" 251045Sfyuan#include "tree.h" 261045Sfyuan#include "varray.h" 271045Sfyuan#include "ggc.h" 281045Sfyuan#include "tree-flow.h" 291045Sfyuan 301045Sfyuan/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, 311045Sfyuan many of which may be thrown away shortly after their creation if jumps 321045Sfyuan were threaded through PHI nodes. 331045Sfyuan 341045Sfyuan While our garbage collection mechanisms will handle this situation, it 351045Sfyuan is extremely wasteful to create nodes and throw them away, especially 361045Sfyuan when the nodes can be reused. 371045Sfyuan 381045Sfyuan For PR 8361, we can significantly reduce the number of nodes allocated 391045Sfyuan and thus the total amount of memory allocated by managing SSA_NAMEs a 401045Sfyuan little. This additionally helps reduce the amount of work done by the 411045Sfyuan garbage collector. Similar results have been seen on a wider variety 421045Sfyuan of tests (such as the compiler itself). 431045Sfyuan 441045Sfyuan Right now we maintain our free list on a per-function basis. It may 451045Sfyuan or may not make sense to maintain the free list for the duration of 461045Sfyuan a compilation unit. 471045Sfyuan 481045Sfyuan External code should rely solely upon HIGHEST_SSA_VERSION and the 491045Sfyuan externally defined functions. External code should not know about 501045Sfyuan the details of the free list management. 511045Sfyuan 521045Sfyuan External code should also not assume the version number on nodes is 531045Sfyuan monotonically increasing. We reuse the version number when we 541045Sfyuan reuse an SSA_NAME expression. This helps keep arrays and bitmaps 551045Sfyuan more compact. 561045Sfyuan 571045Sfyuan We could also use a zone allocator for these objects since they have 581045Sfyuan a very well defined lifetime. If someone wants to experiment with that 591045Sfyuan this is the place to try it. */ 601045Sfyuan 611045Sfyuan/* Array of all SSA_NAMEs used in the function. */ 621045SfyuanVEC(tree,gc) *ssa_names; 631045Sfyuan 641045Sfyuan/* Free list of SSA_NAMEs. This list is wiped at the end of each function 651045Sfyuan after we leave SSA form. */ 661045Sfyuanstatic GTY (()) tree free_ssanames; 671045Sfyuan 681045Sfyuan/* Version numbers with special meanings. We start allocating new version 691045Sfyuan numbers after the special ones. */ 701045Sfyuan#define UNUSED_NAME_VERSION 0 711045Sfyuan 721045Sfyuan#ifdef GATHER_STATISTICS 731045Sfyuanunsigned int ssa_name_nodes_reused; 741045Sfyuanunsigned int ssa_name_nodes_created; 751045Sfyuan#endif 761045Sfyuan 771045Sfyuan/* Initialize management of SSA_NAMEs. */ 781045Sfyuan 791045Sfyuanvoid 801045Sfyuaninit_ssanames (void) 811045Sfyuan{ 821045Sfyuan ssa_names = VEC_alloc (tree, gc, 50); 831045Sfyuan 841045Sfyuan /* Version 0 is special, so reserve the first slot in the table. Though 851045Sfyuan currently unused, we may use version 0 in alias analysis as part of 861045Sfyuan the heuristics used to group aliases when the alias sets are too 871045Sfyuan large. 881045Sfyuan 891045Sfyuan We use VEC_quick_push here because we know that SSA_NAMES has at 901045Sfyuan least 50 elements reserved in it. */ 911045Sfyuan VEC_quick_push (tree, ssa_names, NULL_TREE); 921045Sfyuan free_ssanames = NULL; 931045Sfyuan} 941045Sfyuan 951045Sfyuan/* Finalize management of SSA_NAMEs. */ 961045Sfyuan 971045Sfyuanvoid 981045Sfyuanfini_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