--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/tree-ssanames.c	Fri Jul 17 14:47:48 2009 +0900
@@ -0,0 +1,363 @@
+/* Generic routines for manipulating SSA_NAME expressions
+   Copyright (C) 2003, 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
+                                                                               
+This file is part of GCC.
+                                                                               
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+                                                                               
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+                                                                               
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "varray.h"
+#include "ggc.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+
+/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
+   many of which may be thrown away shortly after their creation if jumps
+   were threaded through PHI nodes.  
+
+   While our garbage collection mechanisms will handle this situation, it
+   is extremely wasteful to create nodes and throw them away, especially
+   when the nodes can be reused.
+
+   For PR 8361, we can significantly reduce the number of nodes allocated
+   and thus the total amount of memory allocated by managing SSA_NAMEs a
+   little.  This additionally helps reduce the amount of work done by the
+   garbage collector.  Similar results have been seen on a wider variety
+   of tests (such as the compiler itself).
+
+   Right now we maintain our free list on a per-function basis.  It may
+   or may not make sense to maintain the free list for the duration of
+   a compilation unit. 
+
+   External code should rely solely upon HIGHEST_SSA_VERSION and the
+   externally defined functions.  External code should not know about
+   the details of the free list management.
+
+   External code should also not assume the version number on nodes is
+   monotonically increasing.  We reuse the version number when we
+   reuse an SSA_NAME expression.  This helps keep arrays and bitmaps
+   more compact.
+
+   We could also use a zone allocator for these objects since they have
+   a very well defined lifetime.  If someone wants to experiment with that
+   this is the place to try it.  */
+
+/* Version numbers with special meanings.  We start allocating new version
+   numbers after the special ones.  */
+#define UNUSED_NAME_VERSION 0
+
+#ifdef GATHER_STATISTICS
+unsigned int ssa_name_nodes_reused;
+unsigned int ssa_name_nodes_created;
+#endif
+
+/* Initialize management of SSA_NAMEs to default SIZE.  If SIZE is
+   zero use default.  */
+
+void
+init_ssanames (struct function *fn, int size)
+{
+  if (size < 50)
+    size = 50;
+
+  SSANAMES (fn) = VEC_alloc (tree, gc, size);
+
+  /* Version 0 is special, so reserve the first slot in the table.  Though
+     currently unused, we may use version 0 in alias analysis as part of
+     the heuristics used to group aliases when the alias sets are too
+     large.
+
+     We use VEC_quick_push here because we know that SSA_NAMES has at
+     least 50 elements reserved in it.  */
+  VEC_quick_push (tree, SSANAMES (fn), NULL_TREE);
+  FREE_SSANAMES (fn) = NULL;
+}
+
+/* Finalize management of SSA_NAMEs.  */
+
+void
+fini_ssanames (void)
+{
+  VEC_free (tree, gc, SSANAMES (cfun));
+  FREE_SSANAMES (cfun) = NULL;
+}
+
+/* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
+
+#ifdef GATHER_STATISTICS
+void
+ssanames_print_statistics (void)
+{
+  fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created);
+  fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused);
+}
+#endif
+
+/* Return an SSA_NAME node for variable VAR defined in statement STMT
+   in function FN.  STMT may be an empty statement for artificial
+   references (e.g., default definitions created when a variable is
+   used without a preceding definition).  */
+
+tree
+make_ssa_name_fn (struct function *fn, tree var, gimple stmt)
+{
+  tree t;
+  use_operand_p imm;
+
+  gcc_assert (DECL_P (var));
+
+  /* If our free list has an element, then use it.  */
+  if (FREE_SSANAMES (fn))
+    {
+      t = FREE_SSANAMES (fn);
+      FREE_SSANAMES (fn) = TREE_CHAIN (FREE_SSANAMES (fn));
+#ifdef GATHER_STATISTICS
+      ssa_name_nodes_reused++;
+#endif
+
+      /* The node was cleared out when we put it on the free list, so
+	 there is no need to do so again here.  */
+      gcc_assert (ssa_name (SSA_NAME_VERSION (t)) == NULL);
+      VEC_replace (tree, SSANAMES (fn), SSA_NAME_VERSION (t), t);
+    }
+  else
+    {
+      t = make_node (SSA_NAME);
+      SSA_NAME_VERSION (t) = VEC_length (tree, SSANAMES (fn));
+      VEC_safe_push (tree, gc, SSANAMES (fn), t);
+#ifdef GATHER_STATISTICS
+      ssa_name_nodes_created++;
+#endif
+    }
+
+  TREE_TYPE (t) = TREE_TYPE (var);
+  SSA_NAME_VAR (t) = var;
+  SSA_NAME_DEF_STMT (t) = stmt;
+  SSA_NAME_PTR_INFO (t) = NULL;
+  SSA_NAME_IN_FREE_LIST (t) = 0;
+  SSA_NAME_IS_DEFAULT_DEF (t) = 0;
+  imm = &(SSA_NAME_IMM_USE_NODE (t));
+  imm->use = NULL;
+  imm->prev = imm;
+  imm->next = imm;
+  imm->loc.ssa_name = t;
+
+  return t;
+}
+
+
+/* We no longer need the SSA_NAME expression VAR, release it so that
+   it may be reused. 
+
+   Note it is assumed that no calls to make_ssa_name will be made
+   until all uses of the ssa name are released and that the only
+   use of the SSA_NAME expression is to check its SSA_NAME_VAR.  All
+   other fields must be assumed clobbered.  */
+
+void
+release_ssa_name (tree var)
+{
+  if (!var)
+    return;
+
+  /* Never release the default definition for a symbol.  It's a
+     special SSA name that should always exist once it's created.  */
+  if (SSA_NAME_IS_DEFAULT_DEF (var))
+    return;
+
+  /* If VAR has been registered for SSA updating, don't remove it.
+     After update_ssa has run, the name will be released.  */
+  if (name_registered_for_update_p (var))
+    {
+      release_ssa_name_after_update_ssa (var);
+      return;
+    }
+
+  /* release_ssa_name can be called multiple times on a single SSA_NAME.
+     However, it should only end up on our free list one time.   We
+     keep a status bit in the SSA_NAME node itself to indicate it has
+     been put on the free list. 
+
+     Note that once on the freelist you can not reference the SSA_NAME's
+     defining statement.  */
+  if (! SSA_NAME_IN_FREE_LIST (var))
+    {
+      tree saved_ssa_name_var = SSA_NAME_VAR (var);
+      int saved_ssa_name_version = SSA_NAME_VERSION (var);
+      use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var));
+
+#ifdef ENABLE_CHECKING
+      verify_imm_links (stderr, var);
+#endif
+      while (imm->next != imm)
+	delink_imm_use (imm->next);
+
+      VEC_replace (tree, SSANAMES (cfun),
+		   SSA_NAME_VERSION (var), NULL_TREE);
+      memset (var, 0, tree_size (var));
+
+      imm->prev = imm;
+      imm->next = imm;
+      imm->loc.ssa_name = var;
+
+      /* First put back the right tree node so that the tree checking
+	 macros do not complain.  */
+      TREE_SET_CODE (var, SSA_NAME);
+
+      /* Restore the version number.  */
+      SSA_NAME_VERSION (var) = saved_ssa_name_version;
+
+      /* Hopefully this can go away once we have the new incremental
+         SSA updating code installed.  */
+      SSA_NAME_VAR (var) = saved_ssa_name_var;
+
+      /* Note this SSA_NAME is now in the first list.  */
+      SSA_NAME_IN_FREE_LIST (var) = 1;
+
+      /* And finally link it into the free list.  */
+      TREE_CHAIN (var) = FREE_SSANAMES (cfun);
+      FREE_SSANAMES (cfun) = var;
+    }
+}
+
+/* Creates a duplicate of a ssa name NAME defined in statement STMT.  */
+
+tree
+duplicate_ssa_name (tree name, gimple stmt)
+{
+  tree new_name = make_ssa_name (SSA_NAME_VAR (name), stmt);
+  struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name);
+
+  if (old_ptr_info)
+    duplicate_ssa_name_ptr_info (new_name, old_ptr_info);
+
+  return new_name;
+}
+
+
+/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by
+   the SSA name NAME.  */
+
+void
+duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info)
+{
+  struct ptr_info_def *new_ptr_info;
+
+  gcc_assert (POINTER_TYPE_P (TREE_TYPE (name)));
+  gcc_assert (!SSA_NAME_PTR_INFO (name));
+
+  if (!ptr_info)
+    return;
+
+  new_ptr_info = GGC_NEW (struct ptr_info_def);
+  *new_ptr_info = *ptr_info;
+
+  if (ptr_info->pt_vars)
+    {
+      new_ptr_info->pt_vars = BITMAP_GGC_ALLOC ();
+      bitmap_copy (new_ptr_info->pt_vars, ptr_info->pt_vars);
+    }
+
+  SSA_NAME_PTR_INFO (name) = new_ptr_info;
+}
+
+
+/* Release all the SSA_NAMEs created by STMT.  */
+
+void
+release_defs (gimple stmt)
+{
+  tree def;
+  ssa_op_iter iter;
+
+  /* Make sure that we are in SSA.  Otherwise, operand cache may point
+     to garbage.  */
+  gcc_assert (gimple_in_ssa_p (cfun));
+
+  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
+    if (TREE_CODE (def) == SSA_NAME)
+      release_ssa_name (def);
+}
+
+
+/* Replace the symbol associated with SSA_NAME with SYM.  */
+
+void
+replace_ssa_name_symbol (tree ssa_name, tree sym)
+{
+  SSA_NAME_VAR (ssa_name) = sym;
+  TREE_TYPE (ssa_name) = TREE_TYPE (sym);
+}
+
+/* Return SSA names that are unused to GGC memory.  This is used to keep
+   footprint of compiler during interprocedural optimization.
+   As a side effect the SSA_NAME_VERSION number reuse is reduced
+   so this function should not be used too often.  */
+static unsigned int
+release_dead_ssa_names (void)
+{
+  tree t, next;
+  int n = 0;
+  referenced_var_iterator rvi;
+
+  /* Current defs point to various dead SSA names that in turn points to dead
+     statements so bunch of dead memory is held from releasing.  */
+  FOR_EACH_REFERENCED_VAR (t, rvi)
+    set_current_def (t, NULL);
+  /* Now release the freelist.  */
+  for (t = FREE_SSANAMES (cfun); t; t = next)
+    {
+      next = TREE_CHAIN (t);
+      /* Dangling pointers might make GGC to still see dead SSA names, so it is
+ 	 important to unlink the list and avoid GGC from seeing all subsequent
+	 SSA names.  In longer run we want to have all dangling pointers here
+	 removed (since they usually go through dead statements that consume
+	 considerable amounts of memory).  */
+      TREE_CHAIN (t) = NULL_TREE;
+      n++;
+    }
+  FREE_SSANAMES (cfun) = NULL;
+
+  /* Cgraph edges has been invalidated and point to dead statement.  We need to
+     remove them now and will rebuild it before next IPA pass.  */
+  cgraph_node_remove_callees (cgraph_node (current_function_decl));
+
+  if (dump_file)
+    fprintf (dump_file, "Released %i names, %.2f%%\n", n, n * 100.0 / num_ssa_names);
+  return 0;
+}
+
+struct gimple_opt_pass pass_release_ssa_names =
+{
+ {
+  GIMPLE_PASS,
+  "release_ssa",			/* name */
+  NULL,					/* gate */
+  release_dead_ssa_names,		/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  0,					/* tv_id */
+  PROP_ssa,				/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func 			/* todo_flags_finish */
+ }
+};