1169689Skan/* Generic routines for manipulating SSA_NAME expressions 2169689Skan Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan 4169689SkanThis file is part of GCC. 5169689Skan 6169689SkanGCC is free software; you can redistribute it and/or modify 7169689Skanit under the terms of the GNU General Public License as published by 8169689Skanthe Free Software Foundation; either version 2, or (at your option) 9169689Skanany later version. 10169689Skan 11169689SkanGCC is distributed in the hope that it will be useful, 12169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 13169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169689SkanGNU General Public License for more details. 15169689Skan 16169689SkanYou should have received a copy of the GNU General Public License 17169689Skanalong with GCC; see the file COPYING. If not, write to 18169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 19169689SkanBoston, MA 02110-1301, USA. */ 20169689Skan 21169689Skan#include "config.h" 22169689Skan#include "system.h" 23169689Skan#include "coretypes.h" 24169689Skan#include "tm.h" 25169689Skan#include "tree.h" 26169689Skan#include "varray.h" 27169689Skan#include "ggc.h" 28169689Skan#include "tree-flow.h" 29169689Skan 30169689Skan/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, 31169689Skan many of which may be thrown away shortly after their creation if jumps 32169689Skan were threaded through PHI nodes. 33169689Skan 34169689Skan While our garbage collection mechanisms will handle this situation, it 35169689Skan is extremely wasteful to create nodes and throw them away, especially 36169689Skan when the nodes can be reused. 37169689Skan 38169689Skan For PR 8361, we can significantly reduce the number of nodes allocated 39169689Skan and thus the total amount of memory allocated by managing SSA_NAMEs a 40169689Skan little. This additionally helps reduce the amount of work done by the 41169689Skan garbage collector. Similar results have been seen on a wider variety 42169689Skan of tests (such as the compiler itself). 43169689Skan 44169689Skan Right now we maintain our free list on a per-function basis. It may 45169689Skan or may not make sense to maintain the free list for the duration of 46169689Skan a compilation unit. 47169689Skan 48169689Skan External code should rely solely upon HIGHEST_SSA_VERSION and the 49169689Skan externally defined functions. External code should not know about 50169689Skan the details of the free list management. 51169689Skan 52169689Skan External code should also not assume the version number on nodes is 53169689Skan monotonically increasing. We reuse the version number when we 54169689Skan reuse an SSA_NAME expression. This helps keep arrays and bitmaps 55169689Skan more compact. 56169689Skan 57169689Skan We could also use a zone allocator for these objects since they have 58169689Skan a very well defined lifetime. If someone wants to experiment with that 59169689Skan this is the place to try it. */ 60169689Skan 61169689Skan/* Array of all SSA_NAMEs used in the function. */ 62169689SkanVEC(tree,gc) *ssa_names; 63169689Skan 64169689Skan/* Free list of SSA_NAMEs. This list is wiped at the end of each function 65169689Skan after we leave SSA form. */ 66169689Skanstatic GTY (()) tree free_ssanames; 67169689Skan 68169689Skan/* Version numbers with special meanings. We start allocating new version 69169689Skan numbers after the special ones. */ 70169689Skan#define UNUSED_NAME_VERSION 0 71169689Skan 72169689Skan#ifdef GATHER_STATISTICS 73169689Skanunsigned int ssa_name_nodes_reused; 74169689Skanunsigned int ssa_name_nodes_created; 75169689Skan#endif 76169689Skan 77169689Skan/* Initialize management of SSA_NAMEs. */ 78169689Skan 79169689Skanvoid 80169689Skaninit_ssanames (void) 81169689Skan{ 82169689Skan ssa_names = VEC_alloc (tree, gc, 50); 83169689Skan 84169689Skan /* Version 0 is special, so reserve the first slot in the table. Though 85169689Skan currently unused, we may use version 0 in alias analysis as part of 86169689Skan the heuristics used to group aliases when the alias sets are too 87169689Skan large. 88169689Skan 89169689Skan We use VEC_quick_push here because we know that SSA_NAMES has at 90169689Skan least 50 elements reserved in it. */ 91169689Skan VEC_quick_push (tree, ssa_names, NULL_TREE); 92169689Skan free_ssanames = NULL; 93169689Skan} 94169689Skan 95169689Skan/* Finalize management of SSA_NAMEs. */ 96169689Skan 97169689Skanvoid 98169689Skanfini_ssanames (void) 99169689Skan{ 100169689Skan VEC_free (tree, gc, ssa_names); 101169689Skan free_ssanames = NULL; 102169689Skan} 103169689Skan 104169689Skan/* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ 105169689Skan 106169689Skan#ifdef GATHER_STATISTICS 107169689Skanvoid 108169689Skanssanames_print_statistics (void) 109169689Skan{ 110169689Skan fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); 111169689Skan fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); 112169689Skan} 113169689Skan#endif 114169689Skan 115169689Skan/* Return an SSA_NAME node for variable VAR defined in statement STMT. 116169689Skan STMT may be an empty statement for artificial references (e.g., default 117169689Skan definitions created when a variable is used without a preceding 118169689Skan definition). */ 119169689Skan 120169689Skantree 121169689Skanmake_ssa_name (tree var, tree stmt) 122169689Skan{ 123169689Skan tree t; 124169689Skan use_operand_p imm; 125169689Skan 126169689Skan gcc_assert (DECL_P (var) 127169689Skan || TREE_CODE (var) == INDIRECT_REF); 128169689Skan 129169689Skan gcc_assert (!stmt || EXPR_P (stmt) || TREE_CODE (stmt) == PHI_NODE); 130169689Skan 131169689Skan /* If our free list has an element, then use it. */ 132169689Skan if (free_ssanames) 133169689Skan { 134169689Skan t = free_ssanames; 135169689Skan free_ssanames = TREE_CHAIN (free_ssanames); 136169689Skan#ifdef GATHER_STATISTICS 137169689Skan ssa_name_nodes_reused++; 138169689Skan#endif 139169689Skan 140169689Skan /* The node was cleared out when we put it on the free list, so 141169689Skan there is no need to do so again here. */ 142169689Skan gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL); 143169689Skan VEC_replace (tree, ssa_names, SSA_NAME_VERSION (t), t); 144169689Skan } 145169689Skan else 146169689Skan { 147169689Skan t = make_node (SSA_NAME); 148169689Skan SSA_NAME_VERSION (t) = num_ssa_names; 149169689Skan VEC_safe_push (tree, gc, ssa_names, t); 150169689Skan#ifdef GATHER_STATISTICS 151169689Skan ssa_name_nodes_created++; 152169689Skan#endif 153169689Skan } 154169689Skan 155169689Skan TREE_TYPE (t) = TREE_TYPE (var); 156169689Skan SSA_NAME_VAR (t) = var; 157169689Skan SSA_NAME_DEF_STMT (t) = stmt; 158169689Skan SSA_NAME_PTR_INFO (t) = NULL; 159169689Skan SSA_NAME_IN_FREE_LIST (t) = 0; 160169689Skan imm = &(SSA_NAME_IMM_USE_NODE (t)); 161169689Skan imm->use = NULL; 162169689Skan imm->prev = imm; 163169689Skan imm->next = imm; 164169689Skan imm->stmt = t; 165169689Skan 166169689Skan return t; 167169689Skan} 168169689Skan 169169689Skan 170169689Skan/* We no longer need the SSA_NAME expression VAR, release it so that 171169689Skan it may be reused. 172169689Skan 173169689Skan Note it is assumed that no calls to make_ssa_name will be made 174169689Skan until all uses of the ssa name are released and that the only 175169689Skan use of the SSA_NAME expression is to check its SSA_NAME_VAR. All 176169689Skan other fields must be assumed clobbered. */ 177169689Skan 178169689Skanvoid 179169689Skanrelease_ssa_name (tree var) 180169689Skan{ 181169689Skan if (!var) 182169689Skan return; 183169689Skan 184169689Skan /* Never release the default definition for a symbol. It's a 185169689Skan special SSA name that should always exist once it's created. */ 186169689Skan if (var == default_def (SSA_NAME_VAR (var))) 187169689Skan return; 188169689Skan 189169689Skan /* If VAR has been registered for SSA updating, don't remove it. 190169689Skan After update_ssa has run, the name will be released. */ 191169689Skan if (name_registered_for_update_p (var)) 192169689Skan { 193169689Skan release_ssa_name_after_update_ssa (var); 194169689Skan return; 195169689Skan } 196169689Skan 197169689Skan /* release_ssa_name can be called multiple times on a single SSA_NAME. 198169689Skan However, it should only end up on our free list one time. We 199169689Skan keep a status bit in the SSA_NAME node itself to indicate it has 200169689Skan been put on the free list. 201169689Skan 202169689Skan Note that once on the freelist you can not reference the SSA_NAME's 203169689Skan defining statement. */ 204169689Skan if (! SSA_NAME_IN_FREE_LIST (var)) 205169689Skan { 206169689Skan tree saved_ssa_name_var = SSA_NAME_VAR (var); 207169689Skan int saved_ssa_name_version = SSA_NAME_VERSION (var); 208169689Skan use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); 209169689Skan 210169689Skan#ifdef ENABLE_CHECKING 211169689Skan verify_imm_links (stderr, var); 212169689Skan#endif 213169689Skan while (imm->next != imm) 214169689Skan delink_imm_use (imm->next); 215169689Skan 216169689Skan VEC_replace (tree, ssa_names, SSA_NAME_VERSION (var), NULL_TREE); 217169689Skan memset (var, 0, tree_size (var)); 218169689Skan 219169689Skan imm->prev = imm; 220169689Skan imm->next = imm; 221169689Skan imm->stmt = var; 222169689Skan /* First put back the right tree node so that the tree checking 223169689Skan macros do not complain. */ 224169689Skan TREE_SET_CODE (var, SSA_NAME); 225169689Skan 226169689Skan /* Restore the version number. */ 227169689Skan SSA_NAME_VERSION (var) = saved_ssa_name_version; 228169689Skan 229169689Skan /* Hopefully this can go away once we have the new incremental 230169689Skan SSA updating code installed. */ 231169689Skan SSA_NAME_VAR (var) = saved_ssa_name_var; 232169689Skan 233169689Skan /* Note this SSA_NAME is now in the first list. */ 234169689Skan SSA_NAME_IN_FREE_LIST (var) = 1; 235169689Skan 236169689Skan /* And finally link it into the free list. */ 237169689Skan TREE_CHAIN (var) = free_ssanames; 238169689Skan free_ssanames = var; 239169689Skan } 240169689Skan} 241169689Skan 242169689Skan/* Creates a duplicate of a ssa name NAME defined in statement STMT. */ 243169689Skan 244169689Skantree 245169689Skanduplicate_ssa_name (tree name, tree stmt) 246169689Skan{ 247169689Skan tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt); 248169689Skan struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); 249169689Skan 250169689Skan if (old_ptr_info) 251169689Skan duplicate_ssa_name_ptr_info (new_name, old_ptr_info); 252169689Skan 253169689Skan return new_name; 254169689Skan} 255169689Skan 256169689Skan 257169689Skan/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by 258169689Skan the SSA name NAME. */ 259169689Skan 260169689Skanvoid 261169689Skanduplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) 262169689Skan{ 263169689Skan struct ptr_info_def *new_ptr_info; 264169689Skan 265169689Skan gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); 266169689Skan gcc_assert (!SSA_NAME_PTR_INFO (name)); 267169689Skan 268169689Skan if (!ptr_info) 269169689Skan return; 270169689Skan 271169689Skan new_ptr_info = ggc_alloc (sizeof (struct ptr_info_def)); 272169689Skan *new_ptr_info = *ptr_info; 273169689Skan 274169689Skan if (ptr_info->pt_vars) 275169689Skan { 276169689Skan new_ptr_info->pt_vars = BITMAP_GGC_ALLOC (); 277169689Skan bitmap_copy (new_ptr_info->pt_vars, ptr_info->pt_vars); 278169689Skan } 279169689Skan 280169689Skan SSA_NAME_PTR_INFO (name) = new_ptr_info; 281169689Skan} 282169689Skan 283169689Skan 284169689Skan/* Release all the SSA_NAMEs created by STMT. */ 285169689Skan 286169689Skanvoid 287169689Skanrelease_defs (tree stmt) 288169689Skan{ 289169689Skan tree def; 290169689Skan ssa_op_iter iter; 291169689Skan 292169689Skan /* Make sure that we are in SSA. Otherwise, operand cache may point 293169689Skan to garbage. */ 294169689Skan gcc_assert (in_ssa_p); 295169689Skan 296169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 297169689Skan if (TREE_CODE (def) == SSA_NAME) 298169689Skan release_ssa_name (def); 299169689Skan} 300169689Skan 301169689Skan 302169689Skan/* Replace the symbol associated with SSA_NAME with SYM. */ 303169689Skan 304169689Skanvoid 305169689Skanreplace_ssa_name_symbol (tree ssa_name, tree sym) 306169689Skan{ 307169689Skan SSA_NAME_VAR (ssa_name) = sym; 308169689Skan TREE_TYPE (ssa_name) = TREE_TYPE (sym); 309169689Skan} 310169689Skan 311169689Skan#include "gt-tree-ssanames.h" 312