--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/tree-into-ssa.c	Fri Jul 17 14:47:48 2009 +0900
@@ -0,0 +1,3333 @@
+/* Rewrite a program in Normal form into SSA.
+   Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008
+   Free Software Foundation, Inc.
+   Contributed by Diego Novillo <dnovillo@redhat.com>
+
+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 "flags.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "langhooks.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "expr.h"
+#include "function.h"
+#include "diagnostic.h"
+#include "bitmap.h"
+#include "tree-flow.h"
+#include "gimple.h"
+#include "tree-inline.h"
+#include "varray.h"
+#include "timevar.h"
+#include "hashtab.h"
+#include "tree-dump.h"
+#include "tree-pass.h"
+#include "cfgloop.h"
+#include "domwalk.h"
+#include "ggc.h"
+#include "params.h"
+#include "vecprim.h"
+
+
+/* This file builds the SSA form for a function as described in:
+   R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
+   Computing Static Single Assignment Form and the Control Dependence
+   Graph. ACM Transactions on Programming Languages and Systems,
+   13(4):451-490, October 1991.  */
+
+/* Structure to map a variable VAR to the set of blocks that contain
+   definitions for VAR.  */
+struct def_blocks_d
+{
+  /* The variable.  */
+  tree var;
+
+  /* Blocks that contain definitions of VAR.  Bit I will be set if the
+     Ith block contains a definition of VAR.  */
+  bitmap def_blocks;
+
+  /* Blocks that contain a PHI node for VAR.  */
+  bitmap phi_blocks;
+
+  /* Blocks where VAR is live-on-entry.  Similar semantics as
+     DEF_BLOCKS.  */
+  bitmap livein_blocks;
+};
+
+
+/* Each entry in DEF_BLOCKS contains an element of type STRUCT
+   DEF_BLOCKS_D, mapping a variable VAR to a bitmap describing all the
+   basic blocks where VAR is defined (assigned a new value).  It also
+   contains a bitmap of all the blocks where VAR is live-on-entry
+   (i.e., there is a use of VAR in block B without a preceding
+   definition in B).  The live-on-entry information is used when
+   computing PHI pruning heuristics.  */
+static htab_t def_blocks;
+
+/* Stack of trees used to restore the global currdefs to its original
+   state after completing rewriting of a block and its dominator
+   children.  Its elements have the following properties:
+
+   - An SSA_NAME (N) indicates that the current definition of the
+     underlying variable should be set to the given SSA_NAME.  If the
+     symbol associated with the SSA_NAME is not a GIMPLE register, the
+     next slot in the stack must be a _DECL node (SYM).  In this case,
+     the name N in the previous slot is the current reaching
+     definition for SYM.
+
+   - A _DECL node indicates that the underlying variable has no
+     current definition.
+
+   - A NULL node at the top entry is used to mark the last slot
+     associated with the current block.  */
+static VEC(tree,heap) *block_defs_stack;
+
+
+/* Set of existing SSA names being replaced by update_ssa.  */
+static sbitmap old_ssa_names;
+
+/* Set of new SSA names being added by update_ssa.  Note that both
+   NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
+   the operations done on them are presence tests.  */
+static sbitmap new_ssa_names;
+
+
+/* Symbols whose SSA form needs to be updated or created for the first
+   time.  */
+static bitmap syms_to_rename;
+
+/* Subset of SYMS_TO_RENAME.  Contains all the GIMPLE register symbols
+   that have been marked for renaming.  */
+static bitmap regs_to_rename;
+
+/* Subset of SYMS_TO_RENAME.  Contains all the memory symbols
+   that have been marked for renaming.  */
+static bitmap mem_syms_to_rename;
+
+/* Set of SSA names that have been marked to be released after they
+   were registered in the replacement table.  They will be finally
+   released after we finish updating the SSA web.  */
+static bitmap names_to_release;
+
+static VEC(gimple_vec, heap) *phis_to_rewrite;
+
+/* The bitmap of non-NULL elements of PHIS_TO_REWRITE.  */
+static bitmap blocks_with_phis_to_rewrite;
+
+/* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES.  These sets need
+   to grow as the callers to register_new_name_mapping will typically
+   create new names on the fly.  FIXME.  Currently set to 1/3 to avoid
+   frequent reallocations but still need to find a reasonable growth
+   strategy.  */
+#define NAME_SETS_GROWTH_FACTOR	(MAX (3, num_ssa_names / 3))
+
+/* Tuple used to represent replacement mappings.  */
+struct repl_map_d
+{
+  tree name;
+  bitmap set;
+};
+
+
+/* NEW -> OLD_SET replacement table.  If we are replacing several
+   existing SSA names O_1, O_2, ..., O_j with a new name N_i,
+   then REPL_TBL[N_i] = { O_1, O_2, ..., O_j }.  */
+static htab_t repl_tbl;
+
+/* true if register_new_name_mapping needs to initialize the data
+   structures needed by update_ssa.  */
+static bool need_to_initialize_update_ssa_p = true;
+
+/* true if update_ssa needs to update virtual operands.  */
+static bool need_to_update_vops_p = false;
+
+/* Statistics kept by update_ssa to use in the virtual mapping
+   heuristic.  If the number of virtual mappings is beyond certain
+   threshold, the updater will switch from using the mappings into
+   renaming the virtual symbols from scratch.  In some cases, the
+   large number of name mappings for virtual names causes significant
+   slowdowns in the PHI insertion code.  */
+struct update_ssa_stats_d
+{
+  unsigned num_virtual_mappings;
+  unsigned num_total_mappings;
+  bitmap virtual_symbols;
+  unsigned num_virtual_symbols;
+};
+static struct update_ssa_stats_d update_ssa_stats;
+
+/* Global data to attach to the main dominator walk structure.  */
+struct mark_def_sites_global_data
+{
+  /* This bitmap contains the variables which are set before they
+     are used in a basic block.  */
+  bitmap kills;
+
+  /* Bitmap of names to rename.  */
+  sbitmap names_to_rename;
+
+  /* Set of blocks that mark_def_sites deems interesting for the
+     renamer to process.  */
+  sbitmap interesting_blocks;
+};
+
+
+/* Information stored for SSA names.  */
+struct ssa_name_info
+{
+  /* The current reaching definition replacing this SSA name.  */
+  tree current_def;
+
+  /* This field indicates whether or not the variable may need PHI nodes.
+     See the enum's definition for more detailed information about the
+     states.  */
+  ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
+
+  /* Age of this record (so that info_for_ssa_name table can be cleared
+     quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
+     are assumed to be null.  */
+  unsigned age;
+};
+
+/* The information associated with names.  */
+typedef struct ssa_name_info *ssa_name_info_p;
+DEF_VEC_P (ssa_name_info_p);
+DEF_VEC_ALLOC_P (ssa_name_info_p, heap);
+
+static VEC(ssa_name_info_p, heap) *info_for_ssa_name;
+static unsigned current_info_for_ssa_name_age;
+
+/* The set of blocks affected by update_ssa.  */
+static bitmap blocks_to_update;
+
+/* The main entry point to the SSA renamer (rewrite_blocks) may be
+   called several times to do different, but related, tasks.
+   Initially, we need it to rename the whole program into SSA form.
+   At other times, we may need it to only rename into SSA newly
+   exposed symbols.  Finally, we can also call it to incrementally fix
+   an already built SSA web.  */
+enum rewrite_mode {
+    /* Convert the whole function into SSA form.  */
+    REWRITE_ALL,
+
+    /* Incrementally update the SSA web by replacing existing SSA
+       names with new ones.  See update_ssa for details.  */
+    REWRITE_UPDATE
+};
+
+
+
+
+/* Prototypes for debugging functions.  */
+extern void dump_tree_ssa (FILE *);
+extern void debug_tree_ssa (void);
+extern void debug_def_blocks (void);
+extern void dump_tree_ssa_stats (FILE *);
+extern void debug_tree_ssa_stats (void);
+extern void dump_update_ssa (FILE *);
+extern void debug_update_ssa (void);
+extern void dump_names_replaced_by (FILE *, tree);
+extern void debug_names_replaced_by (tree);
+extern void dump_def_blocks (FILE *);
+extern void debug_def_blocks (void);
+extern void dump_defs_stack (FILE *, int);
+extern void debug_defs_stack (int);
+extern void dump_currdefs (FILE *);
+extern void debug_currdefs (void);
+
+/* Return true if STMT needs to be rewritten.  When renaming a subset
+   of the variables, not all statements will be processed.  This is
+   decided in mark_def_sites.  */
+
+static inline bool
+rewrite_uses_p (gimple stmt)
+{
+  return gimple_visited_p (stmt);
+}
+
+
+/* Set the rewrite marker on STMT to the value given by REWRITE_P.  */
+
+static inline void
+set_rewrite_uses (gimple stmt, bool rewrite_p)
+{
+  gimple_set_visited (stmt, rewrite_p);
+}
+
+
+/* Return true if the DEFs created by statement STMT should be
+   registered when marking new definition sites.  This is slightly
+   different than rewrite_uses_p: it's used by update_ssa to
+   distinguish statements that need to have both uses and defs
+   processed from those that only need to have their defs processed.
+   Statements that define new SSA names only need to have their defs
+   registered, but they don't need to have their uses renamed.  */
+
+static inline bool
+register_defs_p (gimple stmt)
+{
+  return gimple_plf (stmt, GF_PLF_1) != 0;
+}
+
+
+/* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered.  */
+
+static inline void
+set_register_defs (gimple stmt, bool register_defs_p)
+{
+  gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
+}
+
+
+/* Get the information associated with NAME.  */
+
+static inline ssa_name_info_p
+get_ssa_name_ann (tree name)
+{
+  unsigned ver = SSA_NAME_VERSION (name);
+  unsigned len = VEC_length (ssa_name_info_p, info_for_ssa_name);
+  struct ssa_name_info *info;
+
+  if (ver >= len)
+    {
+      unsigned new_len = num_ssa_names;
+
+      VEC_reserve (ssa_name_info_p, heap, info_for_ssa_name, new_len);
+      while (len++ < new_len)
+	{
+	  struct ssa_name_info *info = XCNEW (struct ssa_name_info);
+	  info->age = current_info_for_ssa_name_age;
+	  VEC_quick_push (ssa_name_info_p, info_for_ssa_name, info);
+	}
+    }
+
+  info = VEC_index (ssa_name_info_p, info_for_ssa_name, ver);
+  if (info->age < current_info_for_ssa_name_age)
+    {
+      info->need_phi_state = 0;
+      info->current_def = NULL_TREE;
+      info->age = current_info_for_ssa_name_age;
+    }
+
+  return info;
+}
+
+
+/* Clears info for SSA names.  */
+
+static void
+clear_ssa_name_info (void)
+{
+  current_info_for_ssa_name_age++;
+}
+
+
+/* Get phi_state field for VAR.  */
+
+static inline enum need_phi_state
+get_phi_state (tree var)
+{
+  if (TREE_CODE (var) == SSA_NAME)
+    return get_ssa_name_ann (var)->need_phi_state;
+  else
+    return var_ann (var)->need_phi_state;
+}
+
+
+/* Sets phi_state field for VAR to STATE.  */
+
+static inline void
+set_phi_state (tree var, enum need_phi_state state)
+{
+  if (TREE_CODE (var) == SSA_NAME)
+    get_ssa_name_ann (var)->need_phi_state = state;
+  else
+    var_ann (var)->need_phi_state = state;
+}
+
+
+/* Return the current definition for VAR.  */
+
+tree
+get_current_def (tree var)
+{
+  if (TREE_CODE (var) == SSA_NAME)
+    return get_ssa_name_ann (var)->current_def;
+  else
+    return var_ann (var)->current_def;
+}
+
+
+/* Sets current definition of VAR to DEF.  */
+
+void
+set_current_def (tree var, tree def)
+{
+  if (TREE_CODE (var) == SSA_NAME)
+    get_ssa_name_ann (var)->current_def = def;
+  else
+    var_ann (var)->current_def = def;
+}
+
+
+/* Compute global livein information given the set of blocks where
+   an object is locally live at the start of the block (LIVEIN)
+   and the set of blocks where the object is defined (DEF_BLOCKS).
+
+   Note: This routine augments the existing local livein information
+   to include global livein (i.e., it modifies the underlying bitmap
+   for LIVEIN).  */
+
+void
+compute_global_livein (bitmap livein ATTRIBUTE_UNUSED, bitmap def_blocks ATTRIBUTE_UNUSED)
+{
+  basic_block bb, *worklist, *tos;
+  unsigned i;
+  bitmap_iterator bi;
+
+  tos = worklist
+    = (basic_block *) xmalloc (sizeof (basic_block) * (last_basic_block + 1));
+
+  EXECUTE_IF_SET_IN_BITMAP (livein, 0, i, bi)
+    *tos++ = BASIC_BLOCK (i);
+
+  /* Iterate until the worklist is empty.  */
+  while (tos != worklist)
+    {
+      edge e;
+      edge_iterator ei;
+
+      /* Pull a block off the worklist.  */
+      bb = *--tos;
+
+      /* For each predecessor block.  */
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	{
+	  basic_block pred = e->src;
+	  int pred_index = pred->index;
+
+	  /* None of this is necessary for the entry block.  */
+	  if (pred != ENTRY_BLOCK_PTR
+	      && ! bitmap_bit_p (livein, pred_index)
+	      && ! bitmap_bit_p (def_blocks, pred_index))
+	    {
+	      *tos++ = pred;
+	      bitmap_set_bit (livein, pred_index);
+	    }
+	}
+    }
+
+  free (worklist);
+}
+
+
+/* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
+   all statements in basic block BB.  */
+
+static void
+initialize_flags_in_bb (basic_block bb)
+{
+  gimple stmt;
+  gimple_stmt_iterator gsi;
+
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple phi = gsi_stmt (gsi);
+      set_rewrite_uses (phi, false);
+      set_register_defs (phi, false);
+    }
+
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      stmt = gsi_stmt (gsi);
+
+      /* We are going to use the operand cache API, such as
+	 SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST.  The operand
+	 cache for each statement should be up-to-date.  */
+      gcc_assert (!gimple_modified_p (stmt));
+      set_rewrite_uses (stmt, false);
+      set_register_defs (stmt, false);
+    }
+}
+
+/* Mark block BB as interesting for update_ssa.  */
+
+static void
+mark_block_for_update (basic_block bb)
+{
+  gcc_assert (blocks_to_update != NULL);
+  if (bitmap_bit_p (blocks_to_update, bb->index))
+    return;
+  bitmap_set_bit (blocks_to_update, bb->index);
+  initialize_flags_in_bb (bb);
+}
+
+/* Return the set of blocks where variable VAR is defined and the blocks
+   where VAR is live on entry (livein).  If no entry is found in
+   DEF_BLOCKS, a new one is created and returned.  */
+
+static inline struct def_blocks_d *
+get_def_blocks_for (tree var)
+{
+  struct def_blocks_d db, *db_p;
+  void **slot;
+
+  db.var = var;
+  slot = htab_find_slot (def_blocks, (void *) &db, INSERT);
+  if (*slot == NULL)
+    {
+      db_p = XNEW (struct def_blocks_d);
+      db_p->var = var;
+      db_p->def_blocks = BITMAP_ALLOC (NULL);
+      db_p->phi_blocks = BITMAP_ALLOC (NULL);
+      db_p->livein_blocks = BITMAP_ALLOC (NULL);
+      *slot = (void *) db_p;
+    }
+  else
+    db_p = (struct def_blocks_d *) *slot;
+
+  return db_p;
+}
+
+
+/* Mark block BB as the definition site for variable VAR.  PHI_P is true if
+   VAR is defined by a PHI node.  */
+
+static void
+set_def_block (tree var, basic_block bb, bool phi_p)
+{
+  struct def_blocks_d *db_p;
+  enum need_phi_state state;
+
+  state = get_phi_state (var);
+  db_p = get_def_blocks_for (var);
+
+  /* Set the bit corresponding to the block where VAR is defined.  */
+  bitmap_set_bit (db_p->def_blocks, bb->index);
+  if (phi_p)
+    bitmap_set_bit (db_p->phi_blocks, bb->index);
+
+  /* Keep track of whether or not we may need to insert PHI nodes.
+
+     If we are in the UNKNOWN state, then this is the first definition
+     of VAR.  Additionally, we have not seen any uses of VAR yet, so
+     we do not need a PHI node for this variable at this time (i.e.,
+     transition to NEED_PHI_STATE_NO).
+
+     If we are in any other state, then we either have multiple definitions
+     of this variable occurring in different blocks or we saw a use of the
+     variable which was not dominated by the block containing the
+     definition(s).  In this case we may need a PHI node, so enter
+     state NEED_PHI_STATE_MAYBE.  */
+  if (state == NEED_PHI_STATE_UNKNOWN)
+    set_phi_state (var, NEED_PHI_STATE_NO);
+  else
+    set_phi_state (var, NEED_PHI_STATE_MAYBE);
+}
+
+
+/* Mark block BB as having VAR live at the entry to BB.  */
+
+static void
+set_livein_block (tree var, basic_block bb)
+{
+  struct def_blocks_d *db_p;
+  enum need_phi_state state = get_phi_state (var);
+
+  db_p = get_def_blocks_for (var);
+
+  /* Set the bit corresponding to the block where VAR is live in.  */
+  bitmap_set_bit (db_p->livein_blocks, bb->index);
+
+  /* Keep track of whether or not we may need to insert PHI nodes.
+
+     If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
+     by the single block containing the definition(s) of this variable.  If
+     it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
+     NEED_PHI_STATE_MAYBE.  */
+  if (state == NEED_PHI_STATE_NO)
+    {
+      int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
+
+      if (def_block_index == -1
+	  || ! dominated_by_p (CDI_DOMINATORS, bb,
+	                       BASIC_BLOCK (def_block_index)))
+	set_phi_state (var, NEED_PHI_STATE_MAYBE);
+    }
+  else
+    set_phi_state (var, NEED_PHI_STATE_MAYBE);
+}
+
+
+/* Return true if symbol SYM is marked for renaming.  */
+
+static inline bool
+symbol_marked_for_renaming (tree sym)
+{
+  return bitmap_bit_p (syms_to_rename, DECL_UID (sym));
+}
+
+
+/* Return true if NAME is in OLD_SSA_NAMES.  */
+
+static inline bool
+is_old_name (tree name)
+{
+  unsigned ver = SSA_NAME_VERSION (name);
+  return ver < new_ssa_names->n_bits && TEST_BIT (old_ssa_names, ver);
+}
+
+
+/* Return true if NAME is in NEW_SSA_NAMES.  */
+
+static inline bool
+is_new_name (tree name)
+{
+  unsigned ver = SSA_NAME_VERSION (name);
+  return ver < new_ssa_names->n_bits && TEST_BIT (new_ssa_names, ver);
+}
+
+
+/* Hashing and equality functions for REPL_TBL.  */
+
+static hashval_t
+repl_map_hash (const void *p)
+{
+  return htab_hash_pointer ((const void *)((const struct repl_map_d *)p)->name);
+}
+
+static int
+repl_map_eq (const void *p1, const void *p2)
+{
+  return ((const struct repl_map_d *)p1)->name
+	 == ((const struct repl_map_d *)p2)->name;
+}
+
+static void
+repl_map_free (void *p)
+{
+  BITMAP_FREE (((struct repl_map_d *)p)->set);
+  free (p);
+}
+
+
+/* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET).  */
+
+static inline bitmap
+names_replaced_by (tree new_tree)
+{
+  struct repl_map_d m;
+  void **slot;
+
+  m.name = new_tree;
+  slot = htab_find_slot (repl_tbl, (void *) &m, NO_INSERT);
+
+  /* If N was not registered in the replacement table, return NULL.  */
+  if (slot == NULL || *slot == NULL)
+    return NULL;
+
+  return ((struct repl_map_d *) *slot)->set;
+}
+
+
+/* Add OLD to REPL_TBL[NEW_TREE].SET.  */
+
+static inline void
+add_to_repl_tbl (tree new_tree, tree old)
+{
+  struct repl_map_d m, *mp;
+  void **slot;
+
+  m.name = new_tree;
+  slot = htab_find_slot (repl_tbl, (void *) &m, INSERT);
+  if (*slot == NULL)
+    {
+      mp = XNEW (struct repl_map_d);
+      mp->name = new_tree;
+      mp->set = BITMAP_ALLOC (NULL);
+      *slot = (void *) mp;
+    }
+  else
+    mp = (struct repl_map_d *) *slot;
+
+  bitmap_set_bit (mp->set, SSA_NAME_VERSION (old));
+}
+
+
+/* Add a new mapping NEW_TREE -> OLD REPL_TBL.  Every entry N_i in REPL_TBL
+   represents the set of names O_1 ... O_j replaced by N_i.  This is
+   used by update_ssa and its helpers to introduce new SSA names in an
+   already formed SSA web.  */
+
+static void
+add_new_name_mapping (tree new_tree, tree old)
+{
+  timevar_push (TV_TREE_SSA_INCREMENTAL);
+
+  /* OLD and NEW_TREE must be different SSA names for the same symbol.  */
+  gcc_assert (new_tree != old && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
+
+  /* If this mapping is for virtual names, we will need to update
+     virtual operands.  If this is a mapping for .MEM, then we gather
+     the symbols associated with each name.  */
+  if (!is_gimple_reg (new_tree))
+    {
+      tree sym;
+
+      need_to_update_vops_p = true;
+
+      update_ssa_stats.num_virtual_mappings++;
+      update_ssa_stats.num_virtual_symbols++;
+
+      /* Keep counts of virtual mappings and symbols to use in the
+	 virtual mapping heuristic.  If we have large numbers of
+	 virtual mappings for a relatively low number of symbols, it
+	 will make more sense to rename the symbols from scratch.
+	 Otherwise, the insertion of PHI nodes for each of the old
+	 names in these mappings will be very slow.  */
+      sym = SSA_NAME_VAR (new_tree);
+      bitmap_set_bit (update_ssa_stats.virtual_symbols, DECL_UID (sym));
+    }
+
+  /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
+     caller may have created new names since the set was created.  */
+  if (new_ssa_names->n_bits <= num_ssa_names - 1)
+    {
+      unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
+      new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
+      old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
+    }
+
+  /* Update the REPL_TBL table.  */
+  add_to_repl_tbl (new_tree, old);
+
+  /* If OLD had already been registered as a new name, then all the
+     names that OLD replaces should also be replaced by NEW_TREE.  */
+  if (is_new_name (old))
+    bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
+
+  /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
+     respectively.  */
+  SET_BIT (new_ssa_names, SSA_NAME_VERSION (new_tree));
+  SET_BIT (old_ssa_names, SSA_NAME_VERSION (old));
+
+  /* Update mapping counter to use in the virtual mapping heuristic.  */
+  update_ssa_stats.num_total_mappings++;
+
+  timevar_pop (TV_TREE_SSA_INCREMENTAL);
+}
+
+
+/* Call back for walk_dominator_tree used to collect definition sites
+   for every variable in the function.  For every statement S in block
+   BB:
+
+   1- Variables defined by S in the DEFS of S are marked in the bitmap
+      WALK_DATA->GLOBAL_DATA->KILLS.
+
+   2- If S uses a variable VAR and there is no preceding kill of VAR,
+      then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
+
+   This information is used to determine which variables are live
+   across block boundaries to reduce the number of PHI nodes
+   we create.  */
+
+static void
+mark_def_sites (struct dom_walk_data *walk_data, basic_block bb,
+		gimple_stmt_iterator gsi)
+{
+  struct mark_def_sites_global_data *gd;
+  bitmap kills;
+  tree def;
+  gimple stmt;
+  use_operand_p use_p;
+  ssa_op_iter iter;
+
+  /* Since this is the first time that we rewrite the program into SSA
+     form, force an operand scan on every statement.  */
+  stmt = gsi_stmt (gsi);
+  update_stmt (stmt);
+
+  gd = (struct mark_def_sites_global_data *) walk_data->global_data;
+  kills = gd->kills;
+
+  gcc_assert (blocks_to_update == NULL);
+  set_register_defs (stmt, false);
+  set_rewrite_uses (stmt, false);
+
+  /* If a variable is used before being set, then the variable is live
+     across a block boundary, so mark it live-on-entry to BB.  */
+  FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+    {
+      tree sym = USE_FROM_PTR (use_p);
+      gcc_assert (DECL_P (sym));
+      if (!bitmap_bit_p (kills, DECL_UID (sym)))
+	set_livein_block (sym, bb);
+      set_rewrite_uses (stmt, true);
+    }
+  
+  /* Now process the defs.  Mark BB as the definition block and add
+     each def to the set of killed symbols.  */
+  FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+    {
+      gcc_assert (DECL_P (def));
+      set_def_block (def, bb, false);
+      bitmap_set_bit (kills, DECL_UID (def));
+      set_register_defs (stmt, true);
+    }
+
+  /* If we found the statement interesting then also mark the block BB
+     as interesting.  */
+  if (rewrite_uses_p (stmt) || register_defs_p (stmt))
+    SET_BIT (gd->interesting_blocks, bb->index);
+}
+
+/* Structure used by prune_unused_phi_nodes to record bounds of the intervals
+   in the dfs numbering of the dominance tree.  */
+
+struct dom_dfsnum
+{
+  /* Basic block whose index this entry corresponds to.  */
+  unsigned bb_index;
+
+  /* The dfs number of this node.  */
+  unsigned dfs_num;
+};
+
+/* Compares two entries of type struct dom_dfsnum by dfs_num field.  Callback
+   for qsort.  */
+
+static int
+cmp_dfsnum (const void *a, const void *b)
+{
+  const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
+  const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
+
+  return (int) da->dfs_num - (int) db->dfs_num;
+}
+
+/* Among the intervals starting at the N points specified in DEFS, find
+   the one that contains S, and return its bb_index.  */
+
+static unsigned
+find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
+{
+  unsigned f = 0, t = n, m;
+
+  while (t > f + 1)
+    {
+      m = (f + t) / 2;
+      if (defs[m].dfs_num <= s)
+	f = m;
+      else
+	t = m;
+    }
+
+  return defs[f].bb_index;
+}
+
+/* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
+   KILLS is a bitmap of blocks where the value is defined before any use.  */
+
+static void
+prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
+{
+  VEC(int, heap) *worklist;
+  bitmap_iterator bi;
+  unsigned i, b, p, u, top;
+  bitmap live_phis;
+  basic_block def_bb, use_bb;
+  edge e;
+  edge_iterator ei;
+  bitmap to_remove;
+  struct dom_dfsnum *defs;
+  unsigned n_defs, adef;
+
+  if (bitmap_empty_p (uses))
+    {
+      bitmap_clear (phis);
+      return;
+    }
+
+  /* The phi must dominate a use, or an argument of a live phi.  Also, we
+     do not create any phi nodes in def blocks, unless they are also livein.  */
+  to_remove = BITMAP_ALLOC (NULL);
+  bitmap_and_compl (to_remove, kills, uses);
+  bitmap_and_compl_into (phis, to_remove);
+  if (bitmap_empty_p (phis))
+    {
+      BITMAP_FREE (to_remove);
+      return;
+    }
+
+  /* We want to remove the unnecessary phi nodes, but we do not want to compute
+     liveness information, as that may be linear in the size of CFG, and if
+     there are lot of different variables to rewrite, this may lead to quadratic
+     behavior.
+
+     Instead, we basically emulate standard dce.  We put all uses to worklist,
+     then for each of them find the nearest def that dominates them.  If this
+     def is a phi node, we mark it live, and if it was not live before, we
+     add the predecessors of its basic block to the worklist.
+   
+     To quickly locate the nearest def that dominates use, we use dfs numbering
+     of the dominance tree (that is already available in order to speed up
+     queries).  For each def, we have the interval given by the dfs number on
+     entry to and on exit from the corresponding subtree in the dominance tree.
+     The nearest dominator for a given use is the smallest of these intervals
+     that contains entry and exit dfs numbers for the basic block with the use.
+     If we store the bounds for all the uses to an array and sort it, we can
+     locate the nearest dominating def in logarithmic time by binary search.*/
+  bitmap_ior (to_remove, kills, phis);
+  n_defs = bitmap_count_bits (to_remove);
+  defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
+  defs[0].bb_index = 1;
+  defs[0].dfs_num = 0;
+  adef = 1;
+  EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
+    {
+      def_bb = BASIC_BLOCK (i);
+      defs[adef].bb_index = i;
+      defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
+      defs[adef + 1].bb_index = i;
+      defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
+      adef += 2;
+    }
+  BITMAP_FREE (to_remove);
+  gcc_assert (adef == 2 * n_defs + 1);
+  qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
+  gcc_assert (defs[0].bb_index == 1);
+
+  /* Now each DEFS entry contains the number of the basic block to that the
+     dfs number corresponds.  Change them to the number of basic block that
+     corresponds to the interval following the dfs number.  Also, for the
+     dfs_out numbers, increase the dfs number by one (so that it corresponds
+     to the start of the following interval, not to the end of the current
+     one).  We use WORKLIST as a stack.  */
+  worklist = VEC_alloc (int, heap, n_defs + 1);
+  VEC_quick_push (int, worklist, 1);
+  top = 1;
+  n_defs = 1;
+  for (i = 1; i < adef; i++)
+    {
+      b = defs[i].bb_index;
+      if (b == top)
+	{
+	  /* This is a closing element.  Interval corresponding to the top
+	     of the stack after removing it follows.  */
+	  VEC_pop (int, worklist);
+	  top = VEC_index (int, worklist, VEC_length (int, worklist) - 1);
+	  defs[n_defs].bb_index = top;
+	  defs[n_defs].dfs_num = defs[i].dfs_num + 1;
+	}
+      else
+	{
+	  /* Opening element.  Nothing to do, just push it to the stack and move
+	     it to the correct position.  */
+	  defs[n_defs].bb_index = defs[i].bb_index;
+	  defs[n_defs].dfs_num = defs[i].dfs_num;
+	  VEC_quick_push (int, worklist, b);
+	  top = b;
+	}
+
+      /* If this interval starts at the same point as the previous one, cancel
+	 the previous one.  */
+      if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
+	defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
+      else
+	n_defs++;
+    }
+  VEC_pop (int, worklist);
+  gcc_assert (VEC_empty (int, worklist));
+
+  /* Now process the uses.  */
+  live_phis = BITMAP_ALLOC (NULL);
+  EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
+    {
+      VEC_safe_push (int, heap, worklist, i);
+    }
+
+  while (!VEC_empty (int, worklist))
+    {
+      b = VEC_pop (int, worklist);
+      if (b == ENTRY_BLOCK)
+	continue;
+
+      /* If there is a phi node in USE_BB, it is made live.  Otherwise,
+	 find the def that dominates the immediate dominator of USE_BB
+	 (the kill in USE_BB does not dominate the use).  */
+      if (bitmap_bit_p (phis, b))
+	p = b;
+      else
+	{
+	  use_bb = get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (b));
+	  p = find_dfsnum_interval (defs, n_defs,
+				    bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
+	  if (!bitmap_bit_p (phis, p))
+	    continue;
+	}
+
+      /* If the phi node is already live, there is nothing to do.  */
+      if (bitmap_bit_p (live_phis, p))
+	continue;
+
+      /* Mark the phi as live, and add the new uses to the worklist.  */
+      bitmap_set_bit (live_phis, p);
+      def_bb = BASIC_BLOCK (p);
+      FOR_EACH_EDGE (e, ei, def_bb->preds)
+	{
+	  u = e->src->index;
+	  if (bitmap_bit_p (uses, u))
+	    continue;
+
+	  /* In case there is a kill directly in the use block, do not record
+	     the use (this is also necessary for correctness, as we assume that
+	     uses dominated by a def directly in their block have been filtered
+	     out before).  */
+	  if (bitmap_bit_p (kills, u))
+	    continue;
+
+	  bitmap_set_bit (uses, u);
+	  VEC_safe_push (int, heap, worklist, u);
+	}
+    }
+
+  VEC_free (int, heap, worklist);
+  bitmap_copy (phis, live_phis);
+  BITMAP_FREE (live_phis);
+  free (defs);
+}
+
+/* Return the set of blocks where variable VAR is defined and the blocks
+   where VAR is live on entry (livein).  Return NULL, if no entry is
+   found in DEF_BLOCKS.  */
+
+static inline struct def_blocks_d *
+find_def_blocks_for (tree var)
+{
+  struct def_blocks_d dm;
+  dm.var = var;
+  return (struct def_blocks_d *) htab_find (def_blocks, &dm);
+}
+
+
+/* Retrieve or create a default definition for symbol SYM.  */
+
+static inline tree
+get_default_def_for (tree sym)
+{
+  tree ddef = gimple_default_def (cfun, sym);
+
+  if (ddef == NULL_TREE)
+    {
+      ddef = make_ssa_name (sym, gimple_build_nop ());
+      set_default_def (sym, ddef);
+    }
+
+  return ddef;
+}
+
+
+/* Marks phi node PHI in basic block BB for rewrite.  */
+
+static void
+mark_phi_for_rewrite (basic_block bb, gimple phi)
+{
+  gimple_vec phis;
+  unsigned i, idx = bb->index;
+
+  if (rewrite_uses_p (phi))
+    return;
+
+  set_rewrite_uses (phi, true);
+
+  if (!blocks_with_phis_to_rewrite)
+    return;
+
+  bitmap_set_bit (blocks_with_phis_to_rewrite, idx);
+  VEC_reserve (gimple_vec, heap, phis_to_rewrite, last_basic_block + 1);
+  for (i = VEC_length (gimple_vec, phis_to_rewrite); i <= idx; i++)
+    VEC_quick_push (gimple_vec, phis_to_rewrite, NULL);
+
+  phis = VEC_index (gimple_vec, phis_to_rewrite, idx);
+  if (!phis)
+    phis = VEC_alloc (gimple, heap, 10);
+
+  VEC_safe_push (gimple, heap, phis, phi);
+  VEC_replace (gimple_vec, phis_to_rewrite, idx, phis);
+}
+
+
+/* Insert PHI nodes for variable VAR using the iterated dominance
+   frontier given in PHI_INSERTION_POINTS.  If UPDATE_P is true, this
+   function assumes that the caller is incrementally updating the
+   existing SSA form, in which case VAR may be an SSA name instead of
+   a symbol.
+
+   PHI_INSERTION_POINTS is updated to reflect nodes that already had a
+   PHI node for VAR.  On exit, only the nodes that received a PHI node
+   for VAR will be present in PHI_INSERTION_POINTS.  */
+
+static void
+insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
+{
+  unsigned bb_index;
+  edge e;
+  gimple phi;
+  basic_block bb;
+  bitmap_iterator bi;
+  struct def_blocks_d *def_map;
+
+  def_map = find_def_blocks_for (var);
+  gcc_assert (def_map);
+
+  /* Remove the blocks where we already have PHI nodes for VAR.  */
+  bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
+
+  /* Remove obviously useless phi nodes.  */
+  prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
+			  def_map->livein_blocks);
+
+  /* And insert the PHI nodes.  */
+  EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
+    {
+      bb = BASIC_BLOCK (bb_index);
+      if (update_p)
+	mark_block_for_update (bb);
+
+      phi = NULL;
+
+      if (TREE_CODE (var) == SSA_NAME)
+	{
+	  /* If we are rewriting SSA names, create the LHS of the PHI
+	     node by duplicating VAR.  This is useful in the case of
+	     pointers, to also duplicate pointer attributes (alias
+	     information, in particular).  */
+	  edge_iterator ei;
+	  tree new_lhs;
+
+	  gcc_assert (update_p);
+	  phi = create_phi_node (var, bb);
+
+	  new_lhs = duplicate_ssa_name (var, phi);
+	  gimple_phi_set_result (phi, new_lhs);
+	  add_new_name_mapping (new_lhs, var);
+
+	  /* Add VAR to every argument slot of PHI.  We need VAR in
+	     every argument so that rewrite_update_phi_arguments knows
+	     which name is this PHI node replacing.  If VAR is a
+	     symbol marked for renaming, this is not necessary, the
+	     renamer will use the symbol on the LHS to get its
+	     reaching definition.  */
+	  FOR_EACH_EDGE (e, ei, bb->preds)
+	    add_phi_arg (phi, var, e);
+	}
+      else
+	{
+	  gcc_assert (DECL_P (var));
+	  phi = create_phi_node (var, bb);
+	}
+
+      /* Mark this PHI node as interesting for update_ssa.  */
+      set_register_defs (phi, true);
+      mark_phi_for_rewrite (bb, phi);
+    }
+}
+
+
+/* Insert PHI nodes at the dominance frontier of blocks with variable
+   definitions.  DFS contains the dominance frontier information for
+   the flowgraph.  */
+
+static void
+insert_phi_nodes (bitmap *dfs)
+{
+  referenced_var_iterator rvi;
+  tree var;
+
+  timevar_push (TV_TREE_INSERT_PHI_NODES);
+  
+  FOR_EACH_REFERENCED_VAR (var, rvi)
+    {
+      struct def_blocks_d *def_map;
+      bitmap idf;
+
+      def_map = find_def_blocks_for (var);
+      if (def_map == NULL)
+	continue;
+
+      if (get_phi_state (var) != NEED_PHI_STATE_NO)
+	{
+	  idf = compute_idf (def_map->def_blocks, dfs);
+	  insert_phi_nodes_for (var, idf, false);
+	  BITMAP_FREE (idf);
+	}
+    }
+
+  timevar_pop (TV_TREE_INSERT_PHI_NODES);
+}
+
+
+/* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
+   register DEF (an SSA_NAME) to be a new definition for SYM.  */
+
+static void
+register_new_def (tree def, tree sym)
+{
+  tree currdef;
+   
+  /* If this variable is set in a single basic block and all uses are
+     dominated by the set(s) in that single basic block, then there is
+     no reason to record anything for this variable in the block local
+     definition stacks.  Doing so just wastes time and memory.
+
+     This is the same test to prune the set of variables which may
+     need PHI nodes.  So we just use that information since it's already
+     computed and available for us to use.  */
+  if (get_phi_state (sym) == NEED_PHI_STATE_NO)
+    {
+      set_current_def (sym, def);
+      return;
+    }
+
+  currdef = get_current_def (sym);
+
+  /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
+     SSA_NAME_VAR is not necessarily SYM.  In this case, also push SYM
+     in the stack so that we know which symbol is being defined by
+     this SSA name when we unwind the stack.  */
+  if (currdef && !is_gimple_reg (sym))
+    VEC_safe_push (tree, heap, block_defs_stack, sym);
+
+  /* Push the current reaching definition into BLOCK_DEFS_STACK.  This
+     stack is later used by the dominator tree callbacks to restore
+     the reaching definitions for all the variables defined in the
+     block after a recursive visit to all its immediately dominated
+     blocks.  If there is no current reaching definition, then just
+     record the underlying _DECL node.  */
+  VEC_safe_push (tree, heap, block_defs_stack, currdef ? currdef : sym);
+
+  /* Set the current reaching definition for SYM to be DEF.  */
+  set_current_def (sym, def);
+}
+
+
+/* Perform a depth-first traversal of the dominator tree looking for
+   variables to rename.  BB is the block where to start searching.
+   Renaming is a five step process:
+
+   1- Every definition made by PHI nodes at the start of the blocks is
+      registered as the current definition for the corresponding variable.
+
+   2- Every statement in BB is rewritten.  USE and VUSE operands are
+      rewritten with their corresponding reaching definition.  DEF and
+      VDEF targets are registered as new definitions.
+      
+   3- All the PHI nodes in successor blocks of BB are visited.  The
+      argument corresponding to BB is replaced with its current reaching
+      definition.
+
+   4- Recursively rewrite every dominator child block of BB.
+
+   5- Restore (in reverse order) the current reaching definition for every
+      new definition introduced in this block.  This is done so that when
+      we return from the recursive call, all the current reaching
+      definitions are restored to the names that were valid in the
+      dominator parent of BB.  */
+
+/* SSA Rewriting Step 1.  Initialization, create a block local stack
+   of reaching definitions for new SSA names produced in this block
+   (BLOCK_DEFS).  Register new definitions for every PHI node in the
+   block.  */
+
+static void
+rewrite_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			  basic_block bb)
+{
+  gimple phi;
+  gimple_stmt_iterator gsi;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
+
+  /* Mark the unwind point for this block.  */
+  VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
+
+  /* Step 1.  Register new definitions for every PHI node in the block.
+     Conceptually, all the PHI nodes are executed in parallel and each PHI
+     node introduces a new version for the associated variable.  */
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      tree result;
+
+      phi = gsi_stmt (gsi);
+      result = gimple_phi_result (phi);
+      gcc_assert (is_gimple_reg (result));
+      register_new_def (result, SSA_NAME_VAR (result));
+    }
+}
+
+
+/* Return the current definition for variable VAR.  If none is found,
+   create a new SSA name to act as the zeroth definition for VAR.  */
+
+static tree
+get_reaching_def (tree var)
+{
+  tree currdef;
+  
+  /* Lookup the current reaching definition for VAR.  */
+  currdef = get_current_def (var);
+
+  /* If there is no reaching definition for VAR, create and register a
+     default definition for it (if needed).  */
+  if (currdef == NULL_TREE)
+    {
+      tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
+      currdef = get_default_def_for (sym);
+      set_current_def (var, currdef);
+    }
+
+  /* Return the current reaching definition for VAR, or the default
+     definition, if we had to create one.  */
+  return currdef;
+}
+
+
+/* SSA Rewriting Step 2.  Rewrite every variable used in each statement in
+   the block with its immediate reaching definitions.  Update the current
+   definition of a variable when a new real or virtual definition is found.  */
+
+static void
+rewrite_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+	      basic_block bb ATTRIBUTE_UNUSED, gimple_stmt_iterator si)
+{
+  gimple stmt;
+  use_operand_p use_p;
+  def_operand_p def_p;
+  ssa_op_iter iter;
+
+  stmt = gsi_stmt (si);
+
+  /* If mark_def_sites decided that we don't need to rewrite this
+     statement, ignore it.  */
+  gcc_assert (blocks_to_update == NULL);
+  if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Renaming statement ");
+      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  /* Step 1.  Rewrite USES in the statement.  */
+  if (rewrite_uses_p (stmt))
+    FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+      {
+	tree var = USE_FROM_PTR (use_p);
+	gcc_assert (DECL_P (var));
+	SET_USE (use_p, get_reaching_def (var));
+      }
+
+  /* Step 2.  Register the statement's DEF operands.  */
+  if (register_defs_p (stmt))
+    FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
+      {
+	tree var = DEF_FROM_PTR (def_p);
+	gcc_assert (DECL_P (var));
+	SET_DEF (def_p, make_ssa_name (var, stmt));
+	register_new_def (DEF_FROM_PTR (def_p), var);
+      }
+}
+
+
+/* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
+   PHI nodes.  For every PHI node found, add a new argument containing the
+   current reaching definition for the variable and the edge through which
+   that definition is reaching the PHI node.  */
+
+static void
+rewrite_add_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			   basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      gimple phi;
+      gimple_stmt_iterator gsi;
+
+      for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
+	   gsi_next (&gsi))
+	{
+	  tree currdef;
+	  phi = gsi_stmt (gsi);
+	  currdef = get_reaching_def (SSA_NAME_VAR (gimple_phi_result (phi)));
+	  add_phi_arg (phi, currdef, e);
+	}
+    }
+}
+
+
+/* Called after visiting all the statements in basic block BB and all
+   of its dominator children.  Restore CURRDEFS to its original value.  */
+
+static void
+rewrite_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			basic_block bb ATTRIBUTE_UNUSED)
+{
+  /* Restore CURRDEFS to its original state.  */
+  while (VEC_length (tree, block_defs_stack) > 0)
+    {
+      tree tmp = VEC_pop (tree, block_defs_stack);
+      tree saved_def, var;
+
+      if (tmp == NULL_TREE)
+	break;
+
+      if (TREE_CODE (tmp) == SSA_NAME)
+	{
+	  /* If we recorded an SSA_NAME, then make the SSA_NAME the
+	     current definition of its underlying variable.  Note that
+	     if the SSA_NAME is not for a GIMPLE register, the symbol
+	     being defined is stored in the next slot in the stack.
+	     This mechanism is needed because an SSA name for a
+	     non-register symbol may be the definition for more than
+	     one symbol (e.g., SFTs, aliased variables, etc).  */
+	  saved_def = tmp;
+	  var = SSA_NAME_VAR (saved_def);
+	  if (!is_gimple_reg (var))
+	    var = VEC_pop (tree, block_defs_stack);
+	}
+      else
+	{
+	  /* If we recorded anything else, it must have been a _DECL
+	     node and its current reaching definition must have been
+	     NULL.  */
+	  saved_def = NULL;
+	  var = tmp;
+	}
+                                                                                
+      set_current_def (var, saved_def);
+    }
+}
+
+
+/* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE.  */
+
+void
+dump_decl_set (FILE *file, bitmap set)
+{
+  if (set)
+    {
+      bitmap_iterator bi;
+      unsigned i;
+
+      fprintf (file, "{ ");
+
+      EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+	{
+	  print_generic_expr (file, referenced_var (i), 0);
+	  fprintf (file, " ");
+	}
+
+      fprintf (file, "}\n");
+    }
+  else
+    fprintf (file, "NIL\n");
+}
+
+
+/* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE.  */
+
+void
+debug_decl_set (bitmap set)
+{
+  dump_decl_set (stderr, set);
+}
+
+
+/* Dump the renaming stack (block_defs_stack) to FILE.  Traverse the
+   stack up to a maximum of N levels.  If N is -1, the whole stack is
+   dumped.  New levels are created when the dominator tree traversal
+   used for renaming enters a new sub-tree.  */
+
+void
+dump_defs_stack (FILE *file, int n)
+{
+  int i, j;
+
+  fprintf (file, "\n\nRenaming stack");
+  if (n > 0)
+    fprintf (file, " (up to %d levels)", n);
+  fprintf (file, "\n\n");
+
+  i = 1;
+  fprintf (file, "Level %d (current level)\n", i);
+  for (j = (int) VEC_length (tree, block_defs_stack) - 1; j >= 0; j--)
+    {
+      tree name, var;
+      
+      name = VEC_index (tree, block_defs_stack, j);
+      if (name == NULL_TREE)
+	{
+	  i++;
+	  if (n > 0 && i > n)
+	    break;
+	  fprintf (file, "\nLevel %d\n", i);
+	  continue;
+	}
+
+      if (DECL_P (name))
+	{
+	  var = name;
+	  name = NULL_TREE;
+	}
+      else
+	{
+	  var = SSA_NAME_VAR (name);
+	  if (!is_gimple_reg (var))
+	    {
+	      j--;
+	      var = VEC_index (tree, block_defs_stack, j);
+	    }
+	}
+
+      fprintf (file, "    Previous CURRDEF (");
+      print_generic_expr (file, var, 0);
+      fprintf (file, ") = ");
+      if (name)
+	print_generic_expr (file, name, 0);
+      else
+	fprintf (file, "<NIL>");
+      fprintf (file, "\n");
+    }
+}
+
+
+/* Dump the renaming stack (block_defs_stack) to stderr.  Traverse the
+   stack up to a maximum of N levels.  If N is -1, the whole stack is
+   dumped.  New levels are created when the dominator tree traversal
+   used for renaming enters a new sub-tree.  */
+
+void
+debug_defs_stack (int n)
+{
+  dump_defs_stack (stderr, n);
+}
+
+
+/* Dump the current reaching definition of every symbol to FILE.  */
+
+void
+dump_currdefs (FILE *file)
+{
+  referenced_var_iterator i;
+  tree var;
+
+  fprintf (file, "\n\nCurrent reaching definitions\n\n");
+  FOR_EACH_REFERENCED_VAR (var, i)
+    if (syms_to_rename == NULL || bitmap_bit_p (syms_to_rename, DECL_UID (var)))
+      {
+	fprintf (file, "CURRDEF (");
+	print_generic_expr (file, var, 0);
+	fprintf (file, ") = ");
+	if (get_current_def (var))
+	  print_generic_expr (file, get_current_def (var), 0);
+	else
+	  fprintf (file, "<NIL>");
+	fprintf (file, "\n");
+      }
+}
+
+
+/* Dump the current reaching definition of every symbol to stderr.  */
+
+void
+debug_currdefs (void)
+{
+  dump_currdefs (stderr);
+}
+
+
+/* Dump SSA information to FILE.  */
+
+void
+dump_tree_ssa (FILE *file)
+{
+  const char *funcname
+    = lang_hooks.decl_printable_name (current_function_decl, 2);
+
+  fprintf (file, "SSA renaming information for %s\n\n", funcname);
+
+  dump_def_blocks (file);
+  dump_defs_stack (file, -1);
+  dump_currdefs (file);
+  dump_tree_ssa_stats (file);
+}
+
+
+/* Dump SSA information to stderr.  */
+
+void
+debug_tree_ssa (void)
+{
+  dump_tree_ssa (stderr);
+}
+
+
+/* Dump statistics for the hash table HTAB.  */
+
+static void
+htab_statistics (FILE *file, htab_t htab)
+{
+  fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
+	   (long) htab_size (htab),
+	   (long) htab_elements (htab),
+	   htab_collisions (htab));
+}
+
+
+/* Dump SSA statistics on FILE.  */
+
+void
+dump_tree_ssa_stats (FILE *file)
+{
+  if (def_blocks || repl_tbl)
+    fprintf (file, "\nHash table statistics:\n");
+
+  if (def_blocks)
+    {
+      fprintf (file, "    def_blocks:   ");
+      htab_statistics (file, def_blocks);
+    }
+
+  if (repl_tbl)
+    {
+      fprintf (file, "    repl_tbl:     ");
+      htab_statistics (file, repl_tbl);
+    }
+
+  if (def_blocks || repl_tbl)
+    fprintf (file, "\n");
+}
+
+
+/* Dump SSA statistics on stderr.  */
+
+void
+debug_tree_ssa_stats (void)
+{
+  dump_tree_ssa_stats (stderr);
+}
+
+
+/* Hashing and equality functions for DEF_BLOCKS.  */
+
+static hashval_t
+def_blocks_hash (const void *p)
+{
+  return htab_hash_pointer
+	((const void *)((const struct def_blocks_d *)p)->var);
+}
+
+static int
+def_blocks_eq (const void *p1, const void *p2)
+{
+  return ((const struct def_blocks_d *)p1)->var
+	 == ((const struct def_blocks_d *)p2)->var;
+}
+
+
+/* Free memory allocated by one entry in DEF_BLOCKS.  */
+
+static void
+def_blocks_free (void *p)
+{
+  struct def_blocks_d *entry = (struct def_blocks_d *) p;
+  BITMAP_FREE (entry->def_blocks);
+  BITMAP_FREE (entry->phi_blocks);
+  BITMAP_FREE (entry->livein_blocks);
+  free (entry);
+}
+
+
+/* Callback for htab_traverse to dump the DEF_BLOCKS hash table.  */
+
+static int
+debug_def_blocks_r (void **slot, void *data)
+{
+  FILE *file = (FILE *) data;
+  struct def_blocks_d *db_p = (struct def_blocks_d *) *slot;
+  
+  fprintf (file, "VAR: ");
+  print_generic_expr (file, db_p->var, dump_flags);
+  bitmap_print (file, db_p->def_blocks, ", DEF_BLOCKS: { ", "}");
+  bitmap_print (file, db_p->livein_blocks, ", LIVEIN_BLOCKS: { ", "}");
+  bitmap_print (file, db_p->phi_blocks, ", PHI_BLOCKS: { ", "}\n");
+
+  return 1;
+}
+
+
+/* Dump the DEF_BLOCKS hash table on FILE.  */
+
+void
+dump_def_blocks (FILE *file)
+{
+  fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
+  if (def_blocks)
+    htab_traverse (def_blocks, debug_def_blocks_r, file);
+}
+
+
+/* Dump the DEF_BLOCKS hash table on stderr.  */
+
+void
+debug_def_blocks (void)
+{
+  dump_def_blocks (stderr);
+}
+
+
+/* Register NEW_NAME to be the new reaching definition for OLD_NAME.  */
+
+static inline void
+register_new_update_single (tree new_name, tree old_name)
+{
+  tree currdef = get_current_def (old_name);
+
+  /* Push the current reaching definition into BLOCK_DEFS_STACK.
+     This stack is later used by the dominator tree callbacks to
+     restore the reaching definitions for all the variables
+     defined in the block after a recursive visit to all its
+     immediately dominated blocks.  */
+  VEC_reserve (tree, heap, block_defs_stack, 2);
+  VEC_quick_push (tree, block_defs_stack, currdef);
+  VEC_quick_push (tree, block_defs_stack, old_name);
+
+  /* Set the current reaching definition for OLD_NAME to be
+     NEW_NAME.  */
+  set_current_def (old_name, new_name);
+}
+
+
+/* Register NEW_NAME to be the new reaching definition for all the
+   names in OLD_NAMES.  Used by the incremental SSA update routines to
+   replace old SSA names with new ones.  */
+
+static inline void
+register_new_update_set (tree new_name, bitmap old_names)
+{
+  bitmap_iterator bi;
+  unsigned i;
+
+  EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
+    register_new_update_single (new_name, ssa_name (i));
+}
+
+
+/* Initialization of block data structures for the incremental SSA
+   update pass.  Create a block local stack of reaching definitions
+   for new SSA names produced in this block (BLOCK_DEFS).  Register
+   new definitions for every PHI node in the block.  */
+
+static void
+rewrite_update_init_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+		           basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  bool is_abnormal_phi;
+  gimple_stmt_iterator gsi;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\n\nRegistering new PHI nodes in block #%d\n\n",
+	     bb->index);
+
+  /* Mark the unwind point for this block.  */
+  VEC_safe_push (tree, heap, block_defs_stack, NULL_TREE);
+
+  if (!bitmap_bit_p (blocks_to_update, bb->index))
+    return;
+
+  /* Mark the LHS if any of the arguments flows through an abnormal
+     edge.  */
+  is_abnormal_phi = false;
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    if (e->flags & EDGE_ABNORMAL)
+      {
+	is_abnormal_phi = true;
+	break;
+      }
+
+  /* If any of the PHI nodes is a replacement for a name in
+     OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
+     register it as a new definition for its corresponding name.  Also
+     register definitions for names whose underlying symbols are
+     marked for renaming.  */
+  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      tree lhs, lhs_sym;
+      gimple phi = gsi_stmt (gsi);
+
+      if (!register_defs_p (phi))
+	continue;
+      
+      lhs = gimple_phi_result (phi);
+      lhs_sym = SSA_NAME_VAR (lhs);
+
+      if (symbol_marked_for_renaming (lhs_sym))
+	register_new_update_single (lhs, lhs_sym);
+      else
+	{
+
+	  /* If LHS is a new name, register a new definition for all
+	     the names replaced by LHS.  */
+	  if (is_new_name (lhs))
+	    register_new_update_set (lhs, names_replaced_by (lhs));
+	  
+	  /* If LHS is an OLD name, register it as a new definition
+	     for itself.  */
+	  if (is_old_name (lhs))
+	    register_new_update_single (lhs, lhs);
+	}
+
+      if (is_abnormal_phi)
+	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
+    }
+}
+
+
+/* Called after visiting block BB.  Unwind BLOCK_DEFS_STACK to restore
+   the current reaching definition of every name re-written in BB to
+   the original reaching definition before visiting BB.  This
+   unwinding must be done in the opposite order to what is done in
+   register_new_update_set.  */
+
+static void
+rewrite_update_fini_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			   basic_block bb ATTRIBUTE_UNUSED)
+{
+  while (VEC_length (tree, block_defs_stack) > 0)
+    {
+      tree var = VEC_pop (tree, block_defs_stack);
+      tree saved_def;
+      
+      /* NULL indicates the unwind stop point for this block (see
+	 rewrite_update_init_block).  */
+      if (var == NULL)
+	return;
+
+      saved_def = VEC_pop (tree, block_defs_stack);
+      set_current_def (var, saved_def);
+    }
+}
+
+
+/* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
+   it is a symbol marked for renaming, replace it with USE_P's current
+   reaching definition.  */
+
+static inline void
+maybe_replace_use (use_operand_p use_p)
+{
+  tree rdef = NULL_TREE;
+  tree use = USE_FROM_PTR (use_p);
+  tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
+
+  if (symbol_marked_for_renaming (sym))
+    rdef = get_reaching_def (sym);
+  else if (is_old_name (use))
+    rdef = get_reaching_def (use);
+
+  if (rdef && rdef != use)
+    SET_USE (use_p, rdef);
+}
+
+
+/* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
+   or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
+   register it as the current definition for the names replaced by
+   DEF_P.  */
+
+static inline void
+maybe_register_def (def_operand_p def_p, gimple stmt)
+{
+  tree def = DEF_FROM_PTR (def_p);
+  tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
+
+  /* If DEF is a naked symbol that needs renaming, create a new
+     name for it.  */
+  if (symbol_marked_for_renaming (sym))
+    {
+      if (DECL_P (def))
+	{
+	  def = make_ssa_name (def, stmt);
+	  SET_DEF (def_p, def);
+	}
+
+      register_new_update_single (def, sym);
+    }
+  else
+    {
+      /* If DEF is a new name, register it as a new definition
+	 for all the names replaced by DEF.  */
+      if (is_new_name (def))
+	register_new_update_set (def, names_replaced_by (def));
+
+      /* If DEF is an old name, register DEF as a new
+	 definition for itself.  */
+      if (is_old_name (def))
+	register_new_update_single (def, def);
+    }
+}
+
+
+/* Update every variable used in the statement pointed-to by SI.  The
+   statement is assumed to be in SSA form already.  Names in
+   OLD_SSA_NAMES used by SI will be updated to their current reaching
+   definition.  Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
+   will be registered as a new definition for their corresponding name
+   in OLD_SSA_NAMES.  */
+
+static void
+rewrite_update_stmt (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+		     basic_block bb ATTRIBUTE_UNUSED,
+		     gimple_stmt_iterator si)
+{
+  gimple stmt;
+  use_operand_p use_p;
+  def_operand_p def_p;
+  ssa_op_iter iter;
+
+  stmt = gsi_stmt (si);
+
+  gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
+
+  /* Only update marked statements.  */
+  if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
+    return;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Updating SSA information for statement ");
+      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+      fprintf (dump_file, "\n");
+    }
+
+  /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
+     symbol is marked for renaming.  */
+  if (rewrite_uses_p (stmt))
+    {
+      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
+	maybe_replace_use (use_p);
+
+      if (need_to_update_vops_p)
+	FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
+	  maybe_replace_use (use_p);
+    }
+
+  /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
+     Also register definitions for names whose underlying symbol is
+     marked for renaming.  */
+  if (register_defs_p (stmt))
+    {
+      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
+	maybe_register_def (def_p, stmt);
+
+      if (need_to_update_vops_p)
+	FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+	  maybe_register_def (def_p, stmt);
+    }
+}
+
+
+/* Visit all the successor blocks of BB looking for PHI nodes.  For
+   every PHI node found, check if any of its arguments is in
+   OLD_SSA_NAMES.  If so, and if the argument has a current reaching
+   definition, replace it.  */
+
+static void
+rewrite_update_phi_arguments (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+			      basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  unsigned i;
+
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      gimple phi;
+      gimple_vec phis;
+
+      if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
+	continue;
+     
+      phis = VEC_index (gimple_vec, phis_to_rewrite, e->dest->index);
+      for (i = 0; VEC_iterate (gimple, phis, i, phi); i++)
+	{
+	  tree arg, lhs_sym;
+	  use_operand_p arg_p;
+
+  	  gcc_assert (rewrite_uses_p (phi));
+
+	  arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+	  arg = USE_FROM_PTR (arg_p);
+
+	  if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
+	    continue;
+
+	  lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
+
+	  if (arg == NULL_TREE)
+	    {
+	      /* When updating a PHI node for a recently introduced
+		 symbol we may find NULL arguments.  That's why we
+		 take the symbol from the LHS of the PHI node.  */
+	      SET_USE (arg_p, get_reaching_def (lhs_sym));
+	    }
+	  else
+	    {
+	      tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
+
+	      if (symbol_marked_for_renaming (sym))
+		SET_USE (arg_p, get_reaching_def (sym));
+	      else if (is_old_name (arg))
+		SET_USE (arg_p, get_reaching_def (arg));
+	    }
+
+	  if (e->flags & EDGE_ABNORMAL)
+	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
+	}
+    }
+}
+
+
+/* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
+   form.  
+
+   ENTRY indicates the block where to start.  Every block dominated by
+      ENTRY will be rewritten.
+
+   WHAT indicates what actions will be taken by the renamer (see enum
+      rewrite_mode).
+
+   BLOCKS are the set of interesting blocks for the dominator walker
+      to process.  If this set is NULL, then all the nodes dominated
+      by ENTRY are walked.  Otherwise, blocks dominated by ENTRY that
+      are not present in BLOCKS are ignored.  */
+
+static void
+rewrite_blocks (basic_block entry, enum rewrite_mode what, sbitmap blocks)
+{
+  struct dom_walk_data walk_data;
+  
+  /* Rewrite all the basic blocks in the program.  */
+  timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
+
+  /* Setup callbacks for the generic dominator tree walker.  */
+  memset (&walk_data, 0, sizeof (walk_data));
+
+  walk_data.dom_direction = CDI_DOMINATORS;
+  walk_data.interesting_blocks = blocks;
+
+  if (what == REWRITE_ALL)
+    walk_data.before_dom_children_before_stmts = rewrite_initialize_block;
+  else
+    walk_data.before_dom_children_before_stmts = rewrite_update_init_block;
+
+  if (what == REWRITE_ALL)
+    walk_data.before_dom_children_walk_stmts = rewrite_stmt;
+  else if (what == REWRITE_UPDATE)
+    walk_data.before_dom_children_walk_stmts = rewrite_update_stmt;
+  else
+    gcc_unreachable ();
+
+  if (what == REWRITE_ALL)
+    walk_data.before_dom_children_after_stmts = rewrite_add_phi_arguments;
+  else if (what == REWRITE_UPDATE)
+    walk_data.before_dom_children_after_stmts = rewrite_update_phi_arguments;
+  else
+    gcc_unreachable ();
+  
+  if (what == REWRITE_ALL)
+    walk_data.after_dom_children_after_stmts =  rewrite_finalize_block;
+  else if (what == REWRITE_UPDATE)
+    walk_data.after_dom_children_after_stmts = rewrite_update_fini_block;
+  else
+    gcc_unreachable ();
+
+  block_defs_stack = VEC_alloc (tree, heap, 10);
+
+  /* Initialize the dominator walker.  */
+  init_walk_dominator_tree (&walk_data);
+
+  /* Recursively walk the dominator tree rewriting each statement in
+     each basic block.  */
+  walk_dominator_tree (&walk_data, entry);
+
+  /* Finalize the dominator walker.  */
+  fini_walk_dominator_tree (&walk_data);
+
+  /* Debugging dumps.  */
+  if (dump_file && (dump_flags & TDF_STATS))
+    {
+      dump_dfa_stats (dump_file);
+      if (def_blocks)
+	dump_tree_ssa_stats (dump_file);
+    }
+  
+  VEC_free (tree, heap, block_defs_stack);
+
+  timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
+}
+
+
+/* Block initialization routine for mark_def_sites.  Clear the 
+   KILLS bitmap at the start of each block.  */
+
+static void
+mark_def_sites_initialize_block (struct dom_walk_data *walk_data,
+				 basic_block bb ATTRIBUTE_UNUSED)
+{
+  struct mark_def_sites_global_data *gd;
+  gd = (struct mark_def_sites_global_data *) walk_data->global_data;
+  bitmap_clear (gd->kills);
+}
+
+
+/* Mark the definition site blocks for each variable, so that we know
+   where the variable is actually live.
+
+   INTERESTING_BLOCKS will be filled in with all the blocks that
+      should be processed by the renamer.  It is assumed to be
+      initialized and zeroed by the caller.  */
+
+static void
+mark_def_site_blocks (sbitmap interesting_blocks)
+{
+  struct dom_walk_data walk_data;
+  struct mark_def_sites_global_data mark_def_sites_global_data;
+
+  /* Setup callbacks for the generic dominator tree walker to find and
+     mark definition sites.  */
+  walk_data.walk_stmts_backward = false;
+  walk_data.dom_direction = CDI_DOMINATORS;
+  walk_data.initialize_block_local_data = NULL;
+  walk_data.before_dom_children_before_stmts = mark_def_sites_initialize_block;
+  walk_data.before_dom_children_walk_stmts = mark_def_sites;
+  walk_data.before_dom_children_after_stmts = NULL; 
+  walk_data.after_dom_children_before_stmts =  NULL;
+  walk_data.after_dom_children_walk_stmts =  NULL;
+  walk_data.after_dom_children_after_stmts =  NULL;
+  walk_data.interesting_blocks = NULL;
+
+  /* Notice that this bitmap is indexed using variable UIDs, so it must be
+     large enough to accommodate all the variables referenced in the
+     function, not just the ones we are renaming.  */
+  mark_def_sites_global_data.kills = BITMAP_ALLOC (NULL);
+
+  /* Create the set of interesting blocks that will be filled by
+     mark_def_sites.  */
+  mark_def_sites_global_data.interesting_blocks = interesting_blocks;
+  walk_data.global_data = &mark_def_sites_global_data;
+
+  /* We do not have any local data.  */
+  walk_data.block_local_data_size = 0;
+
+  /* Initialize the dominator walker.  */
+  init_walk_dominator_tree (&walk_data);
+
+  /* Recursively walk the dominator tree.  */
+  walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+
+  /* Finalize the dominator walker.  */
+  fini_walk_dominator_tree (&walk_data);
+
+  /* We no longer need this bitmap, clear and free it.  */
+  BITMAP_FREE (mark_def_sites_global_data.kills);
+}
+
+
+/* Initialize internal data needed during renaming.  */
+
+static void
+init_ssa_renamer (void)
+{
+  tree var;
+  referenced_var_iterator rvi;
+
+  cfun->gimple_df->in_ssa_p = false;
+
+  /* Allocate memory for the DEF_BLOCKS hash table.  */
+  gcc_assert (def_blocks == NULL);
+  def_blocks = htab_create (num_referenced_vars, def_blocks_hash,
+                            def_blocks_eq, def_blocks_free);
+
+  FOR_EACH_REFERENCED_VAR(var, rvi)
+    set_current_def (var, NULL_TREE);
+}
+
+
+/* Deallocate internal data structures used by the renamer.  */
+
+static void
+fini_ssa_renamer (void)
+{
+  if (def_blocks)
+    {
+      htab_delete (def_blocks);
+      def_blocks = NULL;
+    }
+
+  cfun->gimple_df->in_ssa_p = true;
+}
+
+/* Main entry point into the SSA builder.  The renaming process
+   proceeds in four main phases:
+
+   1- Compute dominance frontier and immediate dominators, needed to
+      insert PHI nodes and rename the function in dominator tree
+      order.
+
+   2- Find and mark all the blocks that define variables
+      (mark_def_site_blocks).
+
+   3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
+
+   4- Rename all the blocks (rewrite_blocks) and statements in the program.
+
+   Steps 3 and 4 are done using the dominator tree walker
+   (walk_dominator_tree).  */
+
+static unsigned int
+rewrite_into_ssa (void)
+{
+  bitmap *dfs;
+  basic_block bb;
+  sbitmap interesting_blocks;
+  
+  timevar_push (TV_TREE_SSA_OTHER);
+
+  /* Initialize operand data structures.  */
+  init_ssa_operands ();
+
+  /* Initialize internal data needed by the renamer.  */
+  init_ssa_renamer ();
+
+  /* Initialize the set of interesting blocks.  The callback
+     mark_def_sites will add to this set those blocks that the renamer
+     should process.  */
+  interesting_blocks = sbitmap_alloc (last_basic_block);
+  sbitmap_zero (interesting_blocks);
+
+  /* Initialize dominance frontier.  */
+  dfs = XNEWVEC (bitmap, last_basic_block);
+  FOR_EACH_BB (bb)
+    dfs[bb->index] = BITMAP_ALLOC (NULL);
+
+  /* 1- Compute dominance frontiers.  */
+  calculate_dominance_info (CDI_DOMINATORS);
+  compute_dominance_frontiers (dfs);
+
+  /* 2- Find and mark definition sites.  */
+  mark_def_site_blocks (interesting_blocks);
+
+  /* 3- Insert PHI nodes at dominance frontiers of definition blocks.  */
+  insert_phi_nodes (dfs);
+
+  /* 4- Rename all the blocks.  */
+  rewrite_blocks (ENTRY_BLOCK_PTR, REWRITE_ALL, interesting_blocks);
+
+  /* Free allocated memory.  */
+  FOR_EACH_BB (bb)
+    BITMAP_FREE (dfs[bb->index]);
+  free (dfs);
+  sbitmap_free (interesting_blocks);
+
+  fini_ssa_renamer ();
+
+  timevar_pop (TV_TREE_SSA_OTHER);
+  return 0;
+}
+
+
+struct gimple_opt_pass pass_build_ssa = 
+{
+ {
+  GIMPLE_PASS,
+  "ssa",				/* name */
+  NULL,					/* gate */
+  rewrite_into_ssa,			/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  0,					/* tv_id */
+  PROP_cfg | PROP_referenced_vars,	/* properties_required */
+  PROP_ssa,				/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func
+    | TODO_verify_ssa
+    | TODO_remove_unused_locals		/* todo_flags_finish */
+ }
+};
+
+
+/* Mark the definition of VAR at STMT and BB as interesting for the
+   renamer.  BLOCKS is the set of blocks that need updating.  */
+
+static void
+mark_def_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
+{
+  gcc_assert (bitmap_bit_p (blocks_to_update, bb->index));
+  set_register_defs (stmt, true);
+
+  if (insert_phi_p)
+    {
+      bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
+
+      set_def_block (var, bb, is_phi_p);
+
+      /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
+	 site for both itself and all the old names replaced by it.  */
+      if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
+	{
+	  bitmap_iterator bi;
+	  unsigned i;
+	  bitmap set = names_replaced_by (var);
+	  if (set)
+	    EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+	      set_def_block (ssa_name (i), bb, is_phi_p);
+	}
+    }
+}
+
+
+/* Mark the use of VAR at STMT and BB as interesting for the
+   renamer.  INSERT_PHI_P is true if we are going to insert new PHI
+   nodes.  */
+
+static inline void
+mark_use_interesting (tree var, gimple stmt, basic_block bb, bool insert_phi_p)
+{
+  basic_block def_bb = gimple_bb (stmt);
+
+  mark_block_for_update (def_bb);
+  mark_block_for_update (bb);
+
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    mark_phi_for_rewrite (def_bb, stmt);
+  else
+    set_rewrite_uses (stmt, true);
+
+  /* If VAR has not been defined in BB, then it is live-on-entry
+     to BB.  Note that we cannot just use the block holding VAR's
+     definition because if VAR is one of the names in OLD_SSA_NAMES,
+     it will have several definitions (itself and all the names that
+     replace it).  */
+  if (insert_phi_p)
+    {
+      struct def_blocks_d *db_p = get_def_blocks_for (var);
+      if (!bitmap_bit_p (db_p->def_blocks, bb->index))
+	set_livein_block (var, bb);
+    }
+}
+
+
+/* Do a dominator walk starting at BB processing statements that
+   reference symbols in SYMS_TO_RENAME.  This is very similar to
+   mark_def_sites, but the scan handles statements whose operands may
+   already be SSA names.
+
+   If INSERT_PHI_P is true, mark those uses as live in the
+   corresponding block.  This is later used by the PHI placement
+   algorithm to make PHI pruning decisions.
+
+   FIXME.  Most of this would be unnecessary if we could associate a
+	   symbol to all the SSA names that reference it.  But that
+	   sounds like it would be expensive to maintain.  Still, it
+	   would be interesting to see if it makes better sense to do
+	   that.  */
+
+static void
+prepare_block_for_update (basic_block bb, bool insert_phi_p)
+{
+  basic_block son;
+  gimple_stmt_iterator si;
+  edge e;
+  edge_iterator ei;
+
+  mark_block_for_update (bb);
+
+  /* Process PHI nodes marking interesting those that define or use
+     the symbols that we are interested in.  */
+  for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
+    {
+      gimple phi = gsi_stmt (si);
+      tree lhs_sym, lhs = gimple_phi_result (phi);
+
+      lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
+
+      if (!symbol_marked_for_renaming (lhs_sym))
+	continue;
+
+      mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
+
+      /* Mark the uses in phi nodes as interesting.  It would be more correct
+	 to process the arguments of the phi nodes of the successor edges of
+	 BB at the end of prepare_block_for_update, however, that turns out
+	 to be significantly more expensive.  Doing it here is conservatively
+	 correct -- it may only cause us to believe a value to be live in a
+	 block that also contains its definition, and thus insert a few more
+	 phi nodes for it.  */
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
+    }
+
+  /* Process the statements.  */
+  for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+    {
+      gimple stmt;
+      ssa_op_iter i;
+      use_operand_p use_p;
+      def_operand_p def_p;
+      
+      stmt = gsi_stmt (si);
+
+      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
+	{
+	  tree use = USE_FROM_PTR (use_p);
+	  tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
+	  if (symbol_marked_for_renaming (sym))
+	    mark_use_interesting (sym, stmt, bb, insert_phi_p);
+	}
+
+      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_ALL_DEFS)
+	{
+	  tree def = DEF_FROM_PTR (def_p);
+	  tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
+	  if (symbol_marked_for_renaming (sym))
+	    mark_def_interesting (sym, stmt, bb, insert_phi_p);
+	}
+    }
+
+  /* Now visit all the blocks dominated by BB.  */
+  for (son = first_dom_son (CDI_DOMINATORS, bb);
+       son;
+       son = next_dom_son (CDI_DOMINATORS, son))
+    prepare_block_for_update (son, insert_phi_p);
+}
+
+
+/* Helper for prepare_names_to_update.  Mark all the use sites for
+   NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
+   prepare_names_to_update.  */
+
+static void
+prepare_use_sites_for (tree name, bool insert_phi_p)
+{
+  use_operand_p use_p;
+  imm_use_iterator iter;
+
+  FOR_EACH_IMM_USE_FAST (use_p, iter, name)
+    {
+      gimple stmt = USE_STMT (use_p);
+      basic_block bb = gimple_bb (stmt);
+
+      if (gimple_code (stmt) == GIMPLE_PHI)
+	{
+	  int ix = PHI_ARG_INDEX_FROM_USE (use_p);
+	  edge e = gimple_phi_arg_edge (stmt, ix);
+	  mark_use_interesting (name, stmt, e->src, insert_phi_p);
+	}
+      else
+	{
+	  /* For regular statements, mark this as an interesting use
+	     for NAME.  */
+	  mark_use_interesting (name, stmt, bb, insert_phi_p);
+	}
+    }
+}
+
+
+/* Helper for prepare_names_to_update.  Mark the definition site for
+   NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
+   prepare_names_to_update.  */
+
+static void
+prepare_def_site_for (tree name, bool insert_phi_p)
+{
+  gimple stmt;
+  basic_block bb;
+
+  gcc_assert (names_to_release == NULL
+	      || !bitmap_bit_p (names_to_release, SSA_NAME_VERSION (name)));
+
+  stmt = SSA_NAME_DEF_STMT (name);
+  bb = gimple_bb (stmt);
+  if (bb)
+    {
+      gcc_assert (bb->index < last_basic_block);
+      mark_block_for_update (bb);
+      mark_def_interesting (name, stmt, bb, insert_phi_p);
+    }
+}
+
+
+/* Mark definition and use sites of names in NEW_SSA_NAMES and
+   OLD_SSA_NAMES.  INSERT_PHI_P is true if the caller wants to insert
+   PHI nodes for newly created names.  */
+
+static void
+prepare_names_to_update (bool insert_phi_p)
+{
+  unsigned i = 0;
+  bitmap_iterator bi;
+  sbitmap_iterator sbi;
+
+  /* If a name N from NEW_SSA_NAMES is also marked to be released,
+     remove it from NEW_SSA_NAMES so that we don't try to visit its
+     defining basic block (which most likely doesn't exist).  Notice
+     that we cannot do the same with names in OLD_SSA_NAMES because we
+     want to replace existing instances.  */
+  if (names_to_release)
+    EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
+      RESET_BIT (new_ssa_names, i);
+
+  /* First process names in NEW_SSA_NAMES.  Otherwise, uses of old
+     names may be considered to be live-in on blocks that contain
+     definitions for their replacements.  */
+  EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
+    prepare_def_site_for (ssa_name (i), insert_phi_p);
+
+  /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
+     OLD_SSA_NAMES, but we have to ignore its definition site.  */
+  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
+    {
+      if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
+	prepare_def_site_for (ssa_name (i), insert_phi_p);
+      prepare_use_sites_for (ssa_name (i), insert_phi_p);
+    }
+}
+
+
+/* Dump all the names replaced by NAME to FILE.  */
+
+void
+dump_names_replaced_by (FILE *file, tree name)
+{
+  unsigned i;
+  bitmap old_set;
+  bitmap_iterator bi;
+
+  print_generic_expr (file, name, 0);
+  fprintf (file, " -> { ");
+
+  old_set = names_replaced_by (name);
+  EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
+    {
+      print_generic_expr (file, ssa_name (i), 0);
+      fprintf (file, " ");
+    }
+
+  fprintf (file, "}\n");
+}
+
+
+/* Dump all the names replaced by NAME to stderr.  */
+
+void
+debug_names_replaced_by (tree name)
+{
+  dump_names_replaced_by (stderr, name);
+}
+
+
+/* Dump SSA update information to FILE.  */
+
+void
+dump_update_ssa (FILE *file)
+{
+  unsigned i = 0;
+  bitmap_iterator bi;
+
+  if (!need_ssa_update_p ())
+    return;
+
+  if (new_ssa_names && sbitmap_first_set_bit (new_ssa_names) >= 0)
+    {
+      sbitmap_iterator sbi;
+
+      fprintf (file, "\nSSA replacement table\n");
+      fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
+	             "O_1, ..., O_j\n\n");
+
+      EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
+	dump_names_replaced_by (file, ssa_name (i));
+
+      fprintf (file, "\n");
+      fprintf (file, "Number of virtual NEW -> OLD mappings: %7u\n",
+	       update_ssa_stats.num_virtual_mappings);
+      fprintf (file, "Number of real NEW -> OLD mappings:    %7u\n",
+	       update_ssa_stats.num_total_mappings
+	       - update_ssa_stats.num_virtual_mappings);
+      fprintf (file, "Number of total NEW -> OLD mappings:   %7u\n",
+	       update_ssa_stats.num_total_mappings);
+
+      fprintf (file, "\nNumber of virtual symbols: %u\n",
+	       update_ssa_stats.num_virtual_symbols);
+    }
+
+  if (syms_to_rename && !bitmap_empty_p (syms_to_rename))
+    {
+      fprintf (file, "\n\nSymbols to be put in SSA form\n\n");
+      dump_decl_set (file, syms_to_rename);
+    }
+
+  if (names_to_release && !bitmap_empty_p (names_to_release))
+    {
+      fprintf (file, "\n\nSSA names to release after updating the SSA web\n\n");
+      EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
+	{
+	  print_generic_expr (file, ssa_name (i), 0);
+	  fprintf (file, " ");
+	}
+    }
+
+  fprintf (file, "\n\n");
+}
+
+
+/* Dump SSA update information to stderr.  */
+
+void
+debug_update_ssa (void)
+{
+  dump_update_ssa (stderr);
+}
+
+
+/* Initialize data structures used for incremental SSA updates.  */
+
+static void
+init_update_ssa (void)
+{
+  /* Reserve more space than the current number of names.  The calls to
+     add_new_name_mapping are typically done after creating new SSA
+     names, so we'll need to reallocate these arrays.  */
+  old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
+  sbitmap_zero (old_ssa_names);
+
+  new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
+  sbitmap_zero (new_ssa_names);
+
+  repl_tbl = htab_create (20, repl_map_hash, repl_map_eq, repl_map_free);
+  need_to_initialize_update_ssa_p = false;
+  need_to_update_vops_p = false;
+  syms_to_rename = BITMAP_ALLOC (NULL);
+  regs_to_rename = BITMAP_ALLOC (NULL);
+  mem_syms_to_rename = BITMAP_ALLOC (NULL);
+  names_to_release = NULL;
+  memset (&update_ssa_stats, 0, sizeof (update_ssa_stats));
+  update_ssa_stats.virtual_symbols = BITMAP_ALLOC (NULL);
+}
+
+
+/* Deallocate data structures used for incremental SSA updates.  */
+
+void
+delete_update_ssa (void)
+{
+  unsigned i;
+  bitmap_iterator bi;
+
+  sbitmap_free (old_ssa_names);
+  old_ssa_names = NULL;
+
+  sbitmap_free (new_ssa_names);
+  new_ssa_names = NULL;
+
+  htab_delete (repl_tbl);
+  repl_tbl = NULL;
+
+  need_to_initialize_update_ssa_p = true;
+  need_to_update_vops_p = false;
+  BITMAP_FREE (syms_to_rename);
+  BITMAP_FREE (regs_to_rename);
+  BITMAP_FREE (mem_syms_to_rename);
+  BITMAP_FREE (update_ssa_stats.virtual_symbols);
+
+  if (names_to_release)
+    {
+      EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
+	release_ssa_name (ssa_name (i));
+      BITMAP_FREE (names_to_release);
+    }
+
+  clear_ssa_name_info ();
+
+  fini_ssa_renamer ();
+
+  if (blocks_with_phis_to_rewrite)
+    EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
+      {
+	gimple_vec phis = VEC_index (gimple_vec, phis_to_rewrite, i);
+
+	VEC_free (gimple, heap, phis);
+	VEC_replace (gimple_vec, phis_to_rewrite, i, NULL);
+      }
+
+  BITMAP_FREE (blocks_with_phis_to_rewrite);
+  BITMAP_FREE (blocks_to_update);
+}
+
+
+/* Create a new name for OLD_NAME in statement STMT and replace the
+   operand pointed to by DEF_P with the newly created name.  Return
+   the new name and register the replacement mapping <NEW, OLD> in
+   update_ssa's tables.  */
+
+tree
+create_new_def_for (tree old_name, gimple stmt, def_operand_p def)
+{
+  tree new_name = duplicate_ssa_name (old_name, stmt);
+
+  SET_DEF (def, new_name);
+
+  if (gimple_code (stmt) == GIMPLE_PHI)
+    {
+      edge e;
+      edge_iterator ei;
+      basic_block bb = gimple_bb (stmt);
+
+      /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
+      FOR_EACH_EDGE (e, ei, bb->preds)
+	if (e->flags & EDGE_ABNORMAL)
+	  {
+	    SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = 1;
+	    break;
+	  }
+    }
+
+  register_new_name_mapping (new_name, old_name);
+
+  /* For the benefit of passes that will be updating the SSA form on
+     their own, set the current reaching definition of OLD_NAME to be
+     NEW_NAME.  */
+  set_current_def (old_name, new_name);
+
+  return new_name;
+}
+
+
+/* Register name NEW to be a replacement for name OLD.  This function
+   must be called for every replacement that should be performed by
+   update_ssa.  */
+
+void
+register_new_name_mapping (tree new_Tree ATTRIBUTE_UNUSED, tree old ATTRIBUTE_UNUSED)
+{
+  if (need_to_initialize_update_ssa_p)
+    init_update_ssa ();
+
+  add_new_name_mapping (new_Tree, old);
+}
+
+
+/* Register symbol SYM to be renamed by update_ssa.  */
+
+void
+mark_sym_for_renaming (tree sym)
+{
+  if (need_to_initialize_update_ssa_p)
+    init_update_ssa ();
+
+  bitmap_set_bit (syms_to_rename, DECL_UID (sym));
+
+  if (!is_gimple_reg (sym))
+    {
+      need_to_update_vops_p = true;
+      if (memory_partition (sym))
+	bitmap_set_bit (syms_to_rename, DECL_UID (memory_partition (sym)));
+    }
+}
+
+
+/* Register all the symbols in SET to be renamed by update_ssa.  */
+
+void
+mark_set_for_renaming (bitmap set)
+{
+  bitmap_iterator bi;
+  unsigned i;
+
+  if (set == NULL || bitmap_empty_p (set))
+    return;
+
+  if (need_to_initialize_update_ssa_p)
+    init_update_ssa ();
+
+  EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
+    mark_sym_for_renaming (referenced_var (i));
+}
+
+
+/* Return true if there is any work to be done by update_ssa.  */
+
+bool
+need_ssa_update_p (void)
+{
+  return syms_to_rename || old_ssa_names || new_ssa_names;
+}
+
+/* Return true if SSA name mappings have been registered for SSA updating.  */
+
+bool
+name_mappings_registered_p (void)
+{
+  return repl_tbl && htab_elements (repl_tbl) > 0;
+}
+
+/* Return true if name N has been registered in the replacement table.  */
+
+bool
+name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
+{
+  if (!need_ssa_update_p ())
+    return false;
+
+  return is_new_name (n)
+         || is_old_name (n)
+	 || symbol_marked_for_renaming (SSA_NAME_VAR (n));
+}
+
+
+/* Return the set of all the SSA names marked to be replaced.  */
+
+bitmap
+ssa_names_to_replace (void)
+{
+  unsigned i = 0;
+  bitmap ret;
+  sbitmap_iterator sbi;
+  
+  ret = BITMAP_ALLOC (NULL);
+  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
+    bitmap_set_bit (ret, i);
+
+  return ret;
+}
+
+
+/* Mark NAME to be released after update_ssa has finished.  */
+
+void
+release_ssa_name_after_update_ssa (tree name)
+{
+  gcc_assert (!need_to_initialize_update_ssa_p);
+
+  if (names_to_release == NULL)
+    names_to_release = BITMAP_ALLOC (NULL);
+
+  bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
+}
+
+
+/* Insert new PHI nodes to replace VAR.  DFS contains dominance
+   frontier information.  BLOCKS is the set of blocks to be updated.
+
+   This is slightly different than the regular PHI insertion
+   algorithm.  The value of UPDATE_FLAGS controls how PHI nodes for
+   real names (i.e., GIMPLE registers) are inserted:
+ 
+   - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
+     nodes inside the region affected by the block that defines VAR
+     and the blocks that define all its replacements.  All these
+     definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
+
+     First, we compute the entry point to the region (ENTRY).  This is
+     given by the nearest common dominator to all the definition
+     blocks. When computing the iterated dominance frontier (IDF), any
+     block not strictly dominated by ENTRY is ignored.
+
+     We then call the standard PHI insertion algorithm with the pruned
+     IDF.
+
+   - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
+     names is not pruned.  PHI nodes are inserted at every IDF block.  */
+
+static void
+insert_updated_phi_nodes_for (tree var, bitmap *dfs, bitmap blocks,
+                              unsigned update_flags)
+{
+  basic_block entry;
+  struct def_blocks_d *db;
+  bitmap idf, pruned_idf;
+  bitmap_iterator bi;
+  unsigned i;
+
+#if defined ENABLE_CHECKING
+  if (TREE_CODE (var) == SSA_NAME)
+    gcc_assert (is_old_name (var));
+  else
+    gcc_assert (symbol_marked_for_renaming (var));
+#endif
+
+  /* Get all the definition sites for VAR.  */
+  db = find_def_blocks_for (var);
+
+  /* No need to do anything if there were no definitions to VAR.  */
+  if (db == NULL || bitmap_empty_p (db->def_blocks))
+    return;
+
+  /* Compute the initial iterated dominance frontier.  */
+  idf = compute_idf (db->def_blocks, dfs);
+  pruned_idf = BITMAP_ALLOC (NULL);
+
+  if (TREE_CODE (var) == SSA_NAME)
+    {
+      if (update_flags == TODO_update_ssa)
+	{
+	  /* If doing regular SSA updates for GIMPLE registers, we are
+	     only interested in IDF blocks dominated by the nearest
+	     common dominator of all the definition blocks.  */
+	  entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
+						    db->def_blocks);
+	  if (entry != ENTRY_BLOCK_PTR)
+	    EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
+	      if (BASIC_BLOCK (i) != entry
+		  && dominated_by_p (CDI_DOMINATORS, BASIC_BLOCK (i), entry))
+		bitmap_set_bit (pruned_idf, i);
+	}
+      else
+	{
+	  /* Otherwise, do not prune the IDF for VAR.  */
+	  gcc_assert (update_flags == TODO_update_ssa_full_phi);
+	  bitmap_copy (pruned_idf, idf);
+	}
+    }
+  else
+    {
+      /* Otherwise, VAR is a symbol that needs to be put into SSA form
+	 for the first time, so we need to compute the full IDF for
+	 it.  */
+      bitmap_copy (pruned_idf, idf);
+    }
+
+  if (!bitmap_empty_p (pruned_idf))
+    {
+      /* Make sure that PRUNED_IDF blocks and all their feeding blocks
+	 are included in the region to be updated.  The feeding blocks
+	 are important to guarantee that the PHI arguments are renamed
+	 properly.  */
+
+      /* FIXME, this is not needed if we are updating symbols.  We are
+	 already starting at the ENTRY block anyway.  */
+      bitmap_ior_into (blocks, pruned_idf);
+      EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
+	{
+	  edge e;
+	  edge_iterator ei;
+	  basic_block bb = BASIC_BLOCK (i);
+
+	  FOR_EACH_EDGE (e, ei, bb->preds)
+	    if (e->src->index >= 0)
+	      bitmap_set_bit (blocks, e->src->index);
+	}
+
+      insert_phi_nodes_for (var, pruned_idf, true);
+    }
+
+  BITMAP_FREE (pruned_idf);
+  BITMAP_FREE (idf);
+}
+
+
+/* Heuristic to determine whether SSA name mappings for virtual names
+   should be discarded and their symbols rewritten from scratch.  When
+   there is a large number of mappings for virtual names, the
+   insertion of PHI nodes for the old names in the mappings takes
+   considerable more time than if we inserted PHI nodes for the
+   symbols instead.
+
+   Currently the heuristic takes these stats into account:
+
+   	- Number of mappings for virtual SSA names.
+	- Number of distinct virtual symbols involved in those mappings.
+
+   If the number of virtual mappings is much larger than the number of
+   virtual symbols, then it will be faster to compute PHI insertion
+   spots for the symbols.  Even if this involves traversing the whole
+   CFG, which is what happens when symbols are renamed from scratch.  */
+
+static bool
+switch_virtuals_to_full_rewrite_p (void)
+{
+  if (update_ssa_stats.num_virtual_mappings < (unsigned) MIN_VIRTUAL_MAPPINGS)
+    return false;
+
+  if (update_ssa_stats.num_virtual_mappings
+      > (unsigned) VIRTUAL_MAPPINGS_TO_SYMS_RATIO
+        * update_ssa_stats.num_virtual_symbols)
+    return true;
+
+  return false;
+}
+
+
+/* Remove every virtual mapping and mark all the affected virtual
+   symbols for renaming.  */
+
+static void
+switch_virtuals_to_full_rewrite (void)
+{
+  unsigned i = 0;
+  sbitmap_iterator sbi;
+
+  if (dump_file)
+    {
+      fprintf (dump_file, "\nEnabled virtual name mapping heuristic.\n");
+      fprintf (dump_file, "\tNumber of virtual mappings:       %7u\n",
+	       update_ssa_stats.num_virtual_mappings);
+      fprintf (dump_file, "\tNumber of unique virtual symbols: %7u\n",
+	       update_ssa_stats.num_virtual_symbols);
+      fprintf (dump_file, "Updating FUD-chains from top of CFG will be "
+	                  "faster than processing\nthe name mappings.\n\n");
+    }
+
+  /* Remove all virtual names from NEW_SSA_NAMES and OLD_SSA_NAMES.
+     Note that it is not really necessary to remove the mappings from
+     REPL_TBL, that would only waste time.  */
+  EXECUTE_IF_SET_IN_SBITMAP (new_ssa_names, 0, i, sbi)
+    if (!is_gimple_reg (ssa_name (i)))
+      RESET_BIT (new_ssa_names, i);
+
+  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
+    if (!is_gimple_reg (ssa_name (i)))
+      RESET_BIT (old_ssa_names, i);
+
+  mark_set_for_renaming (update_ssa_stats.virtual_symbols);
+}
+
+
+/* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
+   existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
+
+   1- The names in OLD_SSA_NAMES dominated by the definitions of
+      NEW_SSA_NAMES are all re-written to be reached by the
+      appropriate definition from NEW_SSA_NAMES.
+
+   2- If needed, new PHI nodes are added to the iterated dominance
+      frontier of the blocks where each of NEW_SSA_NAMES are defined.
+
+   The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
+   calling register_new_name_mapping for every pair of names that the
+   caller wants to replace.
+
+   The caller identifies the new names that have been inserted and the
+   names that need to be replaced by calling register_new_name_mapping
+   for every pair <NEW, OLD>.  Note that the function assumes that the
+   new names have already been inserted in the IL.
+
+   For instance, given the following code:
+
+     1	L0:
+     2	x_1 = PHI (0, x_5)
+     3	if (x_1 < 10)
+     4	  if (x_1 > 7)
+     5	    y_2 = 0
+     6	  else
+     7	    y_3 = x_1 + x_7
+     8	  endif
+     9	  x_5 = x_1 + 1
+     10   goto L0;
+     11	endif
+
+   Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
+
+     1	L0:
+     2	x_1 = PHI (0, x_5)
+     3	if (x_1 < 10)
+     4	  x_10 = ...
+     5	  if (x_1 > 7)
+     6	    y_2 = 0
+     7	  else
+     8	    x_11 = ...
+     9	    y_3 = x_1 + x_7
+     10	  endif
+     11	  x_5 = x_1 + 1
+     12	  goto L0;
+     13	endif
+
+   We want to replace all the uses of x_1 with the new definitions of
+   x_10 and x_11.  Note that the only uses that should be replaced are
+   those at lines 5, 9 and 11.  Also, the use of x_7 at line 9 should
+   *not* be replaced (this is why we cannot just mark symbol 'x' for
+   renaming).
+
+   Additionally, we may need to insert a PHI node at line 11 because
+   that is a merge point for x_10 and x_11.  So the use of x_1 at line
+   11 will be replaced with the new PHI node.  The insertion of PHI
+   nodes is optional.  They are not strictly necessary to preserve the
+   SSA form, and depending on what the caller inserted, they may not
+   even be useful for the optimizers.  UPDATE_FLAGS controls various
+   aspects of how update_ssa operates, see the documentation for
+   TODO_update_ssa*.  */
+
+void
+update_ssa (unsigned update_flags)
+{
+  basic_block bb, start_bb;
+  bitmap_iterator bi;
+  unsigned i = 0;
+  sbitmap tmp;
+  bool insert_phi_p;
+  sbitmap_iterator sbi;
+
+  if (!need_ssa_update_p ())
+    return;
+
+  timevar_push (TV_TREE_SSA_INCREMENTAL);
+
+  blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
+  if (!phis_to_rewrite)
+    phis_to_rewrite = VEC_alloc (gimple_vec, heap, last_basic_block);
+  blocks_to_update = BITMAP_ALLOC (NULL);
+
+  /* Ensure that the dominance information is up-to-date.  */
+  calculate_dominance_info (CDI_DOMINATORS);
+
+  /* Only one update flag should be set.  */
+  gcc_assert (update_flags == TODO_update_ssa
+              || update_flags == TODO_update_ssa_no_phi
+	      || update_flags == TODO_update_ssa_full_phi
+	      || update_flags == TODO_update_ssa_only_virtuals);
+
+  /* If we only need to update virtuals, remove all the mappings for
+     real names before proceeding.  The caller is responsible for
+     having dealt with the name mappings before calling update_ssa.  */
+  if (update_flags == TODO_update_ssa_only_virtuals)
+    {
+      sbitmap_zero (old_ssa_names);
+      sbitmap_zero (new_ssa_names);
+      htab_empty (repl_tbl);
+    }
+
+  insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
+
+  if (insert_phi_p)
+    {
+      /* If the caller requested PHI nodes to be added, initialize
+	 live-in information data structures (DEF_BLOCKS).  */
+
+      /* For each SSA name N, the DEF_BLOCKS table describes where the
+	 name is defined, which blocks have PHI nodes for N, and which
+	 blocks have uses of N (i.e., N is live-on-entry in those
+	 blocks).  */
+      def_blocks = htab_create (num_ssa_names, def_blocks_hash,
+				def_blocks_eq, def_blocks_free);
+    }
+  else
+    {
+      def_blocks = NULL;
+    }
+
+  /* Heuristic to avoid massive slow downs when the replacement
+     mappings include lots of virtual names.  */
+  if (insert_phi_p && switch_virtuals_to_full_rewrite_p ())
+    switch_virtuals_to_full_rewrite ();
+
+  /* If there are symbols to rename, identify those symbols that are
+     GIMPLE registers into the set REGS_TO_RENAME and those that are
+     memory symbols into the set MEM_SYMS_TO_RENAME.  */
+  if (!bitmap_empty_p (syms_to_rename))
+    {
+      unsigned i;
+      bitmap_iterator bi;
+
+      EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
+	{
+	  tree sym = referenced_var (i);
+	  if (is_gimple_reg (sym))
+	    bitmap_set_bit (regs_to_rename, i);
+	  else
+	    {
+	      /* Memory partitioning information may have been
+		 computed after the symbol was marked for renaming,
+		 if SYM is inside a partition also mark the partition
+		 for renaming.  */
+	      tree mpt = memory_partition (sym);
+	      if (mpt)
+		bitmap_set_bit (syms_to_rename, DECL_UID (mpt));
+	    }
+	}
+
+      /* Memory symbols are those not in REGS_TO_RENAME.  */
+      bitmap_and_compl (mem_syms_to_rename, syms_to_rename, regs_to_rename);
+    }
+
+  /* If there are names defined in the replacement table, prepare
+     definition and use sites for all the names in NEW_SSA_NAMES and
+     OLD_SSA_NAMES.  */
+  if (sbitmap_first_set_bit (new_ssa_names) >= 0)
+    {
+      prepare_names_to_update (insert_phi_p);
+
+      /* If all the names in NEW_SSA_NAMES had been marked for
+	 removal, and there are no symbols to rename, then there's
+	 nothing else to do.  */
+      if (sbitmap_first_set_bit (new_ssa_names) < 0
+	  && bitmap_empty_p (syms_to_rename))
+	goto done;
+    }
+
+  /* Next, determine the block at which to start the renaming process.  */
+  if (!bitmap_empty_p (syms_to_rename))
+    {
+      /* If we have to rename some symbols from scratch, we need to
+	 start the process at the root of the CFG.  FIXME, it should
+	 be possible to determine the nearest block that had a
+	 definition for each of the symbols that are marked for
+	 updating.  For now this seems more work than it's worth.  */
+      start_bb = ENTRY_BLOCK_PTR;
+
+      /* Traverse the CFG looking for existing definitions and uses of
+	 symbols in SYMS_TO_RENAME.  Mark interesting blocks and
+	 statements and set local live-in information for the PHI
+	 placement heuristics.  */
+      prepare_block_for_update (start_bb, insert_phi_p);
+    }
+  else
+    {
+      /* Otherwise, the entry block to the region is the nearest
+	 common dominator for the blocks in BLOCKS.  */
+      start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
+						   blocks_to_update);
+    }
+
+  /* If requested, insert PHI nodes at the iterated dominance frontier
+     of every block, creating new definitions for names in OLD_SSA_NAMES
+     and for symbols in SYMS_TO_RENAME.  */
+  if (insert_phi_p)
+    {
+      bitmap *dfs;
+
+      /* If the caller requested PHI nodes to be added, compute
+	 dominance frontiers.  */
+      dfs = XNEWVEC (bitmap, last_basic_block);
+      FOR_EACH_BB (bb)
+	dfs[bb->index] = BITMAP_ALLOC (NULL);
+      compute_dominance_frontiers (dfs);
+
+      if (sbitmap_first_set_bit (old_ssa_names) >= 0)
+	{
+	  sbitmap_iterator sbi;
+
+	  /* insert_update_phi_nodes_for will call add_new_name_mapping
+	     when inserting new PHI nodes, so the set OLD_SSA_NAMES
+	     will grow while we are traversing it (but it will not
+	     gain any new members).  Copy OLD_SSA_NAMES to a temporary
+	     for traversal.  */
+	  sbitmap tmp = sbitmap_alloc (old_ssa_names->n_bits);
+	  sbitmap_copy (tmp, old_ssa_names);
+	  EXECUTE_IF_SET_IN_SBITMAP (tmp, 0, i, sbi)
+	    insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
+	                                  update_flags);
+	  sbitmap_free (tmp);
+	}
+
+      EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
+	insert_updated_phi_nodes_for (referenced_var (i), dfs, blocks_to_update,
+	                              update_flags);
+
+      FOR_EACH_BB (bb)
+	BITMAP_FREE (dfs[bb->index]);
+      free (dfs);
+
+      /* Insertion of PHI nodes may have added blocks to the region.
+	 We need to re-compute START_BB to include the newly added
+	 blocks.  */
+      if (start_bb != ENTRY_BLOCK_PTR)
+	start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
+						     blocks_to_update);
+    }
+
+  /* Reset the current definition for name and symbol before renaming
+     the sub-graph.  */
+  EXECUTE_IF_SET_IN_SBITMAP (old_ssa_names, 0, i, sbi)
+    set_current_def (ssa_name (i), NULL_TREE);
+
+  EXECUTE_IF_SET_IN_BITMAP (syms_to_rename, 0, i, bi)
+    set_current_def (referenced_var (i), NULL_TREE);
+
+  /* Now start the renaming process at START_BB.  */
+  tmp = sbitmap_alloc (last_basic_block);
+  sbitmap_zero (tmp);
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
+    SET_BIT (tmp, i);
+
+  rewrite_blocks (start_bb, REWRITE_UPDATE, tmp);
+
+  sbitmap_free (tmp);
+
+  /* Debugging dumps.  */
+  if (dump_file)
+    {
+      int c;
+      unsigned i;
+
+      dump_update_ssa (dump_file);
+
+      fprintf (dump_file, "Incremental SSA update started at block: %d\n\n",
+	       start_bb->index);
+
+      c = 0;
+      EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
+	c++;
+      fprintf (dump_file, "Number of blocks in CFG: %d\n", last_basic_block);
+      fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n\n",
+	       c, PERCENT (c, last_basic_block));
+
+      if (dump_flags & TDF_DETAILS)
+	{
+	  fprintf (dump_file, "Affected blocks: ");
+	  EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
+	    fprintf (dump_file, "%u ", i);
+	  fprintf (dump_file, "\n");
+	}
+
+      fprintf (dump_file, "\n\n");
+    }
+
+  /* Free allocated memory.  */
+done:
+  delete_update_ssa ();
+
+  timevar_pop (TV_TREE_SSA_INCREMENTAL);
+}