df.h (DF_SCAN, [...]): New macros.

2005-01-11  Danny Berlin <dberlin@dberlin.org>
            Kenneth Zadeck <zadeck@naturalbridge.com>

	* df.h (DF_SCAN, DF_RU, DF_RD, DF_LR, DF_UR, DF_UREC, DF_CHAIN,
	DF_RI, DF_LAST_PROBLEM_PLUS1, DF_DU_CHAIN, DF_UD_CHAIN,
	DF_REF_TYPE_NAMES, DF_HARD_REGS, DF_EQUIV_NOTES, DF_SUBREGS,
	DF_SCAN_BB_INFO, DF_RU_BB_INFO, DF_RD_BB_INFO, DF_LR_BB_INFO,
	DF_UR_BB_INFO, DF_UREC_BB_INFO, DF_LIVE_IN, DF_LIVE_OUT,
	DF_RA_LIVE_IN, DF_RA_LIVE_OUT, DF_UPWARD_LIVE_IN,
	DF_UPWARD_LIVE_OUT, DF_REF_REAL_REG, DF_REF_REGNO,
	DF_REF_REAL_LOC, DF_REF_REG, DF_REF_LOC, DF_REF_BB, DF_REF_BBNO,
	DF_REF_INSN, DF_REF_INSN_UID, DF_REF_TYPE, DF_REF_CHAIN,
	DF_REF_ID, DF_REF_FLAGS, DF_REF_NEXT_REG, DF_REF_PREV_REG,
	DF_REF_NEXT_REF, DF_REF_DATA, DF_REF_REG_DEF_P, DF_REF_REG_USE_P,
	DF_REF_REG_MEM_STORE_P, DF_REF_REG_MEM_LOAD_P, DF_REF_REG_MEM_P,
	DF_DEFS_SIZE, DF_DEFS_GET, DF_DEFS_SET, DF_USES_SIZE, DF_USES_GET,
	DF_USES_SET, DF_REG_SIZE, DF_REG_DEF_GET, DF_REG_DEF_SET,
	DF_REG_USE_GET, DF_REG_USE_SET, DF_REGNO_FIRST_DEF,
	DF_REGNO_LAST_USE, DF_INSN_SIZE, DF_INSN_GET, DF_INSN_SET,
	DF_INSN_CONTAINS_ASM, DF_INSN_LUID, DF_INSN_DEFS, DF_INSN_USES,
	DF_INSN_UID_GET, DF_INSN_UID_LUID, DF_INSN_UID_DEFS,
	DF_INSN_UID_USES, DF_SCAN_INITIAL, DF_SCAN_GLOBAL,
	DF_SCAN_POST_ALLOC): New macros.
	(df_flow_dir, df_ref_type, df_ref_flags, df_alloc_function,
	df_free_bb_function, df_local_compute_function, df_init_function,
	df_dataflow_function, df_confluence_function_0,
	df_confluence_function_n, df_transfer_function,
	df_finalizer_function, df_free_function, df_dump_problem_function,
	df_problem, dataflow, df_insn_info, df_reg_info, df_ref, df_link,
	df_ref_info, df, df_map, df_scan_bb_info, df_ru_bb_info,
	df_ru_bb_info, df_rd_bb_info, df_lr_bb_info, df_ur_bb_info,
	df_urec_bb_info, ) New types.
	(df_invalidated_by_call, df_all_hard_regs, df_state) New public
	variables.
	(df_init, df_add_problem, df_set_blocks, df_finish, df_analyze,
	df_analyze_simple_change_some_blocks,
	df_analyze_simple_change_one_block, df_compact_blocks,
	df_bb_replace, df_bb_regno_last_use_find,
	df_bb_regno_first_def_find, df_bb_regno_last_def_find,
	df_insn_regno_def_p, df_find_def, df_find_use,
	df_iterative_dataflow, df_dump, df_chain_dump, df_refs_chain_dump,
	df_regs_chain_dump, df_insn_debug, df_insn_debug_regno,
	df_regno_debug, df_ref_debug, debug_df_insn, debug_df_regno,
	debug_df_reg, debug_df_defno, debug_df_useno, debug_df_ref,
	debug_df_chain, df_get_dependent_problem, df_chain_create,
	df_chain_unlink, df_chain_copy, df_get_live_in, df_get_live_out,
	df_grow_bb_info, df_chain_dump, df_print_bb_index,
	df_ru_add_problem, df_ru_get_bb_info, df_rd_add_problem,
	df_rd_get_bb_info, df_lr_add_problem, df_lr_get_bb_info,
	df_ur_add_problem, df_ur_get_bb_info, df_urec_add_problem,
	df_urec_get_bb_info, df_chain_add_problem, df_ri_add_problem,
	df_reg_lifetime, df_scan_get_bb_info, df_scan_add_problem,
	df_rescan_blocks, df_ref_create, df_get_artificial_defs,
	df_get_artificial_uses, df_reg_chain_create, df_reg_chain_unlink,
	df_ref_remove, df_insn_refs_delete, df_refs_delete,
	df_reorganize_refs, df_set_state, df_hard_reg_init,
	df_read_modify_subreg_p) New public functions.
        * df-core.c: The core dataflow solver and glue routines for rtl
	dataflow.
	(df_init, df_add_problem, df_set_blocks, df_finish,
	df_hybrid_search_forward, df_hybrid_search_backward,
	df_iterative_dataflow, df_prune_to_subcfg, df_analyze_problem,
	df_analyze, df_get_bb_info, df_set_bb_info, df_bb_replace,
	df_bb_regno_last_use_find, df_bb_regno_first_def_find,
	df_bb_regno_last_def_find, df_insn_regno_def_p, df_find_def,
	df_reg_defined, df_find_use, df_reg_used, df_dump,
	df_refs_chain_dump, df_regs_chain_dump, df_insn_debug,
	df_insn_debug_regno, df_regno_debug, df_ref_debug, debug_df_insn,
	debug_df_reg, debug_df_regno, debug_df_ref debug_df_defno,
	debug_df_useno, reset_df_after_reload): New functions.
	* df-scan.c: The scanning fuctions, once in df.c, completely
	rewritten so that they now fully model the functionality of
	register usage at the backend.
	(df_scan_free_internal, df_scan_get_bb_info, df_scan_set_bb_info,
	df_scan_free_bb_info, df_scan_alloc, df_scan_free, df_scan_dump,
	df_scan_add_problem, df_grow_reg_info, df_grow_ref_info,
	df_grow_insn_info, df_rescan_blocks, df_ref_create,
	df_get_artificial_defs, df_get_artificial_uses,
	df_reg_chain_create, df_ref_unlink, df_reg_chain_unlink,
	df_ref_remove, df_insn_create_insn_record, df_insn_refs_delete,
	df_refs_delete, df_reorganize_refs, df_set_state,
	df_ref_create_structure, df_ref_record, df_read_modify_subreg_p,
	df_def_record_1, df_defs_record, df_uses_record,
	df_insn_contains_asm_1, df_insn_contains_asm, df_insn_refs_record,
	df_has_eh_preds, df_bb_refs_record, df_refs_record, df_mark_reg,
	df_record_exit_block_uses, df_hard_reg_init): New functions.

	* df-problems.c: Seven concrete dataflow problems that use the
	scanning in df-scan.c and are solved by the engine in df-core.c.
	(df_get_dependent_problem, df_chain_create, df_chain_unlink,
	df_chain_copy, df_get_live_in, df_get_live_out, df_grow_bb_info,
	df_chain_dump, df_print_bb_index, df_ref_bitmap, df_set_seen,
	df_unset_seen, df_ru_get_bb_info, df_ru_set_bb_info,
	df_ru_free_bb_info, df_ru_alloc,
	df_ru_bb_local_compute_process_def,
	df_ru_bb_local_compute_process_use, df_ru_bb_local_compute,
	df_ru_local_compute, df_ru_init_solution, df_ru_confluence_n,
	df_ru_transfer_function, df_ru_free, df_ru_dump,
	df_ru_add_problem, df_rd_get_bb_info, df_rd_set_bb_info,
	df_rd_free_bb_info, df_rd_alloc,
	df_rd_bb_local_compute_process_def, df_rd_bb_local_compute,
	df_rd_local_compute, df_rd_init_solution, df_rd_confluence_n,
	df_rd_transfer_function, df_rd_free, df_rd_dump,
	df_rd_add_problem, df_lr_get_bb_info, df_lr_set_bb_info,
	df_lr_free_bb_info, df_lr_alloc, df_lr_bb_local_compute,
	df_lr_local_compute, df_lr_init, df_lr_confluence_0,
	df_lr_confluence_n, df_lr_transfer_function, df_lr_free,
	df_lr_dump, df_lr_add_problem, df_ur_get_bb_info,
	df_ur_set_bb_info, df_ur_free_bb_info, df_ur_alloc,
	df_ur_bb_local_compute, df_ur_local_compute, df_ur_init,
	df_ur_local_finalize, df_ur_confluence_n, df_ur_transfer_function,
	df_ur_free, df_ur_dump, df_ur_add_problem, df_urec_get_bb_info,
	df_urec_set_bb_info, df_urec_free_bb_info, df_urec_alloc,
	df_urec_mark_reg_change, df_urec_check_earlyclobber,
	df_urec_mark_reg_use_for_earlyclobber,
	df_urec_mark_reg_use_for_earlyclobber_1, df_urec_bb_local_compute,
	df_urec_local_compute, df_urec_init, df_urec_local_finalize,
	df_urec_confluence_n, df_urec_transfer_function, df_urec_free,
	df_urec_dump, df_urec_add_problem, df_chain_alloc,
	df_chain_create_bb_process_use, df_chain_create_bb,
	df_chain_finalize, df_chain_free, df_chains_dump,
	df_chain_add_problem, df_ri_alloc, df_ri_bb_compute,
	df_ri_compute, df_ri_free, df_ri_dump, df_ri_add_problem,
	df_reg_lifetime): New functions.
	* df.c: Deleted file.
        * ddg.c (create_ddg_dep_no_link, build_inter_loop_deps): Made code
	consistent with new df api.
        * modulo-sched.c (sms_schedule, rest_of_handle_sms,
        rest_of_handle_sms): Ditto.
        * web.c (unionfind_union, union_defs, entry_register, web_main):
	Ditto.
	* loop_invariant.c (invariant_for_use, hash_invariant_expr_1,
	invariant_expr_equal_p, find_defs, check_dependencies,
	find_invariant_insn, find_invariants_to_move, move_invariant_reg,
	free_inv_motion_data, move_loop_invariants): Ditto.
	* sched-deps.c (sched_analyze_1): Ditto.


Co-Authored-By: Kenneth Zadeck <zadeck@naturalbridge.com>

From-SVN: r109577

1 files changed, 3093 insertions, 0 deletions

diff --git a/gcc/df-problems.c b/gcc/df-problems.c
new file mode 100644
index 0000000..c17e048
--- /dev/null
+++ b/gcc/df-problems.c
@@ -0,0 +1,3093 @@
+/* Standard problems for dataflow support routines.
+   Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006
+   Free Software Foundation, Inc.
+   Originally contributed by Michael P. Hayes 
+             (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
+   Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
+             and Kenneth Zadeck (zadeck@naturalbridge.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 2, 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 COPYING.  If not, write to the Free
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "insn-config.h"
+#include "recog.h"
+#include "function.h"
+#include "regs.h"
+#include "output.h"
+#include "alloc-pool.h"
+#include "flags.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "sbitmap.h"
+#include "bitmap.h"
+#include "timevar.h"
+#include "df.h"
+
+#define DF_SPARSE_THRESHOLD 32
+
+static bitmap seen_in_block = NULL;
+static bitmap seen_in_insn = NULL;
+
+
+/*----------------------------------------------------------------------------
+   Public functions access functions for the dataflow problems.
+----------------------------------------------------------------------------*/
+
+/* Get the instance of the problem that DFLOW is dependent on.  */
+
+struct dataflow *
+df_get_dependent_problem (struct dataflow *dflow)
+{
+  struct df *df = dflow->df;
+  struct df_problem *dependent_problem = dflow->problem->dependent_problem;
+
+  gcc_assert (dependent_problem);
+  return df->problems_by_index[dependent_problem->id];
+}
+
+
+/* Create a du or ud chain from SRC to DST and link it into SRC.   */
+
+struct df_link *
+df_chain_create (struct dataflow *dflow, struct df_ref *src, struct df_ref *dst)
+{
+  struct df_link *head = DF_REF_CHAIN (src);
+  struct df_link *link = pool_alloc (dflow->block_pool);;
+  
+  DF_REF_CHAIN (src) = link;
+  link->next = head;
+  link->ref = dst;
+  return link;
+}
+
+
+/* Delete a du or ud chain for REF.  If LINK is NULL, delete all
+   chains for ref and check to see if the reverse chains can also be
+   deleted.  If LINK is not NULL it must be a link off of ref.  In
+   this case, the other end is not deleted.  */
+
+void
+df_chain_unlink (struct dataflow *dflow, struct df_ref *ref, struct df_link *link)
+{
+  struct df_link *chain = DF_REF_CHAIN (ref);
+  if (link)
+    {
+      /* Link was the first element in the chain.  */
+      if (chain == link)
+	DF_REF_CHAIN (ref) = link->next;
+      else
+	{
+	  /* Link is an internal element in the chain.  */
+	  struct df_link *prev = chain;
+	  while (chain)
+	    {
+	      if (chain == link)
+		{
+		  prev->next = chain->next;
+		  break;
+		}
+	      prev = chain;
+	      chain = chain->next;
+	    }
+	}
+      pool_free (dflow->block_pool, link);
+    }
+  else
+    {
+      /* If chain is NULL here, it was because of a recursive call
+	 when the other flavor of chains was not built.  Just run thru
+	 the entire chain calling the other side and then deleting the
+	 link.  */
+      while (chain)
+	{
+	  struct df_link *next = chain->next;
+	  /* Delete the other side if it exists.  */
+	  df_chain_unlink (dflow, chain->ref, chain);
+	  chain = next;
+	}
+    }
+}
+
+
+/* Copy the du or ud chain starting at FROM_REF and attach it to
+   TO_REF.  */ 
+
+void 
+df_chain_copy (struct dataflow *dflow, 
+	       struct df_ref *to_ref, 
+	       struct df_link *from_ref)
+{
+  while (from_ref)
+    {
+      df_chain_create (dflow, to_ref, from_ref->ref);
+      from_ref = from_ref->next;
+    }
+}
+
+
+/* Get the live in set for BB no matter what problem happens to be
+   defined.  */
+
+bitmap
+df_get_live_in (struct df *df, basic_block bb)
+{
+  gcc_assert (df->problems_by_index[DF_LR]);
+
+  if (df->problems_by_index[DF_UREC])
+    return DF_RA_LIVE_IN (df, bb);
+  else if (df->problems_by_index[DF_UR])
+    return DF_LIVE_IN (df, bb);
+  else 
+    return DF_UPWARD_LIVE_IN (df, bb);
+}
+
+
+/* Get the live out set for BB no matter what problem happens to be
+   defined.  */
+
+bitmap
+df_get_live_out (struct df *df, basic_block bb)
+{
+  gcc_assert (df->problems_by_index[DF_LR]);
+
+  if (df->problems_by_index[DF_UREC])
+    return DF_RA_LIVE_OUT (df, bb);
+  else if (df->problems_by_index[DF_UR])
+    return DF_LIVE_OUT (df, bb);
+  else 
+    return DF_UPWARD_LIVE_OUT (df, bb);
+}
+
+
+/*----------------------------------------------------------------------------
+   Utility functions.
+----------------------------------------------------------------------------*/
+
+/* Generic versions to get the void* version of the block info.  Only
+   used inside the problem instace vectors.  */
+
+/* Grow the bb_info array.  */
+
+void
+df_grow_bb_info (struct dataflow *dflow)
+{
+  unsigned int new_size = last_basic_block + 1;
+  if (dflow->block_info_size < new_size)
+    {
+      new_size += new_size / 4;
+      dflow->block_info = xrealloc (dflow->block_info, 
+				    new_size *sizeof (void*));
+      memset (dflow->block_info + dflow->block_info_size, 0,
+	      (new_size - dflow->block_info_size) *sizeof (void *));
+      dflow->block_info_size = new_size;
+    }
+}
+
+/* Dump a def-use or use-def chain for REF to FILE.  */
+
+void
+df_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_link *link, FILE *file)
+{
+  fprintf (file, "{ ");
+  for (; link; link = link->next)
+    {
+      fprintf (file, "%c%d(bb %d insn %d) ",
+	       DF_REF_REG_DEF_P (link->ref) ? 'd' : 'u',
+	       DF_REF_ID (link->ref),
+	       DF_REF_BBNO (link->ref),
+	       DF_REF_INSN (link->ref) ? DF_REF_INSN_UID (link->ref) : -1);
+    }
+  fprintf (file, "}");
+}
+
+
+/* Print some basic block info as part of df_dump.  */
+
+void 
+df_print_bb_index (basic_block bb, FILE *file)
+{
+  edge e;
+  edge_iterator ei;
+
+  fprintf (file, "( ");
+    FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      basic_block pred = e->src;
+      fprintf (file, "%d ", pred->index);
+    } 
+  fprintf (file, ")->[%d]->( ", bb->index);
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      basic_block succ = e->dest;
+      fprintf (file, "%d ", succ->index);
+    } 
+  fprintf (file, ")\n");
+}
+
+
+/* Return the set of reference ids in CHAIN, caching the result in *BMAP.  */
+
+static inline bitmap
+df_ref_bitmap (bitmap *maps, unsigned int regno, int start, int count)
+{
+  bitmap ids = maps[regno];
+  if (!ids)
+    {
+      unsigned int i;
+      unsigned int end = start + count;;
+      ids = BITMAP_ALLOC (NULL);
+      maps[regno] = ids;
+      for (i = start; i < end; i++)
+	bitmap_set_bit (ids, i);
+    }
+  return ids;
+}
+
+
+/* Make sure that the seen_in_insn and seen_in_block sbitmaps are set
+   up correctly. */
+
+static void
+df_set_seen (void)
+{
+  seen_in_block = BITMAP_ALLOC (NULL);
+  seen_in_insn = BITMAP_ALLOC (NULL);
+}
+
+
+static void
+df_unset_seen (void)
+{
+  BITMAP_FREE (seen_in_block);
+  BITMAP_FREE (seen_in_insn);
+}
+
+
+
+/*----------------------------------------------------------------------------
+   REACHING USES
+
+   Find the locations in the function where each use site for a pseudo
+   can reach backwards.
+
+----------------------------------------------------------------------------*/
+
+struct df_ru_problem_data
+{
+  bitmap *use_sites;            /* Bitmap of uses for each pseudo.  */
+  unsigned int use_sites_size;  /* Size of use_sites.  */
+  /* The set of defs to regs invalidated by call.  */
+  bitmap sparse_invalidated_by_call;  
+  /* The set of defs to regs invalidate by call for ru.  */  
+  bitmap dense_invalidated_by_call;   
+};
+
+/* Get basic block info.  */
+
+struct df_ru_bb_info *
+df_ru_get_bb_info (struct dataflow *dflow, unsigned int index)
+{
+  return (struct df_ru_bb_info *) dflow->block_info[index];
+}
+
+
+/* Set basic block info.  */
+
+static void
+df_ru_set_bb_info (struct dataflow *dflow, unsigned int index, 
+		   struct df_ru_bb_info *bb_info)
+{
+  dflow->block_info[index] = bb_info;
+}
+
+
+/* Free basic block info.  */
+
+static void
+df_ru_free_bb_info (struct dataflow *dflow, void *vbb_info)
+{
+  struct df_ru_bb_info *bb_info = (struct df_ru_bb_info *) vbb_info;
+  if (bb_info)
+    {
+      BITMAP_FREE (bb_info->kill);
+      BITMAP_FREE (bb_info->sparse_kill);
+      BITMAP_FREE (bb_info->gen);
+      BITMAP_FREE (bb_info->in);
+      BITMAP_FREE (bb_info->out);
+      pool_free (dflow->block_pool, bb_info);
+    }
+}
+
+
+/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+   not touched unless the block is new.  */
+
+static void 
+df_ru_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  unsigned int reg_size = max_reg_num ();
+
+  if (! dflow->block_pool)
+    dflow->block_pool = create_alloc_pool ("df_ru_block pool", 
+					   sizeof (struct df_ru_bb_info), 50);
+
+  if (dflow->problem_data)
+    {
+      unsigned int i;
+      struct df_ru_problem_data *problem_data =
+	(struct df_ru_problem_data *) dflow->problem_data;
+
+      for (i = 0; i < problem_data->use_sites_size; i++)
+	{
+	  bitmap bm = problem_data->use_sites[i];
+	  if (bm)
+	    {
+	      BITMAP_FREE (bm);
+	      problem_data->use_sites[i] = NULL;
+	    }
+	}
+      
+      if (problem_data->use_sites_size > reg_size)
+	{
+	  problem_data->use_sites 
+	    = xrealloc (problem_data->use_sites, reg_size *sizeof (bitmap));
+	  memset (problem_data->use_sites, 0,
+		  (reg_size - problem_data->use_sites_size) *sizeof (bitmap));
+	  problem_data->use_sites_size = reg_size;
+	}
+
+      bitmap_clear (problem_data->sparse_invalidated_by_call);
+      bitmap_clear (problem_data->dense_invalidated_by_call);
+    }
+  else 
+    {
+      struct df_ru_problem_data *problem_data =
+	xmalloc (sizeof (struct df_ru_problem_data));
+      dflow->problem_data = problem_data;
+
+      problem_data->use_sites = xcalloc (reg_size, sizeof (bitmap));
+      problem_data->use_sites_size = reg_size;
+      problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
+      problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
+    }
+
+  df_grow_bb_info (dflow);
+
+  /* Because of the clustering of all def sites for the same pseudo,
+     we have to process all of the blocks before doing the
+     analysis.  */
+
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+    {
+      struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+      if (bb_info)
+	{ 
+	  bitmap_clear (bb_info->kill);
+	  bitmap_clear (bb_info->sparse_kill);
+	  bitmap_clear (bb_info->gen);
+	}
+      else
+	{ 
+	  bb_info = (struct df_ru_bb_info *) pool_alloc (dflow->block_pool);
+	  df_ru_set_bb_info (dflow, bb_index, bb_info);
+	  bb_info->kill = BITMAP_ALLOC (NULL);
+	  bb_info->sparse_kill = BITMAP_ALLOC (NULL);
+	  bb_info->gen = BITMAP_ALLOC (NULL);
+	  bb_info->in = BITMAP_ALLOC (NULL);
+	  bb_info->out = BITMAP_ALLOC (NULL);
+	}
+    }
+}
+
+
+/* Process a list of DEFs for df_ru_bb_local_compute.  */
+
+static void
+df_ru_bb_local_compute_process_def (struct dataflow *dflow,
+				    struct df_ru_bb_info *bb_info, 
+				    struct df_ref *def)
+{
+  struct df *df = dflow->df;
+  while (def)
+    {
+      unsigned int regno = DF_REF_REGNO (def);
+      unsigned int begin = DF_REG_USE_GET (df, regno)->begin;
+      unsigned int n_uses = DF_REG_USE_GET (df, regno)->n_refs;
+      if (!bitmap_bit_p (seen_in_block, regno))
+	{
+	  /* The first def for regno, causes the kill info to be
+	     generated and the gen information to cleared.  */
+	  if (!bitmap_bit_p (seen_in_insn, regno))
+	    {
+	      if (n_uses > DF_SPARSE_THRESHOLD)
+		{
+		  bitmap_set_bit (bb_info->sparse_kill, regno);
+		  bitmap_clear_range (bb_info->gen, begin, n_uses);
+		}
+	      else
+		{
+		  struct df_ru_problem_data *problem_data =
+		    (struct df_ru_problem_data *) dflow->problem_data;
+		  bitmap uses = 
+		    df_ref_bitmap (problem_data->use_sites, regno, 
+				   begin, n_uses);
+		  bitmap_ior_into (bb_info->kill, uses);
+		  bitmap_and_compl_into (bb_info->gen, uses);
+		}
+	    }
+	  bitmap_set_bit (seen_in_insn, regno);
+	}
+      def = def->next_ref;
+    }
+}
+
+
+/* Process a list of USEs for df_ru_bb_local_compute.  */
+
+static void
+df_ru_bb_local_compute_process_use (struct df_ru_bb_info *bb_info, 
+				    struct df_ref *use,
+				    enum df_ref_flags top_flag)
+{
+  while (use)
+    {
+      if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+	{
+	  /* Add use to set of gens in this BB unless we have seen a
+	     def in a previous instruction.  */
+	  unsigned int regno = DF_REF_REGNO (use);
+	  if (!bitmap_bit_p (seen_in_block, regno))
+	    bitmap_set_bit (bb_info->gen, DF_REF_ID (use));
+	}
+      use = use->next_ref;
+    }
+}
+
+/* Compute local reaching use (upward exposed use) info for basic
+   block BB.  USE_INFO->REGS[R] caches the set of uses for register R.  */
+static void
+df_ru_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+{
+  struct df *df = dflow->df;
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+  rtx insn;
+
+  /* Set when a def for regno is seen.  */
+  bitmap_clear (seen_in_block);
+  bitmap_clear (seen_in_insn);
+
+#ifdef EH_USES
+  /* Variables defined in the prolog that are used by the exception
+     handler.  */
+  df_ru_bb_local_compute_process_use (bb_info, 
+				      df_get_artificial_uses (df, bb_index),
+				      DF_REF_AT_TOP);
+#endif
+
+  /* Process the artificial defs first since these are at the top of
+     the block.  */
+  df_ru_bb_local_compute_process_def (dflow, bb_info, 
+				      df_get_artificial_defs (df, bb_index));
+
+  FOR_BB_INSNS (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+      if (! INSN_P (insn))
+	continue;
+
+      df_ru_bb_local_compute_process_def (dflow, bb_info, 
+					  DF_INSN_UID_GET (df, uid)->defs);
+
+      /* The use processing must happen after the defs processing even
+	 though the uses logically happen first since the defs clear
+	 the gen set. Otherwise, a use for regno occuring in the same
+	 instruction as a def for regno would be cleared.  */ 
+      df_ru_bb_local_compute_process_use (bb_info, 
+					  DF_INSN_UID_GET (df, uid)->uses, 0);
+
+      bitmap_ior_into (seen_in_block, seen_in_insn);
+      bitmap_clear (seen_in_insn);
+    }
+
+  /* Process the hardware registers that are always live.  */
+  df_ru_bb_local_compute_process_use (bb_info, 
+				      df_get_artificial_uses (df, bb_index), 0);
+}
+
+
+/* Compute local reaching use (upward exposed use) info for each basic
+   block within BLOCKS.  */
+static void
+df_ru_local_compute (struct dataflow *dflow, 
+		     bitmap all_blocks,
+		     bitmap rescan_blocks  ATTRIBUTE_UNUSED)
+{
+  struct df *df = dflow->df;
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  unsigned int regno;
+  struct df_ru_problem_data *problem_data =
+    (struct df_ru_problem_data *) dflow->problem_data;
+  bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
+  bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
+
+  df_set_seen ();
+
+  if (!df->use_info.refs_organized)
+    df_reorganize_refs (&df->use_info);
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      df_ru_bb_local_compute (dflow, bb_index);
+    }
+  
+  /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
+  EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
+    {
+      struct df_reg_info *reg_info = DF_REG_USE_GET (df, regno);
+      if (reg_info->n_refs > DF_SPARSE_THRESHOLD)
+	bitmap_set_bit (sparse_invalidated, regno);
+      else
+	{
+	  bitmap defs = df_ref_bitmap (problem_data->use_sites, regno, 
+				       reg_info->begin, reg_info->n_refs);
+	  bitmap_ior_into (dense_invalidated, defs);
+	}
+    }
+
+  df_unset_seen ();
+}
+
+
+/* Initialize the solution bit vectors for problem.  */
+
+static void 
+df_ru_init_solution (struct dataflow *dflow, bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+      bitmap_copy (bb_info->in, bb_info->gen);
+      bitmap_clear (bb_info->out);
+    }
+}
+
+
+/* Out of target gets or of in of source.  */
+
+static void
+df_ru_confluence_n (struct dataflow *dflow, edge e)
+{
+  bitmap op1 = df_ru_get_bb_info (dflow, e->src->index)->out;
+  bitmap op2 = df_ru_get_bb_info (dflow, e->dest->index)->in;
+
+  if (e->flags & EDGE_EH)
+    {
+      struct df_ru_problem_data *problem_data =
+	(struct df_ru_problem_data *) dflow->problem_data;
+      bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
+      bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
+      struct df *df = dflow->df;
+      bitmap_iterator bi;
+      unsigned int regno;
+      bitmap_ior_and_compl_into (op1, op2, dense_invalidated);
+      EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
+	{
+ 	  bitmap_clear_range (op1, 
+ 			      DF_REG_USE_GET (df, regno)->begin, 
+ 			      DF_REG_USE_GET (df, regno)->n_refs);
+	}
+    }
+  else
+    bitmap_ior_into (op1, op2);
+}
+
+
+/* Transfer function.  */
+
+static bool
+df_ru_transfer_function (struct dataflow *dflow, int bb_index)
+{
+  struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb_index);
+  unsigned int regno;
+  bitmap_iterator bi;
+  bitmap in = bb_info->in;
+  bitmap out = bb_info->out;
+  bitmap gen = bb_info->gen;
+  bitmap kill = bb_info->kill;
+  bitmap sparse_kill = bb_info->sparse_kill;
+
+  if (bitmap_empty_p (sparse_kill))
+    return  bitmap_ior_and_compl (in, gen, out, kill);
+  else 
+    {
+      struct df *df = dflow->df;
+      bool changed = false;
+      bitmap tmp = BITMAP_ALLOC (NULL);
+      bitmap_copy (tmp, in);
+      EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
+	{
+	  bitmap_clear_range (tmp, 
+ 			      DF_REG_USE_GET (df, regno)->begin, 
+ 			      DF_REG_USE_GET (df, regno)->n_refs);
+	}
+      bitmap_and_compl_into (tmp, kill);
+      bitmap_ior_into (tmp, gen);
+      changed = !bitmap_equal_p (tmp, out);
+      if (changed)
+	{
+	  BITMAP_FREE (out);
+	  bb_info->in = tmp;
+	}
+      else 
+	BITMAP_FREE (tmp);
+      return changed;
+    }
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_ru_free (struct dataflow *dflow)
+{
+  unsigned int i;
+  struct df_ru_problem_data *problem_data =
+    (struct df_ru_problem_data *) dflow->problem_data;
+
+  for (i = 0; i < dflow->block_info_size; i++)
+    {
+      struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, i);
+      if (bb_info)
+	{
+	  BITMAP_FREE (bb_info->kill);
+	  BITMAP_FREE (bb_info->sparse_kill);
+	  BITMAP_FREE (bb_info->gen);
+	  BITMAP_FREE (bb_info->in);
+	  BITMAP_FREE (bb_info->out);
+	}
+    }
+
+  free_alloc_pool (dflow->block_pool);
+
+  for (i = 0; i < problem_data->use_sites_size; i++)
+    {
+      bitmap bm = problem_data->use_sites[i];
+      if (bm)
+	BITMAP_FREE (bm);
+    }
+
+  free (problem_data->use_sites);
+  BITMAP_FREE (problem_data->sparse_invalidated_by_call);
+  BITMAP_FREE (problem_data->dense_invalidated_by_call);
+
+  dflow->block_info_size = 0;
+  free (dflow->block_info);
+  free (dflow->problem_data);
+  free (dflow);
+}
+
+
+/* Debugging info.  */
+
+static void
+df_ru_dump (struct dataflow *dflow, FILE *file)
+{
+  basic_block bb;
+  struct df *df = dflow->df;
+  struct df_ru_problem_data *problem_data =
+    (struct df_ru_problem_data *) dflow->problem_data;
+  unsigned int m = max_reg_num ();
+  unsigned int regno;
+
+  fprintf (file, "Reaching uses:\n");
+
+  fprintf (file, "  sparse invalidated \t");
+  dump_bitmap (file, problem_data->sparse_invalidated_by_call);
+  fprintf (file, "  dense invalidated \t");
+  dump_bitmap (file, problem_data->dense_invalidated_by_call);
+  
+  for (regno = 0; regno < m; regno++)
+    if (DF_REG_USE_GET (df, regno)->n_refs)
+      fprintf (file, "%d[%d,%d] ", regno, 
+	       DF_REG_USE_GET (df, regno)->begin, 
+	       DF_REG_USE_GET (df, regno)->n_refs);
+  fprintf (file, "\n");
+
+  FOR_ALL_BB (bb)
+    {
+      struct df_ru_bb_info *bb_info = df_ru_get_bb_info (dflow, bb->index);
+      df_print_bb_index (bb, file);
+      
+      if (! bb_info->in)
+	continue;
+      
+      fprintf (file, "  in  \t");
+      dump_bitmap (file, bb_info->in);
+      fprintf (file, "  gen \t");
+      dump_bitmap (file, bb_info->gen);
+      fprintf (file, "  kill\t");
+      dump_bitmap (file, bb_info->kill);
+      fprintf (file, "  out \t");
+      dump_bitmap (file, bb_info->out);
+    }
+}
+
+/* All of the information associated with every instance of the problem.  */
+
+static struct df_problem problem_RU =
+{
+  DF_RU,                      /* Problem id.  */
+  DF_BACKWARD,                /* Direction.  */
+  df_ru_alloc,                /* Allocate the problem specific data.  */
+  df_ru_free_bb_info,         /* Free basic block info.  */
+  df_ru_local_compute,        /* Local compute function.  */
+  df_ru_init_solution,        /* Init the solution specific data.  */
+  df_iterative_dataflow,      /* Iterative solver.  */
+  NULL,                       /* Confluence operator 0.  */ 
+  df_ru_confluence_n,         /* Confluence operator n.  */ 
+  df_ru_transfer_function,    /* Transfer function.  */
+  NULL,                       /* Finalize function.  */
+  df_ru_free,                 /* Free all of the problem information.  */
+  df_ru_dump,                 /* Debugging.  */
+  NULL                        /* Dependent problem.  */
+};
+
+
+
+/* Create a new DATAFLOW instance and add it to an existing instance
+   of DF.  The returned structure is what is used to get at the
+   solution.  */
+
+struct dataflow *
+df_ru_add_problem (struct df *df)
+{
+  return df_add_problem (df, &problem_RU);
+}
+
+
+/*----------------------------------------------------------------------------
+   REACHING DEFINITIONS
+
+   Find the locations in the function where each definition site for a
+   pseudo reaches.
+----------------------------------------------------------------------------*/
+
+struct df_rd_problem_data
+{
+  bitmap *def_sites;            /* Bitmap of defs for each pseudo.  */
+  unsigned int def_sites_size;  /* Size of def_sites.  */
+  /* The set of defs to regs invalidated by call.  */
+  bitmap sparse_invalidated_by_call;  
+  /* The set of defs to regs invalidate by call for ru.  */  
+  bitmap dense_invalidated_by_call;   
+};
+
+/* Get basic block info.  */
+
+struct df_rd_bb_info *
+df_rd_get_bb_info (struct dataflow *dflow, unsigned int index)
+{
+  return (struct df_rd_bb_info *) dflow->block_info[index];
+}
+
+
+/* Set basic block info.  */
+
+static void
+df_rd_set_bb_info (struct dataflow *dflow, unsigned int index, 
+		   struct df_rd_bb_info *bb_info)
+{
+  dflow->block_info[index] = bb_info;
+}
+
+
+/* Free basic block info.  */
+
+static void
+df_rd_free_bb_info (struct dataflow *dflow, void *vbb_info)
+{
+  struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
+  if (bb_info)
+    {
+      BITMAP_FREE (bb_info->kill);
+      BITMAP_FREE (bb_info->sparse_kill);
+      BITMAP_FREE (bb_info->gen);
+      BITMAP_FREE (bb_info->in);
+      BITMAP_FREE (bb_info->out);
+      pool_free (dflow->block_pool, bb_info);
+    }
+}
+
+
+/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+   not touched unless the block is new.  */
+
+static void 
+df_rd_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  unsigned int reg_size = max_reg_num ();
+
+  if (! dflow->block_pool)
+    dflow->block_pool = create_alloc_pool ("df_rd_block pool", 
+					   sizeof (struct df_rd_bb_info), 50);
+
+  if (dflow->problem_data)
+    {
+      unsigned int i;
+      struct df_rd_problem_data *problem_data =
+	(struct df_rd_problem_data *) dflow->problem_data;
+
+      for (i = 0; i < problem_data->def_sites_size; i++)
+	{
+	  bitmap bm = problem_data->def_sites[i];
+	  if (bm)
+	    {
+	      BITMAP_FREE (bm);
+	      problem_data->def_sites[i] = NULL;
+	    }
+	}
+      
+      if (problem_data->def_sites_size > reg_size)
+	{
+	  problem_data->def_sites 
+	    = xrealloc (problem_data->def_sites, reg_size *sizeof (bitmap));
+	  memset (problem_data->def_sites, 0,
+		  (reg_size - problem_data->def_sites_size) *sizeof (bitmap));
+	  problem_data->def_sites_size = reg_size;
+	}
+
+      bitmap_clear (problem_data->sparse_invalidated_by_call);
+      bitmap_clear (problem_data->dense_invalidated_by_call);
+    }
+  else 
+    {
+      struct df_rd_problem_data *problem_data =
+	xmalloc (sizeof (struct df_rd_problem_data));
+      dflow->problem_data = problem_data;
+
+      problem_data->def_sites = xcalloc (reg_size, sizeof (bitmap));
+      problem_data->def_sites_size = reg_size;
+      problem_data->sparse_invalidated_by_call = BITMAP_ALLOC (NULL);
+      problem_data->dense_invalidated_by_call = BITMAP_ALLOC (NULL);
+    }
+
+  df_grow_bb_info (dflow);
+
+  /* Because of the clustering of all def sites for the same pseudo,
+     we have to process all of the blocks before doing the
+     analysis.  */
+
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+    {
+      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+      if (bb_info)
+	{ 
+	  bitmap_clear (bb_info->kill);
+	  bitmap_clear (bb_info->sparse_kill);
+	  bitmap_clear (bb_info->gen);
+	}
+      else
+	{ 
+	  bb_info = (struct df_rd_bb_info *) pool_alloc (dflow->block_pool);
+	  df_rd_set_bb_info (dflow, bb_index, bb_info);
+	  bb_info->kill = BITMAP_ALLOC (NULL);
+	  bb_info->sparse_kill = BITMAP_ALLOC (NULL);
+	  bb_info->gen = BITMAP_ALLOC (NULL);
+	  bb_info->in = BITMAP_ALLOC (NULL);
+	  bb_info->out = BITMAP_ALLOC (NULL);
+	}
+    }
+}
+
+
+/* Process a list of DEFs for df_rd_bb_local_compute.  */
+
+static void
+df_rd_bb_local_compute_process_def (struct dataflow *dflow,
+				    struct df_rd_bb_info *bb_info, 
+				    struct df_ref *def)
+{
+  struct df *df = dflow->df;
+  while (def)
+    {
+      unsigned int regno = DF_REF_REGNO (def);
+      unsigned int begin = DF_REG_DEF_GET (df, regno)->begin;
+      unsigned int n_defs = DF_REG_DEF_GET (df, regno)->n_refs;
+      
+      /* Only the last def(s) for a regno in the block has any
+	 effect.  */ 
+      if (!bitmap_bit_p (seen_in_block, regno))
+	{
+	  /* The first def for regno in insn gets to knock out the
+	     defs from other instructions.  */
+	  if (!bitmap_bit_p (seen_in_insn, regno))
+	    {
+	      if (n_defs > DF_SPARSE_THRESHOLD)
+		{
+		  bitmap_set_bit (bb_info->sparse_kill, regno);
+		  bitmap_clear_range (bb_info->gen, begin, n_defs);
+		}
+	      else
+		{
+		  struct df_rd_problem_data *problem_data =
+		    (struct df_rd_problem_data *) dflow->problem_data;
+		  bitmap defs = 
+		    df_ref_bitmap (problem_data->def_sites, regno, 
+				   begin, n_defs);
+		  bitmap_ior_into (bb_info->kill, defs);
+		  bitmap_and_compl_into (bb_info->gen, defs);
+		}
+	    }
+	  
+	  bitmap_set_bit (seen_in_insn, regno);
+	  /* All defs for regno in the instruction may be put into
+	     the gen set.  */
+	  if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
+	    bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
+	}
+      def = def->next_ref;
+    }
+}
+
+/* Compute local reaching def info for basic block BB.  */
+
+static void
+df_rd_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+{
+  struct df *df = dflow->df;
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+  rtx insn;
+
+  bitmap_clear (seen_in_block);
+  bitmap_clear (seen_in_insn);
+
+  FOR_BB_INSNS_REVERSE (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+
+      if (! INSN_P (insn))
+	continue;
+
+      df_rd_bb_local_compute_process_def (dflow, bb_info, 
+					  DF_INSN_UID_GET (df, uid)->defs);
+
+      /* This complex dance with the two bitmaps is required because
+	 instructions can assign twice to the same pseudo.  This
+	 generally happens with calls that will have one def for the
+	 result and another def for the clobber.  If only one vector
+	 is used and the clobber goes first, the result will be
+	 lost.  */
+      bitmap_ior_into (seen_in_block, seen_in_insn);
+      bitmap_clear (seen_in_insn);
+    }
+
+  /* Process the artificial defs last since we are going backwards
+     thur the block and these are logically at the start.  */
+  df_rd_bb_local_compute_process_def (dflow, bb_info, 
+				      df_get_artificial_defs (df, bb_index));
+}
+
+
+/* Compute local reaching def info for each basic block within BLOCKS.  */
+
+static void
+df_rd_local_compute (struct dataflow *dflow, 
+		     bitmap all_blocks,
+		     bitmap rescan_blocks  ATTRIBUTE_UNUSED)
+{
+  struct df *df = dflow->df;
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  unsigned int regno;
+  struct df_rd_problem_data *problem_data =
+    (struct df_rd_problem_data *) dflow->problem_data;
+  bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
+  bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
+
+  df_set_seen ();
+
+  if (!df->def_info.refs_organized)
+    df_reorganize_refs (&df->def_info);
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      df_rd_bb_local_compute (dflow, bb_index);
+    }
+  
+  /* Set up the knockout bit vectors to be applied across EH_EDGES.  */
+  EXECUTE_IF_SET_IN_BITMAP (df_invalidated_by_call, 0, regno, bi)
+    {
+      struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno);
+      if (reg_info->n_refs > DF_SPARSE_THRESHOLD)
+	{
+	  bitmap_set_bit (sparse_invalidated, regno);
+	}
+      else
+	{
+	  bitmap defs = df_ref_bitmap (problem_data->def_sites, regno, 
+				       reg_info->begin, reg_info->n_refs);
+	  bitmap_ior_into (dense_invalidated, defs);
+	}
+    }
+  df_unset_seen ();
+}
+
+
+/* Initialize the solution bit vectors for problem.  */
+
+static void 
+df_rd_init_solution (struct dataflow *dflow, bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+      
+      bitmap_copy (bb_info->out, bb_info->gen);
+      bitmap_clear (bb_info->in);
+    }
+}
+
+/* In of target gets or of out of source.  */
+
+static void
+df_rd_confluence_n (struct dataflow *dflow, edge e)
+{
+  bitmap op1 = df_rd_get_bb_info (dflow, e->dest->index)->in;
+  bitmap op2 = df_rd_get_bb_info (dflow, e->src->index)->out;
+
+  if (e->flags & EDGE_EH)
+    {
+      struct df_rd_problem_data *problem_data =
+	(struct df_rd_problem_data *) dflow->problem_data;
+      bitmap sparse_invalidated = problem_data->sparse_invalidated_by_call;
+      bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
+      struct df *df = dflow->df;
+      bitmap_iterator bi;
+      unsigned int regno;
+      bitmap_ior_and_compl_into (op1, op2, dense_invalidated);
+      EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
+ 	{
+ 	  bitmap_clear_range (op1, 
+ 			      DF_REG_DEF_GET (df, regno)->begin, 
+ 			      DF_REG_DEF_GET (df, regno)->n_refs);
+	}
+    }
+  else
+    bitmap_ior_into (op1, op2);
+}
+
+
+/* Transfer function.  */
+
+static bool
+df_rd_transfer_function (struct dataflow *dflow, int bb_index)
+{
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb_index);
+  unsigned int regno;
+  bitmap_iterator bi;
+  bitmap in = bb_info->in;
+  bitmap out = bb_info->out;
+  bitmap gen = bb_info->gen;
+  bitmap kill = bb_info->kill;
+  bitmap sparse_kill = bb_info->sparse_kill;
+
+  if (bitmap_empty_p (sparse_kill))
+    return  bitmap_ior_and_compl (out, gen, in, kill);
+  else 
+    {
+      struct df *df = dflow->df;
+      bool changed = false;
+      bitmap tmp = BITMAP_ALLOC (NULL);
+      bitmap_copy (tmp, in);
+      EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
+	{
+	  bitmap_clear_range (tmp, 
+			      DF_REG_DEF_GET (df, regno)->begin, 
+			      DF_REG_DEF_GET (df, regno)->n_refs);
+	}
+      bitmap_and_compl_into (tmp, kill);
+      bitmap_ior_into (tmp, gen);
+      changed = !bitmap_equal_p (tmp, out);
+      if (changed)
+	{
+	  BITMAP_FREE (out);
+	  bb_info->out = tmp;
+	}
+      else 
+	  BITMAP_FREE (tmp);
+      return changed;
+    }
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_rd_free (struct dataflow *dflow)
+{
+  unsigned int i;
+  struct df_rd_problem_data *problem_data =
+    (struct df_rd_problem_data *) dflow->problem_data;
+
+  for (i = 0; i < dflow->block_info_size; i++)
+    {
+      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, i);
+      if (bb_info)
+	{
+	  BITMAP_FREE (bb_info->kill);
+	  BITMAP_FREE (bb_info->sparse_kill);
+	  BITMAP_FREE (bb_info->gen);
+	  BITMAP_FREE (bb_info->in);
+	  BITMAP_FREE (bb_info->out);
+	}
+    }
+
+  free_alloc_pool (dflow->block_pool);
+
+  for (i = 0; i < problem_data->def_sites_size; i++)
+    {
+      bitmap bm = problem_data->def_sites[i];
+      if (bm)
+	BITMAP_FREE (bm);
+    }
+
+  free (problem_data->def_sites);
+  BITMAP_FREE (problem_data->sparse_invalidated_by_call);
+  BITMAP_FREE (problem_data->dense_invalidated_by_call);
+
+  dflow->block_info_size = 0;
+  free (dflow->block_info);
+  free (dflow->problem_data);
+  free (dflow);
+}
+
+
+/* Debugging info.  */
+
+static void
+df_rd_dump (struct dataflow *dflow, FILE *file)
+{
+  struct df *df = dflow->df;
+  basic_block bb;
+  struct df_rd_problem_data *problem_data =
+    (struct df_rd_problem_data *) dflow->problem_data;
+  unsigned int m = max_reg_num ();
+  unsigned int regno;
+  
+  fprintf (file, "Reaching defs:\n\n");
+
+  fprintf (file, "  sparse invalidated \t");
+  dump_bitmap (file, problem_data->sparse_invalidated_by_call);
+  fprintf (file, "  dense invalidated \t");
+  dump_bitmap (file, problem_data->dense_invalidated_by_call);
+
+  for (regno = 0; regno < m; regno++)
+    if (DF_REG_DEF_GET (df, regno)->n_refs)
+      fprintf (file, "%d[%d,%d] ", regno, 
+	       DF_REG_DEF_GET (df, regno)->begin, 
+	       DF_REG_DEF_GET (df, regno)->n_refs);
+  fprintf (file, "\n");
+
+  FOR_ALL_BB (bb)
+    {
+      struct df_rd_bb_info *bb_info = df_rd_get_bb_info (dflow, bb->index);
+      df_print_bb_index (bb, file);
+      
+      if (! bb_info->in)
+	continue;
+      
+      fprintf (file, "  in\t(%d)\n", (int) bitmap_count_bits (bb_info->in));
+      dump_bitmap (file, bb_info->in);
+      fprintf (file, "  gen \t(%d)\n", (int) bitmap_count_bits (bb_info->gen));
+      dump_bitmap (file, bb_info->gen);
+      fprintf (file, "  kill\t(%d)\n", (int) bitmap_count_bits (bb_info->kill));
+      dump_bitmap (file, bb_info->kill);
+      fprintf (file, "  out\t(%d)\n", (int) bitmap_count_bits (bb_info->out));
+      dump_bitmap (file, bb_info->out);
+    }
+}
+
+/* All of the information associated with every instance of the problem.  */
+
+static struct df_problem problem_RD =
+{
+  DF_RD,                      /* Problem id.  */
+  DF_FORWARD,                 /* Direction.  */
+  df_rd_alloc,                /* Allocate the problem specific data.  */
+  df_rd_free_bb_info,         /* Free basic block info.  */
+  df_rd_local_compute,        /* Local compute function.  */
+  df_rd_init_solution,        /* Init the solution specific data.  */
+  df_iterative_dataflow,      /* Iterative solver.  */
+  NULL,                       /* Confluence operator 0.  */ 
+  df_rd_confluence_n,         /* Confluence operator n.  */ 
+  df_rd_transfer_function,    /* Transfer function.  */
+  NULL,                       /* Finalize function.  */
+  df_rd_free,                 /* Free all of the problem information.  */
+  df_rd_dump,                 /* Debugging.  */
+  NULL                        /* Dependent problem.  */
+};
+
+
+
+/* Create a new DATAFLOW instance and add it to an existing instance
+   of DF.  The returned structure is what is used to get at the
+   solution.  */
+
+struct dataflow *
+df_rd_add_problem (struct df *df)
+{
+  return df_add_problem (df, &problem_RD);
+}
+
+
+
+/*----------------------------------------------------------------------------
+   LIVE REGISTERS
+
+   Find the locations in the function where any use of a pseudo can reach
+   in the backwards direction.
+----------------------------------------------------------------------------*/
+
+/* Get basic block info.  */
+
+struct df_lr_bb_info *
+df_lr_get_bb_info (struct dataflow *dflow, unsigned int index)
+{
+  return (struct df_lr_bb_info *) dflow->block_info[index];
+}
+
+
+/* Set basic block info.  */
+
+static void
+df_lr_set_bb_info (struct dataflow *dflow, unsigned int index, 
+		   struct df_lr_bb_info *bb_info)
+{
+  dflow->block_info[index] = bb_info;
+}
+
+ 
+/* Free basic block info.  */
+
+static void
+df_lr_free_bb_info (struct dataflow *dflow, void *vbb_info)
+{
+  struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
+  if (bb_info)
+    {
+      BITMAP_FREE (bb_info->use);
+      BITMAP_FREE (bb_info->def);
+      BITMAP_FREE (bb_info->in);
+      BITMAP_FREE (bb_info->out);
+      pool_free (dflow->block_pool, bb_info);
+    }
+}
+
+
+/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+   not touched unless the block is new.  */
+
+static void 
+df_lr_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  if (! dflow->block_pool)
+    dflow->block_pool = create_alloc_pool ("df_lr_block pool", 
+					   sizeof (struct df_lr_bb_info), 50);
+
+  df_grow_bb_info (dflow);
+
+  /* Because of the clustering of all def sites for the same pseudo,
+     we have to process all of the blocks before doing the
+     analysis.  */
+
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+    {
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+      if (bb_info)
+	{ 
+	  bitmap_clear (bb_info->def);
+	  bitmap_clear (bb_info->use);
+	}
+      else
+	{ 
+	  bb_info = (struct df_lr_bb_info *) pool_alloc (dflow->block_pool);
+	  df_lr_set_bb_info (dflow, bb_index, bb_info);
+	  bb_info->use = BITMAP_ALLOC (NULL);
+	  bb_info->def = BITMAP_ALLOC (NULL);
+	  bb_info->in = BITMAP_ALLOC (NULL);
+	  bb_info->out = BITMAP_ALLOC (NULL);
+	}
+    }
+}
+
+
+/* Compute local live register info for basic block BB.  */
+
+static void
+df_lr_bb_local_compute (struct dataflow *dflow, 
+			struct df *df, unsigned int bb_index)
+{
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+  rtx insn;
+  struct df_ref *def;
+  struct df_ref *use;
+
+  /* Process the hardware registers that are always live.  */
+  for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
+    /* Add use to set of uses in this BB.  */
+    if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
+      bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
+
+  FOR_BB_INSNS_REVERSE (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+
+      if (! INSN_P (insn))
+	continue;	
+
+      if (CALL_P (insn))
+	{
+	  for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+	    {
+	      unsigned int dregno = DF_REF_REGNO (def);
+	      
+	      if (dregno >= FIRST_PSEUDO_REGISTER
+		  || !(SIBLING_CALL_P (insn)
+		       && bitmap_bit_p (df->exit_block_uses, dregno)
+		       && !refers_to_regno_p (dregno, dregno+1,
+					      current_function_return_rtx,
+					      (rtx *)0)))
+		{
+		  /* Add def to set of defs in this BB.  */
+		  bitmap_set_bit (bb_info->def, dregno);
+		  bitmap_clear_bit (bb_info->use, dregno);
+		}
+	    }
+	}
+      else
+	{
+	  for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+	    {
+	      unsigned int dregno = DF_REF_REGNO (def);
+	      
+	      if (DF_INSN_CONTAINS_ASM (df, insn) 
+		  && dregno < FIRST_PSEUDO_REGISTER)
+		{
+		  unsigned int i;
+		  unsigned int end = 
+		    dregno + hard_regno_nregs[dregno][GET_MODE (DF_REF_REG (def))] - 1;
+		  for (i = dregno; i <= end; ++i)
+		    regs_asm_clobbered[i] = 1;
+		}
+	      /* Add def to set of defs in this BB.  */
+	      bitmap_set_bit (bb_info->def, dregno);
+	      bitmap_clear_bit (bb_info->use, dregno);
+	    }
+	}
+
+      for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
+	/* Add use to set of uses in this BB.  */
+	bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
+    }
+
+  /* Process the registers set in an exception handler.  */
+  for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
+    {
+      unsigned int dregno = DF_REF_REGNO (def);
+      bitmap_set_bit (bb_info->def, dregno);
+      bitmap_clear_bit (bb_info->use, dregno);
+    }
+
+#ifdef EH_USES
+  /* Process the uses that are live into an exception handler.  */
+  for (use = df_get_artificial_uses (df, bb_index); use; use = use->next_ref)
+    /* Add use to set of uses in this BB.  */
+    if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
+      bitmap_set_bit (bb_info->use, DF_REF_REGNO (use));
+#endif
+}
+
+/* Compute local live register info for each basic block within BLOCKS.  */
+
+static void
+df_lr_local_compute (struct dataflow *dflow, 
+		     bitmap all_blocks,
+		     bitmap rescan_blocks)
+{
+  struct df *df = dflow->df;
+  unsigned int bb_index;
+  bitmap_iterator bi;
+    
+  /* Assume that the stack pointer is unchanging if alloca hasn't
+     been used.  */
+  if (bitmap_equal_p (all_blocks, rescan_blocks))
+    memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered));
+  
+  bitmap_clear (df->hardware_regs_used);
+  
+  /* The all-important stack pointer must always be live.  */
+  bitmap_set_bit (df->hardware_regs_used, STACK_POINTER_REGNUM);
+  
+  /* Before reload, there are a few registers that must be forced
+     live everywhere -- which might not already be the case for
+     blocks within infinite loops.  */
+  if (! reload_completed)
+    {
+      /* Any reference to any pseudo before reload is a potential
+	 reference of the frame pointer.  */
+      bitmap_set_bit (df->hardware_regs_used, FRAME_POINTER_REGNUM);
+      
+#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
+      /* Pseudos with argument area equivalences may require
+	 reloading via the argument pointer.  */
+      if (fixed_regs[ARG_POINTER_REGNUM])
+	bitmap_set_bit (df->hardware_regs_used, ARG_POINTER_REGNUM);
+#endif
+      
+      /* Any constant, or pseudo with constant equivalences, may
+	 require reloading from memory using the pic register.  */
+      if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
+	  && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
+	bitmap_set_bit (df->hardware_regs_used, PIC_OFFSET_TABLE_REGNUM);
+    }
+  
+  if (bitmap_bit_p (rescan_blocks, EXIT_BLOCK))
+    {
+      /* The exit block is special for this problem and its bits are
+	 computed from thin air.  */
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, EXIT_BLOCK);
+      bitmap_copy (bb_info->use, df->exit_block_uses);
+    }
+  
+  EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
+    {
+      if (bb_index == EXIT_BLOCK)
+	continue;
+      df_lr_bb_local_compute (dflow, df, bb_index);
+    }
+}
+
+
+/* Initialize the solution vectors.  */
+
+static void 
+df_lr_init (struct dataflow *dflow, bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+      bitmap_copy (bb_info->in, bb_info->use);
+      bitmap_clear (bb_info->out);
+    }
+}
+
+
+/* Confluence function that processes infinite loops.  This might be a
+   noreturn function that throws.  And even if it isn't, getting the
+   unwind info right helps debugging.  */
+static void
+df_lr_confluence_0 (struct dataflow *dflow, basic_block bb)
+{
+  struct df *df = dflow->df;
+
+  bitmap op1 = df_lr_get_bb_info (dflow, bb->index)->out;
+  if (bb != EXIT_BLOCK_PTR)
+    bitmap_copy (op1, df->hardware_regs_used);
+} 
+
+
+/* Confluence function that ignores fake edges.  */
+static void
+df_lr_confluence_n (struct dataflow *dflow, edge e)
+{
+  bitmap op1 = df_lr_get_bb_info (dflow, e->src->index)->out;
+  bitmap op2 = df_lr_get_bb_info (dflow, e->dest->index)->in;
+ 
+  /* Call-clobbered registers die across exception and call edges.  */
+  /* ??? Abnormal call edges ignored for the moment, as this gets
+     confused by sibling call edges, which crashes reg-stack.  */
+  if (e->flags & EDGE_EH)
+    bitmap_ior_and_compl_into (op1, op2, df_invalidated_by_call);
+  else
+    bitmap_ior_into (op1, op2);
+
+  bitmap_ior_into (op1, dflow->df->hardware_regs_used);
+} 
+
+
+/* Transfer function.  */
+static bool
+df_lr_transfer_function (struct dataflow *dflow, int bb_index)
+{
+  struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb_index);
+  bitmap in = bb_info->in;
+  bitmap out = bb_info->out;
+  bitmap use = bb_info->use;
+  bitmap def = bb_info->def;
+
+  return bitmap_ior_and_compl (in, use, out, def);
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_lr_free (struct dataflow *dflow)
+{
+  unsigned int i;
+  for (i = 0; i < dflow->block_info_size; i++)
+    {
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, i);
+      if (bb_info)
+	{
+	  BITMAP_FREE (bb_info->use);
+	  BITMAP_FREE (bb_info->def);
+	  BITMAP_FREE (bb_info->in);
+	  BITMAP_FREE (bb_info->out);
+	}
+    }
+  free_alloc_pool (dflow->block_pool);
+
+  dflow->block_info_size = 0;
+  free (dflow->block_info);
+  free (dflow);
+}
+
+
+/* Debugging info.  */
+
+static void
+df_lr_dump (struct dataflow *dflow, FILE *file)
+{
+  basic_block bb;
+  
+  fprintf (file, "Live Registers:\n");
+  FOR_ALL_BB (bb)
+    {
+      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (dflow, bb->index);
+      df_print_bb_index (bb, file);
+      
+      if (!bb_info->in)
+	continue;
+      
+      fprintf (file, "  in  \t");
+      dump_bitmap (file, bb_info->in);
+      fprintf (file, "  use \t");
+      dump_bitmap (file, bb_info->use);
+      fprintf (file, "  def \t");
+      dump_bitmap (file, bb_info->def);
+      fprintf (file, "  out \t");
+      dump_bitmap (file, bb_info->out);
+    }
+}
+
+/* All of the information associated with every instance of the problem.  */
+
+static struct df_problem problem_LR =
+{
+  DF_LR,                      /* Problem id.  */
+  DF_BACKWARD,                /* Direction.  */
+  df_lr_alloc,                /* Allocate the problem specific data.  */
+  df_lr_free_bb_info,         /* Free basic block info.  */
+  df_lr_local_compute,        /* Local compute function.  */
+  df_lr_init,                 /* Init the solution specific data.  */
+  df_iterative_dataflow,      /* Iterative solver.  */
+  df_lr_confluence_0,         /* Confluence operator 0.  */ 
+  df_lr_confluence_n,         /* Confluence operator n.  */ 
+  df_lr_transfer_function,    /* Transfer function.  */
+  NULL,                       /* Finalize function.  */
+  df_lr_free,                 /* Free all of the problem information.  */
+  df_lr_dump,                 /* Debugging.  */
+  NULL                        /* Dependent problem.  */
+};
+
+
+/* Create a new DATAFLOW instance and add it to an existing instance
+   of DF.  The returned structure is what is used to get at the
+   solution.  */
+
+struct dataflow *
+df_lr_add_problem (struct df *df)
+{
+  return df_add_problem (df, &problem_LR);
+}
+
+
+
+/*----------------------------------------------------------------------------
+   UNINITIALIZED REGISTERS
+
+   Find the set of uses for registers that are reachable from the entry
+   block without passing thru a definition.
+----------------------------------------------------------------------------*/
+
+/* Get basic block info.  */
+
+struct df_ur_bb_info *
+df_ur_get_bb_info (struct dataflow *dflow, unsigned int index)
+{
+  return (struct df_ur_bb_info *) dflow->block_info[index];
+}
+
+
+/* Set basic block info.  */
+
+static void
+df_ur_set_bb_info (struct dataflow *dflow, unsigned int index, 
+		   struct df_ur_bb_info *bb_info)
+{
+  dflow->block_info[index] = bb_info;
+}
+
+
+/* Free basic block info.  */
+
+static void
+df_ur_free_bb_info (struct dataflow *dflow, void *vbb_info)
+{
+  struct df_ur_bb_info *bb_info = (struct df_ur_bb_info *) vbb_info;
+  if (bb_info)
+    {
+      BITMAP_FREE (bb_info->gen);
+      BITMAP_FREE (bb_info->kill);
+      BITMAP_FREE (bb_info->in);
+      BITMAP_FREE (bb_info->out);
+      pool_free (dflow->block_pool, bb_info);
+    }
+}
+
+
+/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+   not touched unless the block is new.  */
+
+static void 
+df_ur_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  if (! dflow->block_pool)
+    dflow->block_pool = create_alloc_pool ("df_ur_block pool", 
+					   sizeof (struct df_ur_bb_info), 100);
+
+  df_grow_bb_info (dflow);
+
+  /* Because of the clustering of all def sites for the same pseudo,
+     we have to process all of the blocks before doing the
+     analysis.  */
+
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+    {
+      struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+      if (bb_info)
+	{ 
+	  bitmap_clear (bb_info->kill);
+	  bitmap_clear (bb_info->gen);
+	}
+      else
+	{ 
+	  bb_info = (struct df_ur_bb_info *) pool_alloc (dflow->block_pool);
+	  df_ur_set_bb_info (dflow, bb_index, bb_info);
+	  bb_info->kill = BITMAP_ALLOC (NULL);
+	  bb_info->gen = BITMAP_ALLOC (NULL);
+	  bb_info->in = BITMAP_ALLOC (NULL);
+	  bb_info->out = BITMAP_ALLOC (NULL);
+	}
+    }
+}
+
+
+/* Compute local uninitialized register info for basic block BB.  */
+
+static void
+df_ur_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+{
+  struct df *df = dflow->df;
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+  rtx insn;
+  struct df_ref *def;
+
+  bitmap_clear (seen_in_block);
+  bitmap_clear (seen_in_insn);
+
+  FOR_BB_INSNS_REVERSE (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+      if (!INSN_P (insn))
+	continue;
+
+      for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+	{
+	  unsigned int regno = DF_REF_REGNO (def);
+	      /* Only the last def counts.  */
+	  if (!bitmap_bit_p (seen_in_block, regno))
+	    {
+	      bitmap_set_bit (seen_in_insn, regno);
+	      
+	      if (DF_REF_FLAGS (def) & DF_REF_CLOBBER)
+		bitmap_set_bit (bb_info->kill, regno);
+	      else
+		bitmap_set_bit (bb_info->gen, regno);
+	    }
+	}
+      bitmap_ior_into (seen_in_block, seen_in_insn);
+      bitmap_clear (seen_in_insn);
+    }
+
+  for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
+    {
+      unsigned int regno = DF_REF_REGNO (def);
+      if (!bitmap_bit_p (seen_in_block, regno))
+	{
+	  bitmap_set_bit (seen_in_block, regno);
+	  bitmap_set_bit (bb_info->gen, regno);
+	}
+    }
+}
+
+
+/* Compute local uninitialized register info.  */
+
+static void
+df_ur_local_compute (struct dataflow *dflow, 
+		     bitmap all_blocks ATTRIBUTE_UNUSED,
+		     bitmap rescan_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  df_set_seen ();
+
+  EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
+    {
+      df_ur_bb_local_compute (dflow, bb_index);
+    }
+
+  df_unset_seen ();
+}
+
+
+/* Initialize the solution vectors.  */
+
+static void 
+df_ur_init (struct dataflow *dflow, bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+
+      bitmap_copy (bb_info->out, bb_info->gen);
+      bitmap_clear (bb_info->in);
+    }
+}
+
+
+/* Or in the stack regs, hard regs and early clobber regs into the the
+   ur_in sets of all of the blocks.  */
+
+static void
+df_ur_local_finalize (struct dataflow *dflow, bitmap all_blocks)
+{
+  struct df *df = dflow->df;
+  struct dataflow *lr_dflow = df->problems_by_index[DF_LR];
+  bitmap tmp = BITMAP_ALLOC (NULL);
+  bitmap_iterator bi;
+  unsigned int bb_index;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+      struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index);
+      
+      bitmap_ior_into (bb_info->in, df_all_hard_regs);
+      bitmap_ior_into (bb_info->out, df_all_hard_regs);
+
+      /* No register may reach a location where it is not used.  Thus
+	 we trim the rr result to the places where it is used.  */
+      bitmap_and_into (bb_info->in, bb_lr_info->in);
+      bitmap_and_into (bb_info->out, bb_lr_info->out);
+      
+#if 1
+      /* Hard registers may still stick in the ur_out set, but not
+	 be in the ur_in set, if their only mention was in a call
+	 in this block.  This is because a call kills in the lr
+	 problem but does not kill in the ur problem.  To clean
+	 this up, we execute the transfer function on the lr_in
+	 set and then use that to knock bits out of ur_out.  */
+      bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in, 
+			    bb_info->kill);
+      bitmap_and_into (bb_info->out, tmp);
+#endif
+    }
+  
+  BITMAP_FREE (tmp);
+}
+
+
+/* Confluence function that ignores fake edges.  */
+
+static void
+df_ur_confluence_n (struct dataflow *dflow, edge e)
+{
+  bitmap op1 = df_ur_get_bb_info (dflow, e->dest->index)->in;
+  bitmap op2 = df_ur_get_bb_info (dflow, e->src->index)->out;
+ 
+  if (e->flags & EDGE_FAKE) 
+    return;
+
+  bitmap_ior_into (op1, op2);
+} 
+
+
+/* Transfer function.  */
+
+static bool
+df_ur_transfer_function (struct dataflow *dflow, int bb_index)
+{
+  struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+  bitmap in = bb_info->in;
+  bitmap out = bb_info->out;
+  bitmap gen = bb_info->gen;
+  bitmap kill = bb_info->kill;
+
+  return bitmap_ior_and_compl (out, gen, in, kill);
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_ur_free (struct dataflow *dflow)
+{
+  unsigned int i;
+
+  for (i = 0; i < dflow->block_info_size; i++)
+    {
+      struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, i);
+      if (bb_info)
+	{
+	  BITMAP_FREE (bb_info->gen);
+	  BITMAP_FREE (bb_info->kill);
+	  BITMAP_FREE (bb_info->in);
+	  BITMAP_FREE (bb_info->out);
+	}
+    }
+
+  free_alloc_pool (dflow->block_pool);
+  dflow->block_info_size = 0;
+  free (dflow->block_info);
+  free (dflow);
+}
+
+
+/* Debugging info.  */
+
+static void
+df_ur_dump (struct dataflow *dflow, FILE *file)
+{
+  basic_block bb;
+  
+  fprintf (file, "Undefined regs:\n");
+ 
+  FOR_ALL_BB (bb)
+    {
+      struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb->index);
+      df_print_bb_index (bb, file);
+      
+      if (! bb_info->in)
+	continue;
+      
+      fprintf (file, "  in  \t");
+      dump_bitmap (file, bb_info->in);
+      fprintf (file, "  gen \t");
+      dump_bitmap (file, bb_info->gen);
+      fprintf (file, "  kill\t");
+      dump_bitmap (file, bb_info->kill);
+      fprintf (file, "  out \t");
+      dump_bitmap (file, bb_info->out);
+    }
+}
+
+/* All of the information associated with every instance of the problem.  */
+
+static struct df_problem problem_UR =
+{
+  DF_UR,                      /* Problem id.  */
+  DF_FORWARD,                 /* Direction.  */
+  df_ur_alloc,                /* Allocate the problem specific data.  */
+  df_ur_free_bb_info,         /* Free basic block info.  */
+  df_ur_local_compute,        /* Local compute function.  */
+  df_ur_init,                 /* Init the solution specific data.  */
+  df_iterative_dataflow,      /* Iterative solver.  */
+  NULL,                       /* Confluence operator 0.  */ 
+  df_ur_confluence_n,         /* Confluence operator n.  */ 
+  df_ur_transfer_function,    /* Transfer function.  */
+  df_ur_local_finalize,       /* Finalize function.  */
+  df_ur_free,                 /* Free all of the problem information.  */
+  df_ur_dump,                 /* Debugging.  */
+  &problem_LR                 /* Dependent problem.  */
+};
+
+
+/* Create a new DATAFLOW instance and add it to an existing instance
+   of DF.  The returned structure is what is used to get at the
+   solution.  */
+
+struct dataflow *
+df_ur_add_problem (struct df *df)
+{
+  return df_add_problem (df, &problem_UR);
+}
+
+
+
+/*----------------------------------------------------------------------------
+   UNINITIALIZED REGISTERS WITH EARLYCLOBBER
+
+   Find the set of uses for registers that are reachable from the entry
+   block without passing thru a definition.
+
+   This is a variant of the UR problem above that has a lot of special
+   features just for the register allocation phase.
+----------------------------------------------------------------------------*/
+
+struct df_urec_problem_data
+{
+  bool earlyclobbers_found;     /* True if any instruction contains an
+				   earlyclobber.  */
+#ifdef STACK_REGS
+  bitmap stack_regs;		/* Registers that may be allocated to a STACK_REGS.  */
+#endif
+};
+
+
+/* Get basic block info.  */
+
+struct df_urec_bb_info *
+df_urec_get_bb_info (struct dataflow *dflow, unsigned int index)
+{
+  return (struct df_urec_bb_info *) dflow->block_info[index];
+}
+
+
+/* Set basic block info.  */
+
+static void
+df_urec_set_bb_info (struct dataflow *dflow, unsigned int index, 
+		   struct df_urec_bb_info *bb_info)
+{
+  dflow->block_info[index] = bb_info;
+}
+
+
+/* Free basic block info.  */
+
+static void
+df_urec_free_bb_info (struct dataflow *dflow, void *vbb_info)
+{
+  struct df_urec_bb_info *bb_info = (struct df_urec_bb_info *) vbb_info;
+  if (bb_info)
+    {
+      BITMAP_FREE (bb_info->gen);
+      BITMAP_FREE (bb_info->kill);
+      BITMAP_FREE (bb_info->in);
+      BITMAP_FREE (bb_info->out);
+      BITMAP_FREE (bb_info->earlyclobber);
+      pool_free (dflow->block_pool, bb_info);
+    }
+}
+
+
+/* Allocate or reset bitmaps for DFLOW blocks. The solution bits are
+   not touched unless the block is new.  */
+
+static void 
+df_urec_alloc (struct dataflow *dflow, bitmap blocks_to_rescan)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  struct df_urec_problem_data *problem_data =
+    (struct df_urec_problem_data *) dflow->problem_data;
+
+  if (! dflow->block_pool)
+    dflow->block_pool = create_alloc_pool ("df_urec_block pool", 
+					   sizeof (struct df_urec_bb_info), 50);
+
+  if (!dflow->problem_data)
+    {
+      problem_data = xmalloc (sizeof (struct df_urec_problem_data));
+      dflow->problem_data = problem_data;
+    }
+  problem_data->earlyclobbers_found = false;
+
+  df_grow_bb_info (dflow);
+
+  /* Because of the clustering of all def sites for the same pseudo,
+     we have to process all of the blocks before doing the
+     analysis.  */
+
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_rescan, 0, bb_index, bi)
+    {
+      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
+      if (bb_info)
+	{ 
+	  bitmap_clear (bb_info->kill);
+	  bitmap_clear (bb_info->gen);
+	  bitmap_clear (bb_info->earlyclobber);
+	}
+      else
+	{ 
+	  bb_info = (struct df_urec_bb_info *) pool_alloc (dflow->block_pool);
+	  df_urec_set_bb_info (dflow, bb_index, bb_info);
+	  bb_info->kill = BITMAP_ALLOC (NULL);
+	  bb_info->gen = BITMAP_ALLOC (NULL);
+	  bb_info->in = BITMAP_ALLOC (NULL);
+	  bb_info->out = BITMAP_ALLOC (NULL);
+	  bb_info->earlyclobber = BITMAP_ALLOC (NULL);
+	}
+    }
+}
+
+
+/* The function modifies local info for register REG being changed in
+   SETTER.  DATA is used to pass the current basic block info.  */
+
+static void
+df_urec_mark_reg_change (rtx reg, rtx setter, void *data)
+{
+  int regno;
+  int endregno;
+  int i;
+  struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
+
+  if (GET_CODE (reg) == SUBREG)
+    reg = SUBREG_REG (reg);
+
+  if (!REG_P (reg))
+    return;
+  
+  
+  endregno = regno = REGNO (reg);
+  if (regno < FIRST_PSEUDO_REGISTER)
+    {
+      endregno +=hard_regno_nregs[regno][GET_MODE (reg)];
+      
+      for (i = regno; i < endregno; i++)
+	{
+	  bitmap_set_bit (bb_info->kill, i);
+	  
+	  if (GET_CODE (setter) != CLOBBER)
+	    bitmap_set_bit (bb_info->gen, i);
+	  else
+	    bitmap_clear_bit (bb_info->gen, i);
+	}
+    }
+  else
+    {
+      bitmap_set_bit (bb_info->kill, regno);
+      
+      if (GET_CODE (setter) != CLOBBER)
+	bitmap_set_bit (bb_info->gen, regno);
+      else
+	bitmap_clear_bit (bb_info->gen, regno);
+    }
+}
+/* Classes of registers which could be early clobbered in the current
+   insn.  */
+
+DEF_VEC_I(int);
+DEF_VEC_ALLOC_I(int,heap);
+
+static VEC(int,heap) *earlyclobber_regclass;
+
+/* This function finds and stores register classes that could be early
+   clobbered in INSN.  If any earlyclobber classes are found, the function
+   returns TRUE, in all other cases it returns FALSE.  */
+
+static bool
+df_urec_check_earlyclobber (rtx insn)
+{
+  int opno;
+  bool found = false;
+
+  extract_insn (insn);
+
+  VEC_truncate (int, earlyclobber_regclass, 0);
+  for (opno = 0; opno < recog_data.n_operands; opno++)
+    {
+      char c;
+      bool amp_p;
+      int i;
+      enum reg_class class;
+      const char *p = recog_data.constraints[opno];
+
+      class = NO_REGS;
+      amp_p = false;
+      for (;;)
+	{
+	  c = *p;
+	  switch (c)
+	    {
+	    case '=':  case '+':  case '?':
+	    case '#':  case '!':
+	    case '*':  case '%':
+	    case 'm':  case '<':  case '>':  case 'V':  case 'o':
+	    case 'E':  case 'F':  case 'G':  case 'H':
+	    case 's':  case 'i':  case 'n':
+	    case 'I':  case 'J':  case 'K':  case 'L':
+	    case 'M':  case 'N':  case 'O':  case 'P':
+	    case 'X':
+	    case '0': case '1':  case '2':  case '3':  case '4':
+	    case '5': case '6':  case '7':  case '8':  case '9':
+	      /* These don't say anything we care about.  */
+	      break;
+
+	    case '&':
+	      amp_p = true;
+	      break;
+	    case '\0':
+	    case ',':
+	      if (amp_p && class != NO_REGS)
+		{
+		  int rc;
+
+		  found = true;
+		  for (i = 0;
+		       VEC_iterate (int, earlyclobber_regclass, i, rc);
+		       i++)
+		    {
+		      if (rc == (int) class)
+			goto found_rc;
+		    }
+
+		  /* We use VEC_quick_push here because
+		     earlyclobber_regclass holds no more than
+		     N_REG_CLASSES elements. */
+		  VEC_quick_push (int, earlyclobber_regclass, (int) class);
+		found_rc:
+		  ;
+		}
+	      
+	      amp_p = false;
+	      class = NO_REGS;
+	      break;
+
+	    case 'r':
+	      class = GENERAL_REGS;
+	      break;
+
+	    default:
+	      class = REG_CLASS_FROM_CONSTRAINT (c, p);
+	      break;
+	    }
+	  if (c == '\0')
+	    break;
+	  p += CONSTRAINT_LEN (c, p);
+	}
+    }
+
+  return found;
+}
+
+/* The function checks that pseudo-register *X has a class
+   intersecting with the class of pseudo-register could be early
+   clobbered in the same insn.
+
+   This function is a no-op if earlyclobber_regclass is empty. 
+
+   Reload can assign the same hard register to uninitialized
+   pseudo-register and early clobbered pseudo-register in an insn if
+   the pseudo-register is used first time in given BB and not lived at
+   the BB start.  To prevent this we don't change life information for
+   such pseudo-registers.  */
+
+static int
+df_urec_mark_reg_use_for_earlyclobber (rtx *x, void *data)
+{
+  enum reg_class pref_class, alt_class;
+  int i, regno;
+  struct df_urec_bb_info *bb_info = (struct df_urec_bb_info*) data;
+
+  if (REG_P (*x) && REGNO (*x) >= FIRST_PSEUDO_REGISTER)
+    {
+      int rc;
+
+      regno = REGNO (*x);
+      if (bitmap_bit_p (bb_info->kill, regno)
+	  || bitmap_bit_p (bb_info->gen, regno))
+	return 0;
+      pref_class = reg_preferred_class (regno);
+      alt_class = reg_alternate_class (regno);
+      for (i = 0; VEC_iterate (int, earlyclobber_regclass, i, rc); i++)
+	{
+	  if (reg_classes_intersect_p (rc, pref_class)
+	      || (rc != NO_REGS
+		  && reg_classes_intersect_p (rc, alt_class)))
+	    {
+	      bitmap_set_bit (bb_info->earlyclobber, regno);
+	      break;
+	    }
+	}
+    }
+  return 0;
+}
+
+/* The function processes all pseudo-registers in *X with the aid of
+   previous function.  */
+
+static void
+df_urec_mark_reg_use_for_earlyclobber_1 (rtx *x, void *data)
+{
+  for_each_rtx (x, df_urec_mark_reg_use_for_earlyclobber, data);
+}
+
+
+/* Compute local uninitialized register info for basic block BB.  */
+
+static void
+df_urec_bb_local_compute (struct dataflow *dflow, unsigned int bb_index)
+{
+  struct df *df = dflow->df;
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
+  rtx insn;
+  struct df_ref *def;
+
+  for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
+    {
+      unsigned int regno = DF_REF_REGNO (def);
+      bitmap_set_bit (bb_info->gen, regno);
+    }
+
+  FOR_BB_INSNS (bb, insn)
+    {
+      if (INSN_P (insn))
+	{
+	  note_stores (PATTERN (insn), df_urec_mark_reg_change, bb_info);
+	  if (df_state & (DF_SCAN_GLOBAL | DF_SCAN_POST_ALLOC) 
+	      && df_urec_check_earlyclobber (insn))
+	    {
+	      struct df_urec_problem_data *problem_data =
+		(struct df_urec_problem_data *) dflow->problem_data;
+	      problem_data->earlyclobbers_found = true;
+	      note_uses (&PATTERN (insn), 
+			 df_urec_mark_reg_use_for_earlyclobber_1, bb_info);
+	    }
+	}
+    }
+}
+
+
+/* Compute local uninitialized register info.  */
+
+static void
+df_urec_local_compute (struct dataflow *dflow, 
+		     bitmap all_blocks ATTRIBUTE_UNUSED,
+		     bitmap rescan_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+#ifdef STACK_REGS
+  int i;
+  HARD_REG_SET zero, stack_hard_regs, used;
+  struct df_urec_problem_data *problem_data =
+    (struct df_urec_problem_data *) dflow->problem_data;
+  
+  /* Any register that MAY be allocated to a register stack (like the
+     387) is treated poorly.  Each such register is marked as being
+     live everywhere.  This keeps the register allocator and the
+     subsequent passes from doing anything useful with these values.
+
+     FIXME: This seems like an incredibly poor idea.  */
+
+  CLEAR_HARD_REG_SET (zero);
+  CLEAR_HARD_REG_SET (stack_hard_regs);
+  for (i = FIRST_STACK_REG; i <= LAST_STACK_REG; i++)
+    SET_HARD_REG_BIT (stack_hard_regs, i);
+  problem_data->stack_regs = BITMAP_ALLOC (NULL);
+  for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
+    {
+      COPY_HARD_REG_SET (used, reg_class_contents[reg_preferred_class (i)]);
+      IOR_HARD_REG_SET (used, reg_class_contents[reg_alternate_class (i)]);
+      AND_HARD_REG_SET (used, stack_hard_regs);
+      GO_IF_HARD_REG_EQUAL (used, zero, skip);
+      bitmap_set_bit (problem_data->stack_regs, i);
+    skip:
+      ;
+    }
+#endif
+
+  /* We know that earlyclobber_regclass holds no more than
+    N_REG_CLASSES elements.  See df_urec_check_earlyclobber.  */
+  earlyclobber_regclass = VEC_alloc (int, heap, N_REG_CLASSES);
+
+  EXECUTE_IF_SET_IN_BITMAP (rescan_blocks, 0, bb_index, bi)
+    {
+      df_urec_bb_local_compute (dflow, bb_index);
+    }
+
+  VEC_free (int, heap, earlyclobber_regclass);
+}
+
+
+/* Initialize the solution vectors.  */
+
+static void 
+df_urec_init (struct dataflow *dflow, bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
+
+      /* FIXME: This is a hack, it has been copied over from
+	 make_accurate_live_analysis by Vlad.  Most likely it is necessary
+	 because the generation of gen and kill information for hardware
+	 registers in ur is a subset of what is really necessary and what
+	 is done for the lr problem.  */
+      
+      /* Inside the register allocator, partial availability is only
+	 allowed for the psuedo registers.  To implement this, the rr is
+	 initially iored with a mask ones for the hard registers and zeros
+	 for the pseudos before being iterated.  This means that each
+	 hardware register will be live unless explicitly killed by some
+	 statement.  Eventually most of these bit will die because the
+	 results of rr are anded with the results of lr before being used.
+	 Outside of register allocation, a more conservative strategy of
+	 completely ignoring the unintialized registers is imployed in the
+	 finalizer function.  */
+      if (df_state & DF_SCAN_GLOBAL)
+	{
+	  bitmap_ior (bb_info->out, bb_info->gen, df_all_hard_regs);
+	  bitmap_copy (bb_info->in, df_all_hard_regs);
+	}
+      else
+	{
+	  bitmap_copy (bb_info->out, bb_info->gen);
+	  bitmap_clear (bb_info->in);
+	}
+    }
+}
+
+
+/* Or in the stack regs, hard regs and early clobber regs into the the
+   ur_in sets of all of the blocks.  */
+
+static void
+df_urec_local_finalize (struct dataflow *dflow, bitmap all_blocks)
+{
+  struct df *df = dflow->df;
+  struct dataflow *lr_dflow = df->problems_by_index[DF_LR];
+  bitmap tmp = BITMAP_ALLOC (NULL);
+  bitmap_iterator bi;
+  unsigned int bb_index;
+  struct df_urec_problem_data *problem_data =
+    (struct df_urec_problem_data *) dflow->problem_data;
+
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
+      struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (lr_dflow, bb_index);
+
+      if (bb_index != ENTRY_BLOCK && bb_index != EXIT_BLOCK)
+	{
+	  if (problem_data->earlyclobbers_found)
+	    bitmap_ior_into (bb_info->in, bb_info->earlyclobber);
+	
+#ifdef STACK_REGS
+	  /* We can not use the same stack register for uninitialized
+	     pseudo-register and another living pseudo-register
+	     because if the uninitialized pseudo-register dies,
+	     subsequent pass reg-stack will be confused (it will
+	     believe that the other register dies).  */
+	  bitmap_ior_into (bb_info->in, problem_data->stack_regs);
+	  bitmap_ior_into (bb_info->out, problem_data->stack_regs);
+#endif
+	}
+
+      if (!(df_state & DF_SCAN_GLOBAL))
+	{
+	  bitmap_ior_into (bb_info->in, df_all_hard_regs);
+	  bitmap_ior_into (bb_info->out, df_all_hard_regs);
+	}
+
+      /* No register may reach a location where it is not used.  Thus
+	 we trim the rr result to the places where it is used.  */
+      bitmap_and_into (bb_info->in, bb_lr_info->in);
+      bitmap_and_into (bb_info->out, bb_lr_info->out);
+      
+#if 1
+      /* Hard registers may still stick in the ur_out set, but not
+	 be in the ur_in set, if their only mention was in a call
+	 in this block.  This is because a call kills in the lr
+	 problem but does not kill in the rr problem.  To clean
+	 this up, we execute the transfer function on the lr_in
+	 set and then use that to knock bits out of ur_out.  */
+      bitmap_ior_and_compl (tmp, bb_info->gen, bb_lr_info->in, 
+			    bb_info->kill);
+      bitmap_and_into (bb_info->out, tmp);
+#endif
+    }
+  
+#ifdef STACK_REGS
+  BITMAP_FREE (problem_data->stack_regs);
+#endif
+  BITMAP_FREE (tmp);
+}
+
+
+/* Confluence function that ignores fake edges.  */
+
+static void
+df_urec_confluence_n (struct dataflow *dflow, edge e)
+{
+  bitmap op1 = df_urec_get_bb_info (dflow, e->dest->index)->in;
+  bitmap op2 = df_urec_get_bb_info (dflow, e->src->index)->out;
+ 
+  if (e->flags & EDGE_FAKE) 
+    return;
+
+  bitmap_ior_into (op1, op2);
+} 
+
+
+/* Transfer function.  */
+
+static bool
+df_urec_transfer_function (struct dataflow *dflow, int bb_index)
+{
+  struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb_index);
+  bitmap in = bb_info->in;
+  bitmap out = bb_info->out;
+  bitmap gen = bb_info->gen;
+  bitmap kill = bb_info->kill;
+
+  return bitmap_ior_and_compl (out, gen, in, kill);
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_urec_free (struct dataflow *dflow)
+{
+  unsigned int i;
+
+  for (i = 0; i < dflow->block_info_size; i++)
+    {
+      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, i);
+      if (bb_info)
+	{
+	  BITMAP_FREE (bb_info->gen);
+	  BITMAP_FREE (bb_info->kill);
+	  BITMAP_FREE (bb_info->in);
+	  BITMAP_FREE (bb_info->out);
+	  BITMAP_FREE (bb_info->earlyclobber);
+	}
+    }
+
+  free_alloc_pool (dflow->block_pool);
+  
+  dflow->block_info_size = 0;
+  free (dflow->block_info);
+  free (dflow->problem_data);
+  free (dflow);
+}
+
+
+/* Debugging info.  */
+
+static void
+df_urec_dump (struct dataflow *dflow, FILE *file)
+{
+  basic_block bb;
+  
+  fprintf (file, "Undefined regs:\n");
+ 
+  FOR_ALL_BB (bb)
+    {
+      struct df_urec_bb_info *bb_info = df_urec_get_bb_info (dflow, bb->index);
+      df_print_bb_index (bb, file);
+      
+      if (! bb_info->in)
+	continue;
+      
+      fprintf (file, "  in  \t");
+      dump_bitmap (file, bb_info->in);
+      fprintf (file, "  gen \t");
+      dump_bitmap (file, bb_info->gen);
+      fprintf (file, "  kill\t");
+      dump_bitmap (file, bb_info->kill);
+      fprintf (file, "  ec\t");
+      dump_bitmap (file, bb_info->earlyclobber);
+      fprintf (file, "  out \t");
+      dump_bitmap (file, bb_info->out);
+    }
+}
+
+/* All of the information associated with every instance of the problem.  */
+
+static struct df_problem problem_UREC =
+{
+  DF_UREC,                    /* Problem id.  */
+  DF_FORWARD,                 /* Direction.  */
+  df_urec_alloc,              /* Allocate the problem specific data.  */
+  df_urec_free_bb_info,       /* Free basic block info.  */
+  df_urec_local_compute,      /* Local compute function.  */
+  df_urec_init,               /* Init the solution specific data.  */
+  df_iterative_dataflow,      /* Iterative solver.  */
+  NULL,                       /* Confluence operator 0.  */ 
+  df_urec_confluence_n,       /* Confluence operator n.  */ 
+  df_urec_transfer_function,  /* Transfer function.  */
+  df_urec_local_finalize,     /* Finalize function.  */
+  df_urec_free,               /* Free all of the problem information.  */
+  df_urec_dump,               /* Debugging.  */
+  &problem_LR                 /* Dependent problem.  */
+};
+
+
+/* Create a new DATAFLOW instance and add it to an existing instance
+   of DF.  The returned structure is what is used to get at the
+   solution.  */
+
+struct dataflow *
+df_urec_add_problem (struct df *df)
+{
+  return df_add_problem (df, &problem_UREC);
+}
+
+
+
+/*----------------------------------------------------------------------------
+   CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
+
+   Link either the defs to the uses and / or the uses to the defs.
+
+   These problems are set up like the other dataflow problems so that
+   they nicely fit into the framework.  They are much simpler and only
+   involve a single traversal of instructions and an examination of
+   the reaching defs information (the dependent problem).
+----------------------------------------------------------------------------*/
+
+struct df_chain_problem_data
+{
+  int flags;
+};
+
+
+/* Create def-use or use-def chains.  */
+
+static void  
+df_chain_alloc (struct dataflow *dflow, 
+		bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
+{
+  struct df *df = dflow->df;
+  unsigned int i;
+  struct df_chain_problem_data *problem_data =
+    (struct df_chain_problem_data *) dflow->problem_data;
+
+  /* Wholesale destruction of the old chains.  */ 
+  if (dflow->block_pool)
+    free_alloc_pool (dflow->block_pool);
+
+  dflow->block_pool = create_alloc_pool ("df_chain_chain_block pool", 
+					 sizeof (struct df_link), 100);
+
+  if (problem_data->flags & DF_DU_CHAIN)
+    {
+      if (!df->def_info.refs_organized)
+	df_reorganize_refs (&df->def_info);
+      
+      /* Clear out the pointers from the refs.  */
+      for (i = 0; i < DF_DEFS_SIZE (df); i++)
+	{
+	  struct df_ref *ref = df->def_info.refs[i];
+	  DF_REF_CHAIN (ref) = NULL;
+	}
+    }
+  
+  if (problem_data->flags & DF_UD_CHAIN)
+    {
+      if (!df->use_info.refs_organized)
+	df_reorganize_refs (&df->use_info);
+      for (i = 0; i < DF_USES_SIZE (df); i++)
+	{
+	  struct df_ref *ref = df->use_info.refs[i];
+	  DF_REF_CHAIN (ref) = NULL;
+	}
+    }
+}
+
+
+/* Create the chains for a list of USEs.  */
+
+static void
+df_chain_create_bb_process_use (struct dataflow *dflow, 
+				struct df_chain_problem_data *problem_data,
+				bitmap local_rd,
+				struct df_ref *use,
+				enum df_ref_flags top_flag)
+{
+  struct df *df = dflow->df;
+  bitmap_iterator bi;
+  unsigned int def_index;
+  
+  while (use)
+    {
+      /* Do not want to go thur this for an uninitialized var.  */
+      unsigned int uregno = DF_REF_REGNO (use);
+      int count = DF_REG_DEF_GET (df, uregno)->n_refs;
+      if (count)
+	{
+	  if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
+	    {
+	      unsigned int first_index = DF_REG_DEF_GET (df, uregno)->begin;
+	      unsigned int last_index = first_index + count - 1;
+	      
+	      EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
+		{
+		  struct df_ref *def;
+		  if (def_index > last_index) 
+		    break;
+		  
+		  def = DF_DEFS_GET (df, def_index);
+		  if (problem_data->flags & DF_DU_CHAIN)
+		    df_chain_create (dflow, def, use);
+		  if (problem_data->flags & DF_UD_CHAIN)
+		    df_chain_create (dflow, use, def);
+		}
+	    }
+	}
+      use = use->next_ref;
+    }
+}
+
+/* Reset the storage pool that the def-use or use-def chains have been
+   allocated in. We do not need to re adjust the pointers in the refs,
+   these have already been clean out.*/
+
+/* Create chains from reaching defs bitmaps for basic block BB.  */
+static void
+df_chain_create_bb (struct dataflow *dflow, 
+		    struct dataflow *rd_dflow,
+		    unsigned int bb_index)
+{
+  basic_block bb = BASIC_BLOCK (bb_index);
+  struct df_rd_bb_info *bb_info = df_rd_get_bb_info (rd_dflow, bb_index);
+  rtx insn;
+  bitmap cpy = BITMAP_ALLOC (NULL);
+  struct df *df = dflow->df;
+  struct df_chain_problem_data *problem_data =
+    (struct df_chain_problem_data *) dflow->problem_data;
+  struct df_ref *def;
+
+  bitmap_copy (cpy, bb_info->in);
+
+  /* Since we are going forwards, process the artificial uses first
+     then the artificial defs second.  */
+
+#ifdef EH_USES
+  /* Create the chains for the artificial uses from the EH_USES at the
+     beginning of the block.  */
+  df_chain_create_bb_process_use (dflow, problem_data, cpy,
+				  df_get_artificial_uses (df, bb->index), 
+				  DF_REF_AT_TOP);
+#endif
+
+  for (def = df_get_artificial_defs (df, bb_index); def; def = def->next_ref)
+    {
+      unsigned int dregno = DF_REF_REGNO (def);
+      bitmap_clear_range (cpy, 
+			  DF_REG_DEF_GET (df, dregno)->begin, 
+			  DF_REG_DEF_GET (df, dregno)->n_refs);
+      if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
+	bitmap_set_bit (cpy, DF_REF_ID (def));
+    }
+  
+  /* Process the regular instructions next.  */
+  FOR_BB_INSNS (bb, insn)
+    {
+      struct df_ref *def;
+      unsigned int uid = INSN_UID (insn);
+
+      if (! INSN_P (insn))
+	continue;
+
+      /* Now scan the uses and link them up with the defs that remain
+	 in the cpy vector.  */
+      
+      df_chain_create_bb_process_use (dflow, problem_data, cpy,		     
+				     DF_INSN_UID_GET (df, uid)->uses, 0);
+
+      /* Since we are going forwards, process the defs second.  This
+         pass only changes the bits in cpy.  */
+      for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+	{
+	  unsigned int dregno = DF_REF_REGNO (def);
+	  bitmap_clear_range (cpy, 
+			      DF_REG_DEF_GET (df, dregno)->begin, 
+			      DF_REG_DEF_GET (df, dregno)->n_refs);
+	  if (! (DF_REF_FLAGS (def) & DF_REF_CLOBBER))
+	    bitmap_set_bit (cpy, DF_REF_ID (def));
+	}
+    }
+
+  /* Create the chains for the artificial uses of the hard registers
+     at the end of the block.  */
+  df_chain_create_bb_process_use (dflow, problem_data, cpy,
+				  df_get_artificial_uses (df, bb->index), 0);
+}
+
+/* Create def-use chains from reaching use bitmaps for basic blocks
+   in BLOCKS.  */
+
+static void
+df_chain_finalize (struct dataflow *dflow, bitmap all_blocks)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  struct df *df = dflow->df;
+  struct dataflow *rd_dflow = df->problems_by_index [DF_RD];
+  
+  EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
+    {
+      df_chain_create_bb (dflow, rd_dflow, bb_index);
+    }
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_chain_free (struct dataflow *dflow)
+{
+  free_alloc_pool (dflow->block_pool);
+  free (dflow->problem_data);
+  free (dflow);
+}
+
+
+/* Debugging info.  */
+
+static void
+df_chains_dump (struct dataflow *dflow, FILE *file)
+{
+  struct df *df = dflow->df;
+  unsigned int j;
+  struct df_chain_problem_data *problem_data =
+    (struct df_chain_problem_data *) dflow->problem_data;
+
+  if (problem_data->flags & DF_DU_CHAIN)
+    {
+      fprintf (file, "Def-use chains:\n");
+      for (j = 0; j < df->def_info.bitmap_size; j++)
+	{
+	  struct df_ref *def = DF_DEFS_GET (df, j);
+	  if (def)
+	    {
+	      fprintf (file, "d%d bb %d luid %d insn %d reg %d ",
+		       j, DF_REF_BBNO (def),
+		       DF_INSN_LUID (df, DF_REF_INSN (def)),
+		       DF_REF_INSN (def) ? DF_REF_INSN_UID (def) : -1,
+		       DF_REF_REGNO (def));
+	      if (def->flags & DF_REF_READ_WRITE)
+		fprintf (file, "read/write ");
+	      df_chain_dump (df, DF_REF_CHAIN (def), file);
+	      fprintf (file, "\n");
+	    }
+	}
+    }
+
+  if (problem_data->flags & DF_UD_CHAIN)
+    {
+      fprintf (file, "Use-def chains:\n");
+      for (j = 0; j < df->use_info.bitmap_size; j++)
+	{
+	  struct df_ref *use = DF_USES_GET (df, j);
+	  if (use)
+	    {
+	      fprintf (file, "u%d bb %d luid %d insn %d reg %d ",
+		       j, DF_REF_BBNO (use),
+		       DF_REF_INSN (use) ? 
+		       DF_INSN_LUID (df, DF_REF_INSN (use))
+		       : -1,
+		       DF_REF_INSN (DF_USES_GET (df, j)) ?
+		       DF_REF_INSN_UID (DF_USES_GET (df,j))
+		       : -1,
+		       DF_REF_REGNO (use));
+	      if (use->flags & DF_REF_READ_WRITE)
+		fprintf (file, "read/write ");
+	      if (use->flags & DF_REF_STRIPPED)
+		fprintf (file, "stripped ");
+	      if (use->flags & DF_REF_IN_NOTE)
+		fprintf (file, "note ");
+	      df_chain_dump (df, DF_REF_CHAIN (use), file);
+	      fprintf (file, "\n");
+	    }
+	}
+    }
+}
+
+
+static struct df_problem problem_CHAIN =
+{
+  DF_CHAIN,                   /* Problem id.  */
+  DF_NONE,                    /* Direction.  */
+  df_chain_alloc,             /* Allocate the problem specific data.  */
+  NULL,                       /* Free basic block info.  */
+  NULL,                       /* Local compute function.  */
+  NULL,                       /* Init the solution specific data.  */
+  NULL,                       /* Iterative solver.  */
+  NULL,                       /* Confluence operator 0.  */ 
+  NULL,                       /* Confluence operator n.  */ 
+  NULL,                       /* Transfer function.  */
+  df_chain_finalize,          /* Finalize function.  */
+  df_chain_free,              /* Free all of the problem information.  */
+  df_chains_dump,             /* Debugging.  */
+  &problem_RD                 /* Dependent problem.  */
+};
+
+
+/* Create a new DATAFLOW instance and add it to an existing instance
+   of DF.  The returned structure is what is used to get at the
+   solution.  */
+
+struct dataflow *
+df_chain_add_problem (struct df *df, int flags)
+{
+  struct df_chain_problem_data *problem_data =
+	xmalloc (sizeof (struct df_chain_problem_data));
+  struct dataflow *dflow = df_add_problem (df, &problem_CHAIN);
+
+  dflow->problem_data = problem_data;
+  problem_data->flags = flags;
+  
+  return dflow;
+}
+
+
+/*----------------------------------------------------------------------------
+   REGISTER INFORMATION
+
+   Currently this consists of only lifetime information.  But the plan is
+   to enhance it so that it produces all of the register information needed
+   by the register allocators.
+----------------------------------------------------------------------------*/
+
+
+struct df_ri_problem_data
+{
+  int *lifetime;
+};
+
+
+/* Allocate the lifetime information.  */
+
+static void 
+df_ri_alloc (struct dataflow *dflow, bitmap blocks_to_rescan ATTRIBUTE_UNUSED)
+{
+  struct df_ri_problem_data *problem_data =
+    (struct df_ri_problem_data *) dflow->problem_data;
+
+  if (!dflow->problem_data)
+    {
+      struct df_ri_problem_data *problem_data =
+	xmalloc (sizeof (struct df_ri_problem_data));
+      dflow->problem_data = problem_data;
+    }
+
+  problem_data->lifetime = xrealloc (problem_data->lifetime, 
+				     max_reg_num () *sizeof (int));
+  memset (problem_data->lifetime, 0, max_reg_num () *sizeof (int));
+}
+
+/* Compute register info: lifetime, bb, and number of defs and uses
+   for basic block BB.  */
+
+static void
+df_ri_bb_compute (struct dataflow *dflow, unsigned int bb_index, bitmap live)
+{
+  struct df *df = dflow->df;
+  struct df_ur_bb_info *bb_info = df_ur_get_bb_info (dflow, bb_index);
+  struct df_ri_problem_data *problem_data =
+    (struct df_ri_problem_data *) dflow->problem_data;
+  basic_block bb = BASIC_BLOCK (bb_index);
+  rtx insn;
+
+  bitmap_copy (live, bb_info->out);
+
+  FOR_BB_INSNS_REVERSE (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+      unsigned int regno;
+      bitmap_iterator bi;
+      struct df_ref *def;
+      struct df_ref *use;
+
+      if (! INSN_P (insn))
+	continue;
+
+      for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+	{
+	  unsigned int dregno = DF_REF_REGNO (def);
+
+	  /* Kill this register.  */
+	  bitmap_clear_bit (live, dregno);
+	}
+
+      for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
+	{
+	  unsigned int uregno = DF_REF_REGNO (use);
+
+	  /* This register is now live.  */
+	  bitmap_set_bit (live, uregno);
+	}
+
+      /* Increment lifetimes of all live registers.  */
+      EXECUTE_IF_SET_IN_BITMAP (live, 0, regno, bi)
+	{
+	  problem_data->lifetime[regno]++;
+	}
+    }
+}
+
+
+/* Compute register info: lifetime, bb, and number of defs and uses.  */
+static void
+df_ri_compute (struct dataflow *dflow, bitmap all_blocks ATTRIBUTE_UNUSED, 
+	       bitmap blocks_to_scan)
+{
+  unsigned int bb_index;
+  bitmap_iterator bi;
+  bitmap live;
+
+  live = BITMAP_ALLOC (NULL);
+
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_scan, 0, bb_index, bi)
+  {
+    df_ri_bb_compute (dflow, bb_index, live);
+  }
+
+  BITMAP_FREE (live);
+}
+
+
+/* Free all storage associated with the problem.  */
+
+static void
+df_ri_free (struct dataflow *dflow)
+{
+  struct df_ri_problem_data *problem_data =
+    (struct df_ri_problem_data *) dflow->problem_data;
+
+  free (problem_data->lifetime);
+  free (dflow->problem_data);
+  free (dflow);
+}
+
+
+/* Debugging info.  */
+
+static void
+df_ri_dump (struct dataflow *dflow, FILE *file)
+{
+  struct df_ri_problem_data *problem_data =
+    (struct df_ri_problem_data *) dflow->problem_data;
+  int j;
+
+  fprintf (file, "Register info:\n");
+  for (j = 0; j < max_reg_num (); j++)
+    {
+      fprintf (file, "reg %d life %d\n", j, problem_data->lifetime[j]);
+    }
+}
+
+/* All of the information associated every instance of the problem.  */
+
+static struct df_problem problem_RI =
+{
+  DF_RI,                      /* Problem id.  */
+  DF_NONE,                    /* Direction.  */
+  df_ri_alloc,                /* Allocate the problem specific data.  */
+  NULL,                       /* Free basic block info.  */
+  df_ri_compute,              /* Local compute function.  */
+  NULL,                       /* Init the solution specific data.  */
+  NULL,                       /* Iterative solver.  */
+  NULL,                       /* Confluence operator 0.  */ 
+  NULL,                       /* Confluence operator n.  */ 
+  NULL,                       /* Transfer function.  */
+  NULL,                       /* Finalize function.  */
+  df_ri_free,                 /* Free all of the problem information.  */
+  df_ri_dump,                 /* Debugging.  */
+  &problem_UR                 /* Dependent problem.  */
+};
+
+
+/* Create a new DATAFLOW instance and add it to an existing instance
+   of DF.  The returned structure is what is used to get at the
+   solution.  */
+
+struct dataflow * 
+df_ri_add_problem (struct df *df)
+{
+  return df_add_problem (df, &problem_RI);
+}
+
+
+/* Return total lifetime (in insns) of REG.  */
+int
+df_reg_lifetime (struct df *df, rtx reg)
+{
+  struct dataflow *dflow = df->problems_by_index[DF_RI];
+  struct df_ri_problem_data *problem_data =
+    (struct df_ri_problem_data *) dflow->problem_data;
+  return problem_data->lifetime[REGNO (reg)];
+}
+
+