gcc/tree-ssanames.c

   1 /* Generic routines for manipulating SSA_NAME expressions
   2    Copyright (C) 2003 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, 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
  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 /* Next SSA version number to be allocated.  */
  61 unsigned int highest_ssa_version;
  62
  63 /* Free list of SSA_NAMEs.  This list is wiped at the end of each function
  64    after we leave SSA form.  */
  65 static GTY (()) tree free_ssanames;
  66
  67 /* Version numbers with special meanings.  We start allocating new version
  68    numbers after the special ones.  */
  69 #define UNUSED_NAME_VERSION 0
  70
  71 #ifdef GATHER_STATISTICS
  72 unsigned int ssa_name_nodes_reused;
  73 unsigned int ssa_name_nodes_created;
  74 #endif
  75
  76 /* Initialize management of SSA_NAMEs.  */
  77
  78 void
  79 init_ssanames (void)
  80 {
  81   highest_ssa_version = UNUSED_NAME_VERSION + 1;
  82   free_ssanames = NULL;
  83 }
  84
  85 /* Finalize management of SSA_NAMEs.  */
  86
  87 void
  88 fini_ssanames (void)
  89 {
  90   free_ssanames = NULL;
  91 }
  92
  93 /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
  94
  95 #ifdef GATHER_STATISTICS
  96 void
  97 ssanames_print_statistics (void)
  98 {
  99   fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
 100   fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
 101 }
 102 #endif
 103
 104 /* Return an SSA_NAME node for variable VAR defined in statement STMT.
 105    STMT may be an empty statement for artificial references (e.g., default
 106    definitions created when a variable is used without a preceding
 107    definition).  */
 108
 109 tree
 110 make_ssa_name (tree var, tree stmt)
 111 {
 112   tree t;
 113
 114 #if defined ENABLE_CHECKING
 115   if ((!DECL_P (var)
 116        && TREE_CODE (var) != INDIRECT_REF)
 117       || (!IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (TREE_CODE (stmt)))
 118           && TREE_CODE (stmt) != PHI_NODE))
 119     abort ();
 120 #endif
 121
 122   /* If our free list has an element, then use it.  Also reuse the
 123      SSA version number of the element on the free list which helps
 124      keep sbitmaps and arrays sized HIGHEST_SSA_VERSION smaller.  */
 125   if (free_ssanames)
 126     {
 127       unsigned int save_version;
 128
 129       t = free_ssanames;
 130       free_ssanames = TREE_CHAIN (free_ssanames);
 131 #ifdef GATHER_STATISTICS
 132       ssa_name_nodes_reused++;
 133 #endif
 134
 135       /* Clear the node so that it looks just like one we would have
 136          received from make_node.  */
 137       save_version = SSA_NAME_VERSION (t);
 138       memset (t, 0, tree_size (t));
 139       TREE_SET_CODE (t, SSA_NAME);
 140       SSA_NAME_VERSION (t) = save_version;
 141     }
 142   else
 143     {
 144       t = make_node (SSA_NAME);
 145       SSA_NAME_VERSION (t) = highest_ssa_version++;
 146 #ifdef GATHER_STATISTICS
 147       ssa_name_nodes_created++;
 148 #endif
 149     }
 150
 151   TREE_TYPE (t) = TREE_TYPE (var);
 152   SSA_NAME_VAR (t) = var;
 153   SSA_NAME_DEF_STMT (t) = stmt;
 154
 155   return t;
 156 }
 157
 158 /* We no longer need the SSA_NAME expression VAR, release it so that
 159    it may be reused.
 160
 161    Note it is assumed that no calls to make_ssa_name will be made
 162    until all uses of the ssa name are released and that the only
 163    use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
 164    other fields must be assumed clobbered.  */
 165
 166 void
 167 release_ssa_name (tree var)
 168 {
 169   /* release_ssa_name can be called multiple times on a single SSA_NAME.
 170      However, it should only end up on our free list one time.   We
 171      keep a status bit in the SSA_NAME node itself to indicate it has
 172      been put on the free list.
 173
 174      Note that once on the freelist you can not reference the SSA_NAME's
 175      defining statement.  */
 176   if (! SSA_NAME_IN_FREE_LIST (var))
 177     {
 178       SSA_NAME_IN_FREE_LIST (var) = 1;
 179       TREE_CHAIN (var) = free_ssanames;
 180       free_ssanames = var;
 181     }
 182 }
 183
 184 #include "gt-tree-ssanames.h"