CbC/CbC_gcc: gcc/tree-into-ssa.c comparison

comparison gcc/tree-into-ssa.c @ 0:a06113de4d67

first commit

author	kent <kent@cr.ie.u-ryukyu.ac.jp>
date	Fri, 17 Jul 2009 14:47:48 +0900
parents
children	77e2b8dfacca

comparison

equal deleted inserted replaced

--1:000000000000
+:a06113de4d67
+/* 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);
+}

Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-into-ssa.c @ 0:a06113de4d67