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, 1164 insertions, 0 deletions

diff --git a/gcc/df-core.c b/gcc/df-core.c
new file mode 100644
index 00000000000..aef38cb4354
--- /dev/null
+++ b/gcc/df-core.c
@@ -0,0 +1,1164 @@
+/* Allocation 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.  
+*/
+
+/*
+OVERVIEW:
+
+The files in this collection (df*.c,df.h) provide a general framework
+for solving dataflow problems.  The global dataflow is performed using
+a good implementation of iterative dataflow analysis.
+
+The file df-problems.c provides problem instance for the most common
+dataflow problems: reaching defs, upward exposed uses, live variables,
+uninitialized variables, def-use chains, and use-def chains.  However,
+the interface allows other dataflow problems to be defined as well.
+
+
+USAGE:
+
+Here is an example of using the dataflow routines.
+
+      struct df *df;
+
+      df = df_init (init_flags);
+      
+      df_add_problem (df, problem);
+
+      df_set_blocks (df, blocks);
+
+      df_rescan_blocks (df, blocks);
+
+      df_analyze (df);
+
+      df_dump (df, stderr);
+
+      df_finish (df);
+
+
+
+DF_INIT simply creates a poor man's object (df) that needs to be
+passed to all the dataflow routines.  df_finish destroys this object
+and frees up any allocated memory.
+
+There are two flags that can be passed to df_init:
+
+DF_NO_SCAN means that no scanning of the rtl code is performed.  This
+is used if the problem instance is to do it's own scanning.
+
+DF_HARD_REGS means that the scanning is to build information about
+both pseudo registers and hardware registers.  Without this
+information, the problems will be solved only on pseudo registers.
+
+
+
+DF_ADD_PROBLEM adds a problem, defined by an instance to struct
+df_problem, to the set of problems solved in this instance of df.  All
+calls to add a problem for a given instance of df must occur before
+the first call to DF_RESCAN_BLOCKS or DF_ANALYZE.
+
+For all of the problems defined in df-problems.c, there are
+convienence functions named DF_*_ADD_PROBLEM.
+
+
+Problems can be dependent on other problems.  For instance, solving
+def-use or use-def chains is dependant on solving reaching
+definitions. As long as these dependancies are listed in the problem
+definition, the order of adding the problems is not material.
+Otherwise, the problems will be solved in the order of calls to
+df_add_problem.  Note that it is not necessary to have a problem.  In
+that case, df will just be used to do the scanning.
+
+
+
+DF_SET_BLOCKS is an optional call used to define a region of the
+function on which the analysis will be performed.  The normal case is
+to analyze the entire function and no call to df_set_blocks is made.
+
+When a subset is given, the analysis behaves as if the function only
+contains those blocks and any edges that occur directly between the
+blocks in the set.  Care should be taken to call df_set_blocks right
+before the call to analyze in order to eliminate the possiblity that
+optimizations that reorder blocks invalidate the bitvector.
+
+
+
+DF_RESCAN_BLOCKS is an optional call that causes the scanner to be
+ (re)run over the set of blocks passed in.  If blocks is NULL, the entire
+function (or all of the blocks defined in df_set_blocks) is rescanned.
+If blocks contains blocks that were not defined in the call to
+df_set_blocks, these blocks are added to the set of blocks.
+
+
+DF_ANALYZE causes all of the defined problems to be (re)solved.  It
+does not cause blocks to be (re)scanned at the rtl level unless no
+prior call is made to df_rescan_blocks.
+
+
+DF_DUMP can then be called to dump the information produce to some
+file.
+
+
+
+DF_FINISH causes all of the datastructures to be cleaned up and freed.
+The df_instance is also freed and its pointer should be NULLed.
+
+
+
+
+Scanning produces a `struct df_ref' data structure (ref) is allocated
+for every register reference (def or use) and this records the insn
+and bb the ref is found within.  The refs are linked together in
+chains of uses and defs for each insn and for each register.  Each ref
+also has a chain field that links all the use refs for a def or all
+the def refs for a use.  This is used to create use-def or def-use
+chains.
+
+Different optimizations have different needs.  Ultimately, only
+register allocation and schedulers should be using the bitmaps
+produced for the live register and uninitialized register problems.
+The rest of the backend should be upgraded to using and maintaining
+the linked information such as def use or use def chains.
+
+
+
+PHILOSOPHY:
+
+While incremental bitmaps are not worthwhile to maintain, incremental
+chains may be perfectly reasonable.  The fastest way to build chains
+from scratch or after significant modifications is to build reaching
+definitions (RD) and build the chains from this.
+
+However, general algorithms for maintaining use-def or def-use chains
+are not practical.  The amount of work to recompute the chain any
+chain after an arbitrary change is large.  However, with a modest
+amount of work it is generally possible to have the application that
+uses the chains keep them up to date.  The high level knowledge of
+what is really happening is essential to crafting efficient
+incremental algorithms.
+
+As for the bit vector problems, there is no interface to give a set of
+blocks over with to resolve the iteration.  In general, restarting a
+dataflow iteration is difficult and expensive.  Again, the best way to
+keep the dataflow infomation up to data (if this is really what is
+needed) it to formulate a problem specific solution.
+
+There are fine grained calls for creating and deleting references from
+instructions in df-scan.c.  However, these are not currently connected
+to the engine that resolves the dataflow equations.
+
+
+DATA STRUCTURES:
+
+The basic object is a DF_REF (reference) and this may either be a 
+DEF (definition) or a USE of a register.
+
+These are linked into a variety of lists; namely reg-def, reg-use,
+insn-def, insn-use, def-use, and use-def lists.  For example, the
+reg-def lists contain all the locations that define a given register
+while the insn-use lists contain all the locations that use a
+register.
+
+Note that the reg-def and reg-use chains are generally short for
+pseudos and long for the hard registers.
+
+ACCESSING REFS:
+
+There are 4 ways to obtain access to refs:
+
+1) References are divided into two categories, REAL and ARTIFICIAL.
+
+   REAL refs are associated with instructions.  They are linked into
+   either in the insn's defs list (accessed by the DF_INSN_DEFS or
+   DF_INSN_UID_DEFS macros) or the insn's uses list (accessed by the
+   DF_INSN_USES or DF_INSN_UID_USES macros).  These macros produce a
+   ref (or NULL), the rest of the list can be obtained by traversal of
+   the NEXT_REF field (accessed by the DF_REF_NEXT_REF macro.)  There
+   is no significance to the ordering of the uses or refs in an
+   instruction.
+
+   ARTIFICIAL refs are associated with basic blocks.  The heads of
+   these lists can be accessed by calling get_artificial_defs or
+   get_artificial_uses for the particular basic block.  Artificial
+   defs and uses are only there if DF_HARD_REGS was specified when the
+   df instance was created.
+ 
+   Artificial defs and uses occur at the beginning blocks that are the
+   destination of eh edges.  The defs come from the registers
+   specified in EH_RETURN_DATA_REGNO and the uses come from the
+   registers specified in ED_USES.  Logically these defs and uses
+   should really occur along the eh edge, but there is no convienent
+   way to do this.  Artificial edges that occur at the beginning of
+   the block have the DF_REF_AT_TOP flag set.
+   
+   Artificial uses also occur at the end of all blocks.  These arise
+   from the hard registers that are always live, such as the stack
+   register and are put there to keep the code from forgetting about
+   them.
+
+2) All of the uses and defs associated with each pseudo or hard
+   register are linked in a bidirectional chain.  These are called
+   reg-use or reg_def chains.
+
+   The first use (or def) for a register can be obtained using the
+   DF_REG_USE_GET macro (or DF_REG_DEF_GET macro).  Subsequent uses
+   for the same regno can be obtained by following the next_reg field
+   of the ref.
+
+   In previous versions of this code, these chains were ordered.  It
+   has not been practical to continue this practice.
+
+3) If def-use or use-def chains are built, these can be traversed to
+   get to other refs.
+
+4) An array of all of the uses (and an array of all of the defs) can
+   be built.  These arrays are indexed by the value in the id
+   structure.  These arrays are only lazily kept up to date, and that
+   process can be expensive.  To have these arrays built, call
+   df_reorganize_refs.   Note that the values in the id field of a ref
+   may change across calls to df_analyze or df_reorganize refs.
+
+   If the only use of this array is to find all of the refs, it is
+   better to traverse all of the registers and then traverse all of
+   reg-use or reg-def chains.
+
+
+
+NOTES:
+ 
+Embedded addressing side-effects, such as POST_INC or PRE_INC, generate
+both a use and a def.  These are both marked read/write to show that they
+are dependent. For example, (set (reg 40) (mem (post_inc (reg 42))))
+will generate a use of reg 42 followed by a def of reg 42 (both marked
+read/write).  Similarly, (set (reg 40) (mem (pre_dec (reg 41))))
+generates a use of reg 41 then a def of reg 41 (both marked read/write),
+even though reg 41 is decremented before it is used for the memory
+address in this second example.
+
+A set to a REG inside a ZERO_EXTRACT, or a set to a non-paradoxical SUBREG
+for which the number of word_mode units covered by the outer mode is
+smaller than that covered by the inner mode, invokes a read-modify-write.
+operation.  We generate both a use and a def and again mark them
+read/write.
+
+Paradoxical subreg writes do not leave a trace of the old content, so they
+are write-only operations.  
+*/
+
+
+#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"
+#include "tree-pass.h"
+
+static struct df *ddf = NULL;
+struct df *shared_df = NULL;
+
+/*----------------------------------------------------------------------------
+  Functions to create, destroy and manipulate an instance of df.
+----------------------------------------------------------------------------*/
+
+
+/* Initialize dataflow analysis and allocate and initialize dataflow
+   memory.  */
+
+struct df *
+df_init (int flags)
+{
+  struct df *df = xcalloc (1, sizeof (struct df));
+  df->flags = flags;
+
+  /* This is executed once per compilation to initialize platform
+     specific data structures. */
+  df_hard_reg_init ();
+  
+  /* All df instance must define the scanning problem.  */
+  df_scan_add_problem (df);
+  ddf = df;
+  return df;
+}
+
+/* Add PROBLEM to the DF instance.  */
+
+struct dataflow *
+df_add_problem (struct df *df, struct df_problem *problem)
+{
+  struct dataflow *dflow;
+
+  /* First try to add the dependent problem. */
+  if (problem->dependent_problem)
+    df_add_problem (df, problem->dependent_problem);
+
+  /* Check to see if this problem has already been defined.  If it
+     has, just return that instance, if not, add it to the end of the
+     vector.  */
+  dflow = df->problems_by_index[problem->id];
+  if (dflow)
+    return dflow;
+
+  /* Make a new one and add it to the end.  */
+  dflow = xcalloc (1, sizeof (struct dataflow));
+  dflow->df = df;
+  dflow->problem = problem;
+  df->problems_in_order[df->num_problems_defined++] = dflow;
+  df->problems_by_index[dflow->problem->id] = dflow;
+
+  return dflow;
+}
+
+
+/* Set the blocks that are to be considered for analysis.  If this is
+   not called or is called with null, the entire function in
+   analyzed.  */
+
+void 
+df_set_blocks (struct df *df, bitmap blocks)
+{
+  if (blocks)
+    {
+      if (!df->blocks_to_analyze)
+	df->blocks_to_analyze = BITMAP_ALLOC (NULL);
+      bitmap_copy (df->blocks_to_analyze, blocks);
+    }
+  else
+    {
+      if (df->blocks_to_analyze)
+	{
+	  BITMAP_FREE (df->blocks_to_analyze);
+	  df->blocks_to_analyze = NULL;
+	}
+    }
+}
+
+
+/* Free all the dataflow info and the DF structure.  This should be
+   called from the df_finish macro which also NULLs the parm.  */
+
+void
+df_finish1 (struct df *df)
+{
+  int i;
+
+  for (i = 0; i < df->num_problems_defined; i++)
+    (*df->problems_in_order[i]->problem->free_fun) (df->problems_in_order[i]); 
+
+  free (df);
+}
+
+
+/*----------------------------------------------------------------------------
+   The general data flow analysis engine.
+----------------------------------------------------------------------------*/
+
+
+/* Hybrid search algorithm from "Implementation Techniques for
+   Efficient Data-Flow Analysis of Large Programs".  */
+
+static void
+df_hybrid_search_forward (basic_block bb, 
+			  struct dataflow *dataflow,
+			  bool single_pass)
+{
+  int result_changed;
+  int i = bb->index;
+  edge e;
+  edge_iterator ei;
+
+  SET_BIT (dataflow->visited, bb->index);
+  gcc_assert (TEST_BIT (dataflow->pending, bb->index));
+  RESET_BIT (dataflow->pending, i);
+
+  /*  Calculate <conf_op> of predecessor_outs.  */
+  if (EDGE_COUNT (bb->preds) > 0)
+    FOR_EACH_EDGE (e, ei, bb->preds)
+      {
+	if (!TEST_BIT (dataflow->considered, e->src->index))
+	  continue;
+	
+	(*dataflow->problem->con_fun_n) (dataflow, e);
+      }
+  else if (*dataflow->problem->con_fun_0)
+    (*dataflow->problem->con_fun_0) (dataflow, bb);
+  
+  result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
+  
+  if (!result_changed || single_pass)
+    return;
+  
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      if (e->dest->index == i)
+	continue;
+      if (!TEST_BIT (dataflow->considered, e->dest->index))
+	continue;
+      SET_BIT (dataflow->pending, e->dest->index);
+    }
+  
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    {
+      if (e->dest->index == i)
+	continue;
+      
+      if (!TEST_BIT (dataflow->considered, e->dest->index))
+	continue;
+      if (!TEST_BIT (dataflow->visited, e->dest->index))
+	df_hybrid_search_forward (e->dest, dataflow, single_pass);
+    }
+}
+
+static void
+df_hybrid_search_backward (basic_block bb,
+			   struct dataflow *dataflow,
+			   bool single_pass)
+{
+  int result_changed;
+  int i = bb->index;
+  edge e;
+  edge_iterator ei;
+  
+  SET_BIT (dataflow->visited, bb->index);
+  gcc_assert (TEST_BIT (dataflow->pending, bb->index));
+  RESET_BIT (dataflow->pending, i);
+
+  /*  Calculate <conf_op> of predecessor_outs.  */
+  if (EDGE_COUNT (bb->succs) > 0)
+    FOR_EACH_EDGE (e, ei, bb->succs)					
+      {								
+	if (!TEST_BIT (dataflow->considered, e->dest->index))		
+	  continue;							
+	
+	(*dataflow->problem->con_fun_n) (dataflow, e);
+      }								
+  else if (*dataflow->problem->con_fun_0)
+    (*dataflow->problem->con_fun_0) (dataflow, bb);
+
+  result_changed = (*dataflow->problem->trans_fun) (dataflow, i);
+  
+  if (!result_changed || single_pass)
+    return;
+  
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {								
+      if (e->src->index == i)
+	continue;
+      
+      if (!TEST_BIT (dataflow->considered, e->src->index))
+	continue;
+
+      SET_BIT (dataflow->pending, e->src->index);
+    }								
+  
+  FOR_EACH_EDGE (e, ei, bb->preds)
+    {
+      if (e->src->index == i)
+	continue;
+
+      if (!TEST_BIT (dataflow->considered, e->src->index))
+	continue;
+      
+      if (!TEST_BIT (dataflow->visited, e->src->index))
+	df_hybrid_search_backward (e->src, dataflow, single_pass);
+    }
+}
+
+
+/* This function will perform iterative bitvector dataflow described
+   by DATAFLOW, producing the in and out sets.  Only the part of the
+   cfg induced by blocks in DATAFLOW->order is taken into account.
+
+   SINGLE_PASS is true if you just want to make one pass over the
+   blocks.  */
+
+void
+df_iterative_dataflow (struct dataflow *dataflow,
+		       bitmap blocks_to_consider, bitmap blocks_to_init, 
+		       int *blocks_in_postorder, int n_blocks, 
+		       bool single_pass)
+{
+  unsigned int idx;
+  int i;
+  sbitmap visited = sbitmap_alloc (last_basic_block);
+  sbitmap pending = sbitmap_alloc (last_basic_block);
+  sbitmap considered = sbitmap_alloc (last_basic_block);
+  bitmap_iterator bi;
+
+  dataflow->visited = visited;
+  dataflow->pending = pending;
+  dataflow->considered = considered;
+
+  sbitmap_zero (visited);
+  sbitmap_zero (pending);
+  sbitmap_zero (considered);
+
+  EXECUTE_IF_SET_IN_BITMAP (blocks_to_consider, 0, idx, bi)
+    {
+      SET_BIT (considered, idx);
+    }
+
+  for (i = 0; i < n_blocks; i++)
+    {
+      idx = blocks_in_postorder[i];
+      SET_BIT (pending, idx);
+    };
+
+  (*dataflow->problem->init_fun) (dataflow, blocks_to_init);
+
+  while (1)
+    {
+
+      /* For forward problems, you want to pass in reverse postorder
+         and for backward problems you want postorder.  This has been
+         shown to be as good as you can do by several people, the
+         first being Mathew Hecht in his phd dissertation.
+
+	 The nodes are passed into this function in postorder.  */
+
+      if (dataflow->problem->dir == DF_FORWARD)
+	{
+	  for (i = n_blocks - 1 ; i >= 0 ; i--)
+	    {
+	      idx = blocks_in_postorder[i];
+	      
+	      if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
+		df_hybrid_search_forward (BASIC_BLOCK (idx), dataflow, single_pass);
+	    }
+	}
+      else
+	{
+	  for (i = 0; i < n_blocks; i++)
+	    {
+	      idx = blocks_in_postorder[i];
+	      
+	      if (TEST_BIT (pending, idx) && !TEST_BIT (visited, idx))
+		df_hybrid_search_backward (BASIC_BLOCK (idx), dataflow, single_pass);
+	    }
+	}
+
+      if (sbitmap_first_set_bit (pending) == -1)
+	break;
+
+      sbitmap_zero (visited);
+    }
+
+  sbitmap_free (pending);
+  sbitmap_free (visited);
+  sbitmap_free (considered);
+}
+
+
+/* Remove the entries not in BLOCKS from the LIST of length LEN, preserving
+   the order of the remaining entries.  Returns the length of the resulting
+   list.  */
+
+static unsigned
+df_prune_to_subcfg (int list[], unsigned len, bitmap blocks)
+{
+  unsigned act, last;
+
+  for (act = 0, last = 0; act < len; act++)
+    if (bitmap_bit_p (blocks, list[act]))
+      list[last++] = list[act];
+
+  return last;
+}
+
+
+/* Execute dataflow analysis on a single dataflow problem. 
+
+   There are three sets of blocks passed in: 
+
+   BLOCKS_TO_CONSIDER are the blocks whose solution can either be
+   examined or will be computed.  For calls from DF_ANALYZE, this is
+   the set of blocks that has been passed to DF_SET_BLOCKS.  For calls
+   from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of
+   blocks in the fringe (the set of blocks passed in plus the set of
+   immed preds and succs of those blocks).
+
+   BLOCKS_TO_INIT are the blocks whose solution will be changed by
+   this iteration.  For calls from DF_ANALYZE, this is the set of
+   blocks that has been passed to DF_SET_BLOCKS.  For calls from
+   DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS, this is the set of blocks
+   passed in.
+
+   BLOCKS_TO_SCAN are the set of blocks that need to be rescanned.
+   For calls from DF_ANALYZE, this is the accumulated set of blocks
+   that has been passed to DF_RESCAN_BLOCKS since the last call to
+   DF_ANALYZE.  For calls from DF_ANALYZE_SIMPLE_CHANGE_SOME_BLOCKS,
+   this is the set of blocks passed in.
+ 
+                   blocks_to_consider    blocks_to_init    blocks_to_scan
+   full redo       all                   all               all
+   partial redo    all                   all               sub
+   small fixup     fringe                sub               sub
+*/
+
+static void
+df_analyze_problem (struct dataflow *dflow, 
+		    bitmap blocks_to_consider, 
+		    bitmap blocks_to_init,
+		    bitmap blocks_to_scan,
+		    int *postorder, int n_blocks, bool single_pass)
+{
+  /* (Re)Allocate the datastructures necessary to solve the problem.  */ 
+  if (*dflow->problem->alloc_fun)
+    (*dflow->problem->alloc_fun) (dflow, blocks_to_scan);
+
+  /* Set up the problem and compute the local information.  This
+     function is passed both the blocks_to_consider and the
+     blocks_to_scan because the RD and RU problems require the entire
+     function to be rescanned if they are going to be updated.  */
+  if (*dflow->problem->local_compute_fun)
+    (*dflow->problem->local_compute_fun) (dflow, blocks_to_consider, blocks_to_scan);
+
+  /* Solve the equations.  */
+  if (*dflow->problem->dataflow_fun)
+    (*dflow->problem->dataflow_fun) (dflow, blocks_to_consider, blocks_to_init,
+				    postorder, n_blocks, single_pass);
+
+  /* Massage the solution.  */
+  if (*dflow->problem->finalize_fun)
+    (*dflow->problem->finalize_fun) (dflow, blocks_to_consider);
+}
+
+
+/* Analyze dataflow info for the basic blocks specified by the bitmap
+   BLOCKS, or for the whole CFG if BLOCKS is zero.  */
+
+void
+df_analyze (struct df *df)
+{
+  int *postorder = xmalloc (sizeof (int) *last_basic_block);
+  bitmap current_all_blocks = BITMAP_ALLOC (NULL);
+  int n_blocks;
+  int i;
+  bool everything;
+
+  n_blocks = post_order_compute (postorder, true);
+
+  if (n_blocks != n_basic_blocks)
+    delete_unreachable_blocks ();
+
+  for (i = 0; i < n_blocks; i++)
+    bitmap_set_bit (current_all_blocks, postorder[i]);
+
+  /* No one called df_rescan_blocks, so do it.  */
+  if (!df->blocks_to_scan)
+    df_rescan_blocks (df, NULL);
+
+  /* Make sure that we have pruned any unreachable blocks from these
+     sets.  */
+  bitmap_and_into (df->blocks_to_scan, current_all_blocks);
+
+  if (df->blocks_to_analyze)
+    {
+      everything = false;
+      bitmap_and_into (df->blocks_to_analyze, current_all_blocks);
+      n_blocks = df_prune_to_subcfg (postorder, n_blocks, df->blocks_to_analyze);
+      BITMAP_FREE (current_all_blocks);
+    }
+  else
+    {
+      everything = true;
+      df->blocks_to_analyze = current_all_blocks;
+      current_all_blocks = NULL;
+    }
+
+  /* Skip over the DF_SCAN problem. */
+  for (i = 1; i < df->num_problems_defined; i++)
+    df_analyze_problem (df->problems_in_order[i], 
+			df->blocks_to_analyze, df->blocks_to_analyze, 
+			df->blocks_to_scan,
+			postorder, n_blocks, false);
+
+  if (everything)
+    {
+      BITMAP_FREE (df->blocks_to_analyze);
+      df->blocks_to_analyze = NULL;
+    }
+
+  BITMAP_FREE (df->blocks_to_scan);
+  df->blocks_to_scan = NULL;
+}
+
+
+
+/*----------------------------------------------------------------------------
+   Functions to support limited incremental change.
+----------------------------------------------------------------------------*/
+
+
+/* Get basic block info.  */
+
+static void *
+df_get_bb_info (struct dataflow *dflow, unsigned int index)
+{
+  return (struct df_scan_bb_info *) dflow->block_info[index];
+}
+
+
+/* Set basic block info.  */
+
+static void
+df_set_bb_info (struct dataflow *dflow, unsigned int index, 
+		void *bb_info)
+{
+  dflow->block_info[index] = bb_info;
+}
+
+
+/* Called from the rtl_compact_blocks to reorganize the problems basic
+   block info.  */
+
+void 
+df_compact_blocks (struct df *df)
+{
+  int i, p;
+  basic_block bb;
+  void **problem_temps;
+  int size = last_basic_block *sizeof (void *);
+  problem_temps = xmalloc (size);
+
+  for (p = 0; p < df->num_problems_defined; p++)
+    {
+      struct dataflow *dflow = df->problems_in_order[p];
+      if (*dflow->problem->free_bb_fun)
+	{
+	  df_grow_bb_info (dflow);
+	  memcpy (problem_temps, dflow->block_info, size);
+
+	  /* Copy the bb info from the problem tmps to the proper
+	     place in the block_info vector.  Null out the copied
+	     item.  */
+	  i = NUM_FIXED_BLOCKS;
+	  FOR_EACH_BB (bb) 
+	    {
+	      df_set_bb_info (dflow, i, problem_temps[bb->index]);
+	      problem_temps[bb->index] = NULL;
+	      i++;
+	    }
+	  memset (dflow->block_info + i, 0, 
+		  (last_basic_block - i) *sizeof (void *));
+
+	  /* Free any block infos that were not copied (and NULLed).
+	     These are from orphaned blocks.  */
+	  for (i = NUM_FIXED_BLOCKS; i < last_basic_block; i++)
+	    {
+	      if (problem_temps[i])
+		(*dflow->problem->free_bb_fun) (dflow, problem_temps[i]);
+	    }
+	}
+    }
+
+  free (problem_temps);
+
+  i = NUM_FIXED_BLOCKS;
+  FOR_EACH_BB (bb) 
+    {
+      BASIC_BLOCK (i) = bb;
+      bb->index = i;
+      i++;
+    }
+
+  gcc_assert (i == n_basic_blocks);
+
+  for (; i < last_basic_block; i++)
+    BASIC_BLOCK (i) = NULL;
+}
+
+
+/* Shove NEW_BLOCK in at OLD_INDEX.  Called from if-cvt to hack a
+   block.  There is no excuse for people to do this kind of thing.  */
+
+void 
+df_bb_replace (struct df *df, int old_index, basic_block new_block)
+{
+  int p;
+
+  for (p = 0; p < df->num_problems_defined; p++)
+    {
+      struct dataflow *dflow = df->problems_in_order[p];
+      if (dflow->block_info)
+	{
+	  void *temp;
+
+	  df_grow_bb_info (dflow);
+
+	  /* The old switcheroo.  */
+
+	  temp = df_get_bb_info (dflow, old_index);
+	  df_set_bb_info (dflow, old_index, 
+			  df_get_bb_info (dflow, new_block->index));
+	  df_set_bb_info (dflow, new_block->index, temp);
+	}
+    }
+
+  BASIC_BLOCK (old_index) = new_block;
+  new_block->index = old_index;
+}
+
+/*----------------------------------------------------------------------------
+   PUBLIC INTERFACES TO QUERY INFORMATION.
+----------------------------------------------------------------------------*/
+
+
+/* Return last use of REGNO within BB.  */
+
+struct df_ref *
+df_bb_regno_last_use_find (struct df *df, basic_block bb, unsigned int regno)
+{
+  rtx insn;
+  struct df_ref *use;
+
+  FOR_BB_INSNS_REVERSE (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+      for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
+	if (DF_REF_REGNO (use) == regno)
+	  return use;
+    }
+  return NULL;
+}
+
+
+/* Return first def of REGNO within BB.  */
+
+struct df_ref *
+df_bb_regno_first_def_find (struct df *df, basic_block bb, unsigned int regno)
+{
+  rtx insn;
+  struct df_ref *def;
+
+  FOR_BB_INSNS (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+      for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+	if (DF_REF_REGNO (def) == regno)
+	  return def;
+    }
+  return NULL;
+}
+
+
+/* Return last def of REGNO within BB.  */
+
+struct df_ref *
+df_bb_regno_last_def_find (struct df *df, basic_block bb, unsigned int regno)
+{
+  rtx insn;
+  struct df_ref *def;
+
+  FOR_BB_INSNS_REVERSE (bb, insn)
+    {
+      unsigned int uid = INSN_UID (insn);
+
+      for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+	if (DF_REF_REGNO (def) == regno)
+	  return def;
+    }
+
+  return NULL;
+}
+
+/* Return true if INSN defines REGNO.  */
+
+bool
+df_insn_regno_def_p (struct df *df, rtx insn, unsigned int regno)
+{
+  unsigned int uid;
+  struct df_ref *def;
+
+  uid = INSN_UID (insn);
+  for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+    if (DF_REF_REGNO (def) == regno)
+      return true;
+  
+  return false;
+}
+
+
+/* Finds the reference corresponding to the definition of REG in INSN.
+   DF is the dataflow object.  */
+
+struct df_ref *
+df_find_def (struct df *df, rtx insn, rtx reg)
+{
+  unsigned int uid;
+  struct df_ref *def;
+
+  if (GET_CODE (reg) == SUBREG)
+    reg = SUBREG_REG (reg);
+  gcc_assert (REG_P (reg));
+
+  uid = INSN_UID (insn);
+  for (def = DF_INSN_UID_GET (df, uid)->defs; def; def = def->next_ref)
+    if (rtx_equal_p (DF_REF_REAL_REG (def), reg))
+      return def;
+
+  return NULL;
+}
+
+
+/* Return true if REG is defined in INSN, zero otherwise.  */ 
+
+bool
+df_reg_defined (struct df *df, rtx insn, rtx reg)
+{
+  return df_find_def (df, insn, reg) != NULL;
+}
+  
+
+/* Finds the reference corresponding to the use of REG in INSN.
+   DF is the dataflow object.  */
+  
+struct df_ref *
+df_find_use (struct df *df, rtx insn, rtx reg)
+{
+  unsigned int uid;
+  struct df_ref *use;
+
+  if (GET_CODE (reg) == SUBREG)
+    reg = SUBREG_REG (reg);
+  gcc_assert (REG_P (reg));
+
+  uid = INSN_UID (insn);
+  for (use = DF_INSN_UID_GET (df, uid)->uses; use; use = use->next_ref)
+    if (rtx_equal_p (DF_REF_REAL_REG (use), reg))
+      return use; 
+
+  return NULL;
+}
+
+
+/* Return true if REG is referenced in INSN, zero otherwise.  */ 
+
+bool
+df_reg_used (struct df *df, rtx insn, rtx reg)
+{
+  return df_find_use (df, insn, reg) != NULL;
+}
+  
+
+/*----------------------------------------------------------------------------
+   Debugging and printing functions.
+----------------------------------------------------------------------------*/
+
+/* Dump dataflow info.  */
+void
+df_dump (struct df *df, FILE *file)
+{
+  int i;
+
+  if (! df || ! file)
+    return;
+
+  fprintf (file, "\n\n%s\n", current_function_name ());
+  fprintf (file, "\nDataflow summary:\n");
+  fprintf (file, "def_info->bitmap_size = %d, use_info->bitmap_size = %d\n",
+	   df->def_info.bitmap_size, df->use_info.bitmap_size);
+
+  for (i = 0; i < df->num_problems_defined; i++)
+    (*df->problems_in_order[i]->problem->dump_fun) (df->problems_in_order[i], file); 
+
+  fprintf (file, "\n");
+}
+
+
+void
+df_refs_chain_dump (struct df *df, struct df_ref *ref, 
+		   bool follow_chain, FILE *file)
+{
+  fprintf (file, "{ ");
+  while (ref)
+    {
+      fprintf (file, "%c%d(%d) ",
+	       DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
+	       DF_REF_ID (ref),
+	       DF_REF_REGNO (ref));
+      if (follow_chain)
+	df_chain_dump (df, DF_REF_CHAIN (ref), file);
+      ref = ref->next_ref;
+    }
+  fprintf (file, "}");
+}
+
+
+/* Dump either a ref-def or reg-use chain.  */
+
+void
+df_regs_chain_dump (struct df *df ATTRIBUTE_UNUSED, struct df_ref *ref,  FILE *file)
+{
+  fprintf (file, "{ ");
+  while (ref)
+    {
+      fprintf (file, "%c%d(%d) ",
+	       DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
+	       DF_REF_ID (ref),
+	       DF_REF_REGNO (ref));
+      ref = ref->next_reg;
+    }
+  fprintf (file, "}");
+}
+
+
+void
+df_insn_debug (struct df *df, rtx insn, bool follow_chain, FILE *file)
+{
+  unsigned int uid;
+  int bbi;
+
+  uid = INSN_UID (insn);
+
+  if (DF_INSN_UID_DEFS (df, uid))
+    bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
+  else if (DF_INSN_UID_USES(df, uid))
+    bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
+  else
+    bbi = -1;
+
+  fprintf (file, "insn %d bb %d luid %d defs ",
+	   uid, bbi, DF_INSN_LUID (df, insn));
+
+  df_refs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), follow_chain, file);
+  fprintf (file, " defs ");
+  df_refs_chain_dump (df, DF_INSN_UID_USES (df, uid), follow_chain, file);
+  fprintf (file, "\n");
+}
+
+void
+df_insn_debug_regno (struct df *df, rtx insn, FILE *file)
+{
+  unsigned int uid;
+  int bbi;
+
+  uid = INSN_UID (insn);
+  if (DF_INSN_UID_DEFS (df, uid))
+    bbi = DF_REF_BBNO (DF_INSN_UID_DEFS (df, uid));
+  else if (DF_INSN_UID_USES(df, uid))
+    bbi = DF_REF_BBNO (DF_INSN_UID_USES (df, uid));
+  else
+    bbi = -1;
+
+  fprintf (file, "insn %d bb %d luid %d defs ",
+	   uid, bbi, DF_INSN_LUID (df, insn));
+  df_regs_chain_dump (df, DF_INSN_UID_DEFS (df, uid), file);
+    
+  fprintf (file, " uses ");
+  df_regs_chain_dump (df, DF_INSN_UID_USES (df, uid), file);
+  fprintf (file, "\n");
+}
+
+void
+df_regno_debug (struct df *df, unsigned int regno, FILE *file)
+{
+  fprintf (file, "reg %d defs ", regno);
+  df_regs_chain_dump (df, DF_REG_DEF_GET (df, regno)->reg_chain, file);
+  fprintf (file, " uses ");
+  df_regs_chain_dump (df, DF_REG_USE_GET (df, regno)->reg_chain, file);
+  fprintf (file, "\n");
+}
+
+
+void
+df_ref_debug (struct df *df, struct df_ref *ref, FILE *file)
+{
+  fprintf (file, "%c%d ",
+	   DF_REF_REG_DEF_P (ref) ? 'd' : 'u',
+	   DF_REF_ID (ref));
+  fprintf (file, "reg %d bb %d luid %d insn %d chain ",
+	   DF_REF_REGNO (ref),
+	   DF_REF_BBNO (ref),
+	   DF_REF_INSN (ref) ? DF_INSN_LUID (df, DF_REF_INSN (ref)) : -1,
+	   DF_REF_INSN (ref) ? INSN_UID (DF_REF_INSN (ref)) : -1);
+  df_chain_dump (df, DF_REF_CHAIN (ref), file);
+  fprintf (file, "\n");
+}
+
+/* Functions for debugging from GDB.  */
+
+void
+debug_df_insn (rtx insn)
+{
+  df_insn_debug (ddf, insn, true, stderr);
+  debug_rtx (insn);
+}
+
+
+void
+debug_df_reg (rtx reg)
+{
+  df_regno_debug (ddf, REGNO (reg), stderr);
+}
+
+
+void
+debug_df_regno (unsigned int regno)
+{
+  df_regno_debug (ddf, regno, stderr);
+}
+
+
+void
+debug_df_ref (struct df_ref *ref)
+{
+  df_ref_debug (ddf, ref, stderr);
+}
+
+
+void
+debug_df_defno (unsigned int defno)
+{
+  df_ref_debug (ddf, DF_DEFS_GET (ddf, defno), stderr);
+}
+
+
+void
+debug_df_useno (unsigned int defno)
+{
+  df_ref_debug (ddf, DF_USES_GET (ddf, defno), stderr);
+}
+
+
+void
+debug_df_chain (struct df_link *link)
+{
+  df_chain_dump (ddf, link, stderr);
+  fputc ('\n', stderr);
+}