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.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@109577 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 440 insertions, 230 deletions

diff --git a/gcc/df.h b/gcc/df.h
index e2ad9774dfb..09a112762bf 100644
--- a/gcc/df.h
+++ b/gcc/df.h
@@ -1,8 +1,11 @@
 /* Form lists of pseudo register references for autoinc optimization
    for GNU compiler.  This is part of flow optimization.
-   Copyright (C) 1999, 2000, 2001, 2003, 2004, 2005
+   Copyright (C) 1999, 2000, 2001, 2003, 2004, 2005, 2006
    Free Software Foundation, Inc.
-   Contributed by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
+   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.
 
@@ -26,32 +29,152 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 
 #include "bitmap.h"
 #include "basic-block.h"
+#include "alloc-pool.h"
+
+struct dataflow;
+struct df;
+struct df_problem;
+
+/* Data flow problems.  All problems must have a unique here.  */ 
+/* Scanning is not really a dataflow problem, but it is useful to have
+   the basic block functions in the vector so that things get done in
+   a uniform manner.  */
+#define DF_SCAN  0 
+#define DF_RU    1      /* Reaching Uses. */
+#define DF_RD    2      /* Reaching Defs. */
+#define DF_LR    3      /* Live Registers. */
+#define DF_UR    4      /* Uninitialized Registers. */
+#define DF_UREC  5      /* Uninitialized Registers with Early Clobber. */
+#define DF_CHAIN 6      /* Def-Use and/or Use-Def Chains. */
+#define DF_RI    7      /* Register Info. */
+#define DF_LAST_PROBLEM_PLUS1 (DF_RI + 1)
+
+/* Flags that control the building of chains.  */
+#define DF_DU_CHAIN   1    /* Build DU chains.  */  
+#define DF_UD_CHAIN   2    /* Build UD chains.  */
 
-#define DF_RD		1	/* Reaching definitions.  */
-#define DF_RU		2	/* Reaching uses.  */
-#define DF_LR		4	/* Live registers.  */
-#define DF_DU_CHAIN	8	/* Def-use chain.  */
-#define DF_UD_CHAIN	16	/* Use-def chain.  */
-#define DF_REG_INFO	32	/* Register info.  */
-#define DF_RD_CHAIN	64	/* Reg-def chain.  */
-#define DF_RU_CHAIN	128	/* Reg-use chain.  */
-#define DF_ALL		255
-#define DF_HARD_REGS	1024	/* Mark hard registers.  */
-#define DF_EQUIV_NOTES	2048	/* Mark uses present in EQUIV/EQUAL notes.  */
-#define DF_SUBREGS	4096	/* Return subregs rather than the inner reg.  */
 
-enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
-		  DF_REF_REG_MEM_STORE};
+/* Dataflow direction.  */
+enum df_flow_dir
+  {
+    DF_NONE,
+    DF_FORWARD,
+    DF_BACKWARD
+  };
 
-#define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
+/* Function prototypes added to df_problem instance.  */
 
-/* Link on a def-use or use-def chain.  */
-struct df_link
+/* Allocate the problem specific data.  */
+typedef void (*df_alloc_function) (struct dataflow *, bitmap);
+
+/* Free the basic block info.  Called from the block reordering code
+   to get rid of the blocks that have been squished down.   */
+typedef void (*df_free_bb_function) (struct dataflow *, void *);
+
+/* Local compute function.  */
+typedef void (*df_local_compute_function) (struct dataflow *, bitmap, bitmap);
+
+/* Init the solution specific data.  */
+typedef void (*df_init_function) (struct dataflow *, bitmap);
+
+/* Iterative dataflow function.  */
+typedef void (*df_dataflow_function) (struct dataflow *, bitmap, bitmap, 
+				   int *, int, bool);
+
+/* Confluence operator for blocks with 0 out (or in) edges.  */
+typedef void (*df_confluence_function_0) (struct dataflow *, basic_block);
+
+/* Confluence operator for blocks with 1 or more out (or in) edges.  */
+typedef void (*df_confluence_function_n) (struct dataflow *, edge);
+
+/* Transfer function for blocks.  */
+typedef bool (*df_transfer_function) (struct dataflow *, int);
+
+/* Function to massage the information after the problem solving.  */
+typedef void (*df_finalizer_function) (struct dataflow*, bitmap);
+
+/* Function to free all of the problem specific datastructures.  */
+typedef void (*df_free_function) (struct dataflow *);
+
+/* Function to dump results to FILE.  */
+typedef void (*df_dump_problem_function) (struct dataflow *, FILE *);
+
+/* The static description of a dataflow problem to solve.  See above
+   typedefs for doc for the function fields.  */
+
+struct df_problem {
+  /* The unique id of the problem.  This is used it index into
+     df->defined_problems to make accessing the problem data easy.  */
+  unsigned int id;                        
+  enum df_flow_dir dir;			/* Dataflow direction.  */
+  df_alloc_function alloc_fun;
+  df_free_bb_function free_bb_fun;
+  df_local_compute_function local_compute_fun;
+  df_init_function init_fun;
+  df_dataflow_function dataflow_fun;
+  df_confluence_function_0 con_fun_0;
+  df_confluence_function_n con_fun_n;
+  df_transfer_function trans_fun;
+  df_finalizer_function finalize_fun;
+  df_free_function free_fun;
+  df_dump_problem_function dump_fun;
+
+  /* A dataflow problem that must be solved before this problem can be
+     solved.  */
+  struct df_problem *dependent_problem;
+};
+
+
+/* The specific instance of the problem to solve.  */
+struct dataflow
 {
-  struct df_link *next;
-  struct ref *ref;
+  struct df *df;                        /* Instance of df we are working in.  */
+  struct df_problem *problem;           /* The problem to be solved.  */
+
+  /* Communication between iterative_dataflow and hybrid_search. */
+  sbitmap visited, pending, considered; 
+
+  /* Array indexed by bb->index, that contains basic block problem and
+     solution specific information.  */
+  void **block_info;
+  unsigned int block_info_size;
+
+  /* The pool to allocate the block_info from. */
+  alloc_pool block_pool;                
+
+  /* Other problem specific data that is not on a per basic block
+     basis.  The structure is generally defined privately for the
+     problem.  The exception being the scanning problem where it is
+     fully public.  */
+  void *problem_data;                  
 };
 
+/* One of these structures is allocated for every insn.  */
+struct df_insn_info
+{
+  struct df_ref *defs;	        /* Head of insn-def chain.  */
+  struct df_ref *uses;	        /* Head of insn-use chain.  */
+  /* ???? The following luid field should be considered private so that
+     we can change it on the fly to accommodate new insns?  */
+  int luid;			/* Logical UID.  */
+  bool contains_asm;            /* Contains an asm instruction.  */
+};
+
+/* Two of these structures are allocated for every pseudo reg, one for
+   the uses and one for the defs.  */
+struct df_reg_info
+{
+  struct df_ref *reg_chain;     /* Head of reg-use or def chain.  */
+  unsigned int begin;           /* First def_index for this pseudo.  */
+  unsigned int n_refs;          /* Number of refs or defs for this pseudo.  */
+};
+
+
+enum df_ref_type {DF_REF_REG_DEF, DF_REF_REG_USE, DF_REF_REG_MEM_LOAD,
+		  DF_REF_REG_MEM_STORE};
+
+#define DF_REF_TYPE_NAMES {"def", "use", "mem load", "mem store"}
+
 enum df_ref_flags
   {
     /* Read-modify-write refs generate both a use and a def and
@@ -62,129 +185,177 @@ enum df_ref_flags
     /* This flag is set, if we stripped the subreg from the reference.
        In this case we must make conservative guesses, at what the
        outer mode was.  */
-    DF_REF_STRIPPED = 2
+    DF_REF_STRIPPED = 2,
+    
+    /* If this flag is set, this is not a real definition/use, but an
+       artificial one created to model always live registers, eh uses, etc.  */
+    DF_REF_ARTIFICIAL = 4,
+
+
+    /* If this flag is set for an artificial use or def, that ref
+       logically happens at the top of the block.  If it is not set
+       for an artificial use or def, that ref logically happens at the
+       bottom of the block.  This is never set for regular refs.  */
+    DF_REF_AT_TOP = 8,
+
+    /* This flag is set if the use is inside a REG_EQUAL note.  */
+    DF_REF_IN_NOTE = 16,
+
+    /* This flag is set if this ref is really a clobber, and not a def.  */
+    DF_REF_CLOBBER = 32
   };
 
 
 /* Define a register reference structure.  One of these is allocated
    for every register reference (use or def).  Note some register
    references (e.g., post_inc, subreg) generate both a def and a use.  */
-struct ref
+struct df_ref
 {
   rtx reg;			/* The register referenced.  */
-  rtx insn;			/* Insn containing ref.  */
+  unsigned int regno;           /* The register number referenced.  */
+  basic_block bb;               /* Basic block containing the instruction. */
+  rtx insn;			/* Insn containing ref.  NB: THIS MAY BE NULL.  */
   rtx *loc;			/* The location of the reg.  */
-  struct df_link *chain;	/* Head of def-use or use-def chain.  */
-  unsigned int id;		/* Ref index.  */
+  struct df_link *chain;	/* Head of def-use, use-def or bi chain.  */
+  unsigned int id;		/* Location in table.  */
   enum df_ref_type type;	/* Type of ref.  */
   enum df_ref_flags flags;	/* Various flags.  */
-  void *data;			/* The data assigned to it by user.  */
-};
 
+  /* For each regno, there are two chains of refs, one for the uses
+     and one for the defs.  These chains go thru the refs themselves
+     rather than using an external structure.  */
+  struct df_ref *next_reg;     /* Next ref with same regno and type.  */
+  struct df_ref *prev_reg;     /* Prev ref with same regno and type.  */
 
-/* One of these structures is allocated for every insn.  */
-struct insn_info
-{
-  struct df_link *defs;		/* Head of insn-def chain.  */
-  struct df_link *uses;		/* Head of insn-use chain.  */
-  /* ???? The following luid field should be considered private so that
-     we can change it on the fly to accommodate new insns?  */
-  int luid;			/* Logical UID.  */
+  /* Each insn has two lists, one for the uses and one for the
+     defs. This is the next field in either of these chains. */
+  struct df_ref *next_ref; 
+  void *data;			/* The data assigned to it by user.  */
 };
 
+/* There are two kinds of links: */
 
-/* One of these structures is allocated for every reg.  */
-struct reg_info
+/* This is used for def-use or use-def chains.  */
+struct df_link
 {
-  struct df_link *defs;		/* Head of reg-def chain.  */
-  struct df_link *uses;		/* Head of reg-use chain.  */
-  int lifetime;
-  int n_defs;
-  int n_uses;
+  struct df_ref *ref;
+  struct df_link *next;
 };
 
-
-/* One of these structures is allocated for every basic block.  */
-struct bb_info
+/* Two of these structures are allocated, one for the uses and one for
+   the defs.  */
+struct df_ref_info
 {
-  /* Reaching def bitmaps have def_id elements.  */
-  bitmap rd_kill;
-  bitmap rd_gen;
-  bitmap rd_in;
-  bitmap rd_out;
-  /* Reaching use bitmaps have use_id elements.  */
-  bitmap ru_kill;
-  bitmap ru_gen;
-  bitmap ru_in;
-  bitmap ru_out;
-  /* Live variable bitmaps have n_regs elements.  */
-  bitmap lr_def;
-  bitmap lr_use;
-  bitmap lr_in;
-  bitmap lr_out;
-  int rd_valid;
-  int ru_valid;
-  int lr_valid;
+  struct df_reg_info **regs;    /* Array indexed by pseudo regno. */
+  unsigned int regs_size;       /* Size of currently allocated regs table.  */
+  unsigned int regs_inited;     /* Number of regs with reg_infos allocated.  */
+  struct df_ref **refs;         /* Ref table, indexed by id.  */
+  unsigned int refs_size;       /* Size of currently allocated refs table.  */
+  unsigned int bitmap_size;	/* Number of refs seen.  */
+
+  /* True if refs table is organized so that every reference for a
+     pseudo is contigious.  */
+  bool refs_organized;
+  /* True if the next refs should be added immediately or false to
+     defer to later to reorganize the table.  */
+  bool add_refs_inline; 
 };
 
+
+/*----------------------------------------------------------------------------
+   Problem data for the scanning dataflow problem.  Unlike the other
+   dataflow problems, the problem data for scanning is fully exposed and
+   used by owners of the problem.
+----------------------------------------------------------------------------*/
 
 struct df
 {
+
+#define DF_HARD_REGS	     1	/* Mark hard registers.  */
+#define DF_EQUIV_NOTES	     2	/* Mark uses present in EQUIV/EQUAL notes.  */
+#define DF_SUBREGS	     4	/* Return subregs rather than the inner reg.  */
+
   int flags;			/* Indicates what's recorded.  */
-  struct bb_info *bbs;		/* Basic block table.  */
-  struct ref **defs;		/* Def table, indexed by def_id.  */
-  struct ref **uses;		/* Use table, indexed by use_id.  */
-  struct ref **reg_def_last;	/* Indexed by regno.  */
-  struct reg_info *regs;	/* Regs table, index by regno.  */
-  unsigned int reg_size;	/* Size of regs table.  */
-  struct insn_info *insns;	/* Insn table, indexed by insn UID.  */
-  unsigned int insn_size;	/* Size of insn table.  */
-  unsigned int def_id;		/* Next def ID.  */
-  unsigned int def_size;	/* Size of def table.  */
-  unsigned int n_defs;		/* Size of def bitmaps.  */
-  unsigned int use_id;		/* Next use ID.  */
-  unsigned int use_size;	/* Size of use table.  */
-  unsigned int n_uses;		/* Size of use bitmaps.  */
-  unsigned int n_bbs;		/* Number of basic blocks.  */
-  unsigned int n_regs;		/* Number of regs.  */
-  unsigned int def_id_save;	/* Saved next def ID.  */
-  unsigned int use_id_save;	/* Saved next use ID.  */
-  bitmap insns_modified;	/* Insns that (may) have changed.  */
-  bitmap bbs_modified;		/* Blocks that (may) have changed.  */
-  bitmap all_blocks;		/* All blocks in CFG.  */
-  int *dfs_order;		/* DFS order -> block number.  */
-  int *rc_order;		/* Reverse completion order -> block number.  */
-  int *rts_order;		/* Reverse top sort order -> block number.  */
+
+  /* The set of problems to be solved is stored in two arrays.  In
+     PROBLEMS_IN_ORDER, the problems are stored in the order that they
+     are solved.  This is an internally dense array that may have
+     nulls at the end of it.  In PROBLEMS_BY_INDEX, the problem is
+     stored by the value in df_problem.id.  These are used to access
+     the problem local data without having to search the first
+     array.  */
+
+  struct dataflow *problems_in_order [DF_LAST_PROBLEM_PLUS1]; 
+  struct dataflow *problems_by_index [DF_LAST_PROBLEM_PLUS1]; 
+  int num_problems_defined;
+
+  /* Set after calls to df_scan_blocks, this contains all of the
+     blocks that higher level problems must rescan before solving the
+     dataflow equations.  If this is NULL, the blocks_to_analyze is
+     used. */
+  bitmap blocks_to_scan;
+
+  /* If not NULL, the subset of blocks of the program to be considered
+     for analysis.  */ 
+  bitmap blocks_to_analyze;
+
+  /* The following information is really the problem data for the
+     scanning instance but it is used too often by the other problems
+     to keep getting it from there.  */
+  struct df_ref_info def_info;   /* Def info.  */
+  struct df_ref_info use_info;   /* Use info.  */
+  struct df_insn_info **insns;   /* Insn table, indexed by insn UID.  */
+  unsigned int insns_size;       /* Size of insn table.  */
+  bitmap hardware_regs_used;     /* The set of hardware registers used.  */
+  bitmap exit_block_uses;        /* The set of hardware registers used in exit block.  */
 };
 
+#define DF_SCAN_BB_INFO(DF, BB) (df_scan_get_bb_info((DF)->problems_by_index[DF_SCAN],(BB)->index))
+#define DF_RU_BB_INFO(DF, BB) (df_ru_get_bb_info((DF)->problems_by_index[DF_RU],(BB)->index))
+#define DF_RD_BB_INFO(DF, BB) (df_rd_get_bb_info((DF)->problems_by_index[DF_RD],(BB)->index))
+#define DF_LR_BB_INFO(DF, BB) (df_lr_get_bb_info((DF)->problems_by_index[DF_LR],(BB)->index))
+#define DF_UR_BB_INFO(DF, BB) (df_ur_get_bb_info((DF)->problems_by_index[DF_UR],(BB)->index))
+#define DF_UREC_BB_INFO(DF, BB) (df_urec_get_bb_info((DF)->problems_by_index[DF_UREC],(BB)->index))
 
-struct df_map
-{
-  rtx old;
-  rtx new;
-};
+/* Most transformations that wish to use live register analysis will
+   use these macros.  The DF_UPWARD_LIVE* macros are only half of the
+   solution.  */
+#define DF_LIVE_IN(DF, BB) (DF_UR_BB_INFO(DF, BB)->in) 
+#define DF_LIVE_OUT(DF, BB) (DF_UR_BB_INFO(DF, BB)->out) 
 
 
-#define DF_BB_INFO(REFS, BB) (&REFS->bbs[(BB)->index])
+/* Live in for register allocation also takes into account several other factors.  */
+#define DF_RA_LIVE_IN(DF, BB) (DF_UREC_BB_INFO(DF, BB)->in) 
+#define DF_RA_LIVE_OUT(DF, BB) (DF_UREC_BB_INFO(DF, BB)->out) 
+
+/* These macros are currently used by only reg-stack since it is not
+   tolerant of uninitialized variables.  This intolerance should be
+   fixed because it causes other problems.  */ 
+#define DF_UPWARD_LIVE_IN(DF, BB) (DF_LR_BB_INFO(DF, BB)->in) 
+#define DF_UPWARD_LIVE_OUT(DF, BB) (DF_LR_BB_INFO(DF, BB)->out) 
 
 
 /* Macros to access the elements within the ref structure.  */
 
+
 #define DF_REF_REAL_REG(REF) (GET_CODE ((REF)->reg) == SUBREG \
 				? SUBREG_REG ((REF)->reg) : ((REF)->reg))
-#define DF_REF_REGNO(REF) REGNO (DF_REF_REAL_REG (REF))
+#define DF_REF_REGNO(REF) ((REF)->regno)
 #define DF_REF_REAL_LOC(REF) (GET_CODE ((REF)->reg) == SUBREG \
 			        ? &SUBREG_REG ((REF)->reg) : ((REF)->loc))
 #define DF_REF_REG(REF) ((REF)->reg)
 #define DF_REF_LOC(REF) ((REF)->loc)
-#define DF_REF_BB(REF) (BLOCK_FOR_INSN ((REF)->insn))
-#define DF_REF_BBNO(REF) (BLOCK_FOR_INSN ((REF)->insn)->index)
+#define DF_REF_BB(REF) ((REF)->bb)
+#define DF_REF_BBNO(REF) (DF_REF_BB (REF)->index)
 #define DF_REF_INSN(REF) ((REF)->insn)
 #define DF_REF_INSN_UID(REF) (INSN_UID ((REF)->insn))
 #define DF_REF_TYPE(REF) ((REF)->type)
 #define DF_REF_CHAIN(REF) ((REF)->chain)
 #define DF_REF_ID(REF) ((REF)->id)
 #define DF_REF_FLAGS(REF) ((REF)->flags)
+#define DF_REF_NEXT_REG(REF) ((REF)->next_reg)
+#define DF_REF_PREV_REG(REF) ((REF)->prev_reg)
+#define DF_REF_NEXT_REF(REF) ((REF)->next_ref)
 #define DF_REF_DATA(REF) ((REF)->data)
 
 /* Macros to determine the reference type.  */
@@ -196,174 +367,213 @@ struct df_map
 #define DF_REF_REG_MEM_P(REF) (DF_REF_REG_MEM_STORE_P (REF) \
                                || DF_REF_REG_MEM_LOAD_P (REF))
 
+/* Macros to get the refs out of def_info or use_info refs table.  */
+#define DF_DEFS_SIZE(DF) ((DF)->def_info.bitmap_size)
+#define DF_DEFS_GET(DF,ID) ((DF)->def_info.refs[(ID)])
+#define DF_DEFS_SET(DF,ID,VAL) ((DF)->def_info.refs[(ID)]=(VAL))
+#define DF_USES_SIZE(DF) ((DF)->use_info.bitmap_size)
+#define DF_USES_GET(DF,ID) ((DF)->use_info.refs[(ID)])
+#define DF_USES_SET(DF,ID,VAL) ((DF)->use_info.refs[(ID)]=(VAL))
+
+/* Macros to access the register information from scan dataflow record.  */
+
+#define DF_REG_SIZE(DF) ((DF)->def_info.regs_size)
+#define DF_REG_DEF_GET(DF, REG) ((DF)->def_info.regs[(REG)])
+#define DF_REG_DEF_SET(DF, REG, VAL) ((DF)->def_info.regs[(REG)]=(VAL))
+#define DF_REG_USE_GET(DF, REG) ((DF)->use_info.regs[(REG)])
+#define DF_REG_USE_SET(DF, REG, VAL) ((DF)->use_info.regs[(REG)]=(VAL))
 
 /* Macros to access the elements within the reg_info structure table.  */
 
 #define DF_REGNO_FIRST_DEF(DF, REGNUM) \
-((DF)->regs[REGNUM].defs ? (DF)->regs[REGNUM].defs->ref : 0)
+(DF_REG_DEF_GET(DF, REGNUM) ? DF_REG_DEF_GET(DF, REGNUM) : 0)
 #define DF_REGNO_LAST_USE(DF, REGNUM) \
-((DF)->regs[REGNUM].uses ? (DF)->regs[REGNUM].uses->ref : 0)
-
-#define DF_REGNO_FIRST_BB(DF, REGNUM) \
-((DF)->regs[REGNUM].defs ? DF_REF_BB ((DF)->regs[REGNUM].defs->ref) : 0)
-#define DF_REGNO_LAST_BB(DF, REGNUM) \
-((DF)->regs[REGNUM].uses ? DF_REF_BB ((DF)->regs[REGNUM].uses->ref) : 0)
-
+(DF_REG_USE_GET(DF, REGNUM) ? DF_REG_USE_GET(DF, REGNUM) : 0)
 
 /* Macros to access the elements within the insn_info structure table.  */
 
-#define DF_INSN_LUID(DF, INSN) ((DF)->insns[INSN_UID (INSN)].luid)
-#define DF_INSN_DEFS(DF, INSN) ((DF)->insns[INSN_UID (INSN)].defs)
-#define DF_INSN_USES(DF, INSN) ((DF)->insns[INSN_UID (INSN)].uses)
-
-
-/* Functions to build and analyze dataflow information.  */
-
-extern struct df *df_init (void);
-
-extern int df_analyze (struct df *, bitmap, int);
-extern void df_analyze_subcfg (struct df *, bitmap, int);
-
-extern void df_finish (struct df *);
-
-extern void df_dump (struct df *, int, FILE *);
-
-
-/* Functions to modify insns.  */
-
-extern bool df_insn_modified_p (struct df *, rtx);
-
-extern void df_insn_modify (struct df *, basic_block, rtx);
-
-extern rtx df_insn_delete (struct df *, basic_block, rtx);
-
-extern rtx df_pattern_emit_before (struct df *, rtx, basic_block, rtx);
-
-extern rtx df_jump_pattern_emit_after (struct df *, rtx, basic_block, rtx);
-
-extern rtx df_pattern_emit_after (struct df *, rtx, basic_block, rtx);
+#define DF_INSN_SIZE(DF) ((DF)->insns_size)
+#define DF_INSN_GET(DF,INSN) ((DF)->insns[(INSN_UID(INSN))])
+#define DF_INSN_SET(DF,INSN,VAL) ((DF)->insns[(INSN_UID (INSN))]=(VAL))
+#define DF_INSN_CONTAINS_ASM(DF, INSN) (DF_INSN_GET(DF,INSN)->contains_asm)
+#define DF_INSN_LUID(DF, INSN) (DF_INSN_GET(DF,INSN)->luid)
+#define DF_INSN_DEFS(DF, INSN) (DF_INSN_GET(DF,INSN)->defs)
+#define DF_INSN_USES(DF, INSN) (DF_INSN_GET(DF,INSN)->uses)
 
-extern rtx df_insn_move_before (struct df *, basic_block, rtx, basic_block,
-				rtx);
+#define DF_INSN_UID_GET(DF,UID) ((DF)->insns[(UID)])
+#define DF_INSN_UID_LUID(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->luid)
+#define DF_INSN_UID_DEFS(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->defs)
+#define DF_INSN_UID_USES(DF, INSN) (DF_INSN_UID_GET(DF,INSN)->uses)
 
-extern int df_reg_replace (struct df *, bitmap, rtx, rtx);
+/* This is a bitmap copy of regs_invalidated_by_call so that we can
+   easily add it into bitmaps, etc. */ 
 
-extern int df_ref_reg_replace (struct df *, struct ref *, rtx, rtx);
+extern bitmap df_invalidated_by_call;
 
-extern int df_ref_remove (struct df *, struct ref *);
+/* Initialize ur_in and ur_out as if all hard registers were partially
+available.  */
 
-extern int df_insn_mem_replace (struct df *, basic_block, rtx, rtx, rtx);
+extern bitmap df_all_hard_regs;
 
-extern struct ref *df_bb_def_use_swap (struct df *, basic_block, rtx, rtx,
-				       unsigned int);
+/* The way that registers are processed, especially hard registers,
+   changes as the compilation proceeds. These states are passed to
+   df_set_state to control this processing.  */
 
+#define DF_SCAN_INITIAL    1    /* Processing from beginning of rtl to
+				   global-alloc.  */
+#define DF_SCAN_GLOBAL     2    /* Processing before global
+				   allocation.  */
+#define DF_SCAN_POST_ALLOC 4    /* Processing after register
+				   allocation.  */
+extern int df_state;            /* Indicates where we are in the compilation.  */
 
-/* Functions to query dataflow information.  */
 
-extern basic_block df_regno_bb (struct df *, unsigned int);
-
-extern int df_reg_lifetime (struct df *, rtx);
-
-extern int df_reg_global_p (struct df *, rtx);
-
-extern int df_insn_regno_def_p (struct df *, basic_block, rtx, unsigned int);
-
-extern int df_insn_dominates_all_uses_p (struct df *, basic_block, rtx);
-
-extern int df_insn_dominates_uses_p (struct df *, basic_block, rtx, bitmap);
+/* One of these structures is allocated for every basic block.  */
+struct df_scan_bb_info
+{
+  /* Defs at the start of a basic block that is the target of an
+     exception edge.  */
+  struct df_ref *artificial_defs;
 
-extern int df_bb_reg_live_start_p (struct df *, basic_block, rtx);
+  /* Uses of hard registers that are live at every block.  */
+  struct df_ref *artificial_uses;
+};
 
-extern int df_bb_reg_live_end_p (struct df *, basic_block, rtx);
 
-extern int df_bb_regs_lives_compare (struct df *, basic_block, rtx, rtx);
+/* Reaching uses.  */
+struct df_ru_bb_info 
+{
+  bitmap kill;
+  bitmap sparse_kill;
+  bitmap gen;
+  bitmap in;
+  bitmap out;
+};
 
-extern bool df_local_def_available_p (struct df *, struct ref *, struct ref *);
 
-extern rtx df_bb_single_def_use_insn_find (struct df *, basic_block, rtx,
-					   rtx);
-extern struct ref *df_bb_regno_last_use_find (struct df *, basic_block, unsigned int);
+/* Reaching definitions.  */
+struct df_rd_bb_info 
+{
+  bitmap kill;
+  bitmap sparse_kill;
+  bitmap gen;
+  bitmap in;
+  bitmap out;
+};
 
-extern struct ref *df_bb_regno_first_def_find (struct df *, basic_block, unsigned int);
 
-extern struct ref *df_bb_regno_last_def_find (struct df *, basic_block, unsigned int);
+/* Live registers.  */
+struct df_lr_bb_info 
+{
+  bitmap def;
+  bitmap use;
+  bitmap in;
+  bitmap out;
+};
 
-extern struct ref *df_find_def (struct df *, rtx, rtx);
 
-extern struct ref *df_find_use (struct df *, rtx, rtx);
+/* Uninitialized registers.  */
+struct df_ur_bb_info 
+{
+  bitmap kill;
+  bitmap gen;
+  bitmap in;
+  bitmap out;
+};
 
-extern int df_reg_used (struct df *, rtx, rtx);
+/* Uninitialized registers.  */
+struct df_urec_bb_info 
+{
+  bitmap earlyclobber;
+  bitmap kill;
+  bitmap gen;
+  bitmap in;
+  bitmap out;
+};
 
-/* Functions for debugging from GDB.  */
 
+#define df_finish(df) {df_finish1(df); df=NULL;}
+
+/* Functions defined in df-core.c.  */
+
+extern struct df *df_init (int);
+extern struct dataflow *df_add_problem (struct df *, struct df_problem *);
+extern void df_set_blocks (struct df*, bitmap);
+extern void df_finish1 (struct df *);
+extern void df_analyze (struct df *);
+extern void df_compact_blocks (struct df *);
+extern void df_bb_replace (struct df *, int, basic_block);
+extern struct df_ref *df_bb_regno_last_use_find (struct df *, basic_block, unsigned int);
+extern struct df_ref *df_bb_regno_first_def_find (struct df *, basic_block, unsigned int);
+extern struct df_ref *df_bb_regno_last_def_find (struct df *, basic_block, unsigned int);
+extern bool df_insn_regno_def_p (struct df *, rtx, unsigned int);
+extern struct df_ref *df_find_def (struct df *, rtx, rtx);
+extern bool df_reg_defined (struct df *, rtx, rtx);
+extern struct df_ref *df_find_use (struct df *, rtx, rtx);
+extern bool df_reg_used (struct df *, rtx, rtx);
+extern void df_iterative_dataflow (struct dataflow *, bitmap, bitmap, int *, int, bool);
+extern void df_dump (struct df *, FILE *);
+extern void df_chain_dump (struct df *, struct df_link *, FILE *);
+extern void df_refs_chain_dump (struct df *, struct df_ref *, bool, FILE *);
+extern void df_regs_chain_dump (struct df *, struct df_ref *,  FILE *);
+extern void df_insn_debug (struct df *, rtx, bool, FILE *);
+extern void df_insn_debug_regno (struct df *, rtx, FILE *);
+extern void df_regno_debug (struct df *, unsigned int, FILE *);
+extern void df_ref_debug (struct df *, struct df_ref *, FILE *);
 extern void debug_df_insn (rtx);
-
 extern void debug_df_regno (unsigned int);
-
 extern void debug_df_reg (rtx);
-
 extern void debug_df_defno (unsigned int);
-
 extern void debug_df_useno (unsigned int);
-
-extern void debug_df_ref (struct ref *);
-
+extern void debug_df_ref (struct df_ref *);
 extern void debug_df_chain (struct df_link *);
+/* An instance of df that can be shared between passes.  */
+extern struct df *shared_df; 
+
+
+/* Functions defined in df-problems.c. */
+
+extern struct dataflow *df_get_dependent_problem (struct dataflow *);
+extern struct df_link *df_chain_create (struct dataflow *, struct df_ref *, struct df_ref *);
+extern void df_chain_unlink (struct dataflow *, struct df_ref *, struct df_link *);
+extern void df_chain_copy (struct dataflow *, struct df_ref *, struct df_link *);
+extern bitmap df_get_live_in (struct df *, basic_block);
+extern bitmap df_get_live_out (struct df *, basic_block);
+extern void df_grow_bb_info (struct dataflow *);
+extern void df_chain_dump (struct df *, struct df_link *, FILE *);
+extern void df_print_bb_index (basic_block bb, FILE *file);
+extern struct dataflow *df_ru_add_problem (struct df *);
+extern struct df_ru_bb_info *df_ru_get_bb_info (struct dataflow *, unsigned int);
+extern struct dataflow *df_rd_add_problem (struct df *);
+extern struct df_rd_bb_info *df_rd_get_bb_info (struct dataflow *, unsigned int);
+extern struct dataflow *df_lr_add_problem (struct df *);
+extern struct df_lr_bb_info *df_lr_get_bb_info (struct dataflow *, unsigned int);
+extern struct dataflow *df_ur_add_problem (struct df *);
+extern struct df_ur_bb_info *df_ur_get_bb_info (struct dataflow *, unsigned int);
+extern struct dataflow *df_urec_add_problem (struct df *);
+extern struct df_urec_bb_info *df_urec_get_bb_info (struct dataflow *, unsigned int);
+extern struct dataflow *df_chain_add_problem (struct df *, int flags);
+extern struct dataflow *df_ri_add_problem (struct df *);
+extern int df_reg_lifetime (struct df *, rtx reg);
+
+
+/* Functions defined in df-scan.c.  */
+
+extern struct df_scan_bb_info *df_scan_get_bb_info (struct dataflow *, unsigned int);
+extern struct dataflow *df_scan_add_problem (struct df *);
+extern void df_rescan_blocks (struct df *, bitmap);
+extern struct df_ref *df_ref_create (struct df *, rtx, rtx *, rtx,basic_block,enum df_ref_type, enum df_ref_flags);
+extern struct df_ref *df_get_artificial_defs (struct df *, unsigned int);
+extern struct df_ref *df_get_artificial_uses (struct df *, unsigned int);
+extern void df_reg_chain_create (struct df_reg_info *, struct df_ref *);
+extern struct df_ref *df_reg_chain_unlink (struct dataflow *, struct df_ref *);
+extern void df_ref_remove (struct df *, struct df_ref *);
+extern void df_insn_refs_delete (struct dataflow *, rtx);
+extern void df_refs_delete (struct dataflow *, bitmap);
+extern void df_reorganize_refs (struct df_ref_info *);
+extern void df_set_state (int);
+extern void df_hard_reg_init (void);
+extern bool df_read_modify_subreg_p (rtx);
 
-extern void df_insn_debug (struct df *, rtx, FILE *);
-
-extern void df_insn_debug_regno (struct df *, rtx, FILE *);
-
-
-/* Meet over any path (UNION) or meet over all paths (INTERSECTION).  */
-enum df_confluence_op
-  {
-    DF_UNION,
-    DF_INTERSECTION
-  };
-
-
-/* Dataflow direction.  */
-enum df_flow_dir
-  {
-    DF_FORWARD,
-    DF_BACKWARD
-  };
-
-
-typedef void (*transfer_function) (int, int *, void *, void *,
-				   void *, void *, void *);
-
-/* The description of a dataflow problem to solve.  */
-
-enum set_representation
-{
-  SR_SBITMAP,		/* Represent sets by bitmaps.  */
-  SR_BITMAP		/* Represent sets by sbitmaps.  */
-};
-
-struct dataflow
-{
-  enum set_representation repr;		/* The way the sets are represented.  */
-
-  /* The following arrays are indexed by block indices, so they must always
-     be large enough even if we restrict ourselves just to a subset of cfg.  */
-  void **gen, **kill;			/* Gen and kill sets.  */
-  void **in, **out;			/* Results.  */
-
-  enum df_flow_dir dir;			/* Dataflow direction.  */
-  enum df_confluence_op conf_op;	/* Confluence operator.  */ 
-  unsigned n_blocks;			/* Number of basic blocks in the
-					   order.  */
-  int *order;				/* The list of basic blocks to work
-					   with, in the order they should
-					   be processed in.  */
-  transfer_function transfun;		/* The transfer function.  */
-  void *data;				/* Data used by the transfer
-					   function.  */
-};
-
-extern void iterative_dataflow (struct dataflow *);
-extern bool read_modify_subreg_p (rtx);
 
 #endif /* GCC_DF_H */