This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[dataflow] PATCH COMMITTED: first cut at making scanning incremental.


This is the first in a series of patch that makes the low level rtl
addition, deletion, modification and moving functions call back into the
df so that the scanning is up to date.  This is certainly not
everything, but it is everything that I could find by just looking
around.  The next patch, by Seongbae, will add verification that can be
added to the end of every pass to make sure that the dataflow scanning
info at the end of the pass has been properly updated by the changes
that pass makes.  Then the fun will begin.

There were also passes such as dce, recog, and ifcvt that were updating
the scanning as they were going along.  These explicit calls have been
removed since the rtl and basic block modification routines they call
now do the scanning updating. 

Along the way some other things had to be changed.  Many of the df
scanning functions have lost their df or dflow parameters.  This keeps
from having to thread an instance of df thru all of the rtl routines. 
Others will loose theirs soon.

There is no more df_ref.data field.  This was only used by loop-iv.c and
loop-invariant.c.   It was just too hard to figure out what to do with
this field when the ref was deleted because the insn was deleted.  The
data in these fields have been moved to private arrays in these passes. 
This saves a fair amount of space since there are many instances of
df_ref and only these two passes used the field.

This has been bootstapped and regression tested on x86-64-linux and does
not add any new regressions.  It will be more extensively tested after
Seongbae's merge. 

This pass also has the first steps to being able to add and delete
dataflow problems from the df instance.  The idea is that there will be
one persistent instance of df with the lr, ur, and live problems always
computed. The other problems would be added and or deleted from the df
instance as necessary.

Kenny

2006-11-07  Kenneth Zadeck <zadeck@naturalbridge.com>
    * cfg.c (compact_blocks): Make df aware when blocks are moved around.
    * auto-inc-dec.c (attempt_change): Removed explicit df updating.
    * ifcvt.c (cond_exec_process_if_block,
    noce_mem_write_may_trap_or_fault_p, noce_process_if_block,
    cond_move_process_if_block, process_if_block, find_if_header):
    Removed unused df parameter.
    (merge_if_block, find_cond_trap, find_if_case_1, find_if_case_2):
    Removed explicit df updating.
    (if_convert): Rearranged calls to df.
    (struct tree_opt_pass pass_rtl_ifcvt, pass_if_after_combine,
    pass_if_after_reload): Added TODO_verify_flow.
    * recog.c (delete_insn_chain_and_flow): Deleted function.
    (peephole2_optimize): Removed unused dataflow problem and variable
    and delete explicit df updating calls.
    (pass_split_before_sched2): Added TODO_verify_flow.
    * emit_rtl (add_insn_after, add_insn_before, remove_insn,
    reorder_insns, emit_insn_after_1): Added explicit updating of df.
    (set_insn_deleted): New function.
    * loop_invariant.c (invariant_table_size, invariant_table): New
    variables.
    (check_invariant_table_size): New function.
    (invariant_for_use, find_defs, check_dependency,
    find_invariant_insn, free_inv_motion_data, move_loop_invariants):
    Replaced DF_REF_DATA with invariant_table.
    * loop-iv.c (clean_slate, iv_ref_table_size, iv_ref_table): New
    variables.
    (check_iv_ref_table_size): New function.
    (clear_iv_info, iv_analysis_loop_init, record_iv, iv_analyze_def,
    iv_analysis_done): Replaced DF_REF_DATA with iv_ref_table.
    * cfglayout.c (fixup_reorder_chain): Now uses compact_blocks.
    * rtl.h (SET_INSN_DELETED): now calls set_insn_deleted.
    * Makefile.in: (emit-rtl.o): Now dependent on df.h.
    * sched-rgn.c (pass_sched, pass_sched2): Added TODO_verify_flow.
    * cfgrtl.c (rtl_delete_block, update_bb_for_insn,
    rtl_merge_blocks, try_redirect_by_replacing_jump,
    cfg_layout_merge_blocks): Added explicit updating of df.
    * dce.c (delete_unmarked_insns): Removed df_delete parameter and
    explicit updating of df info.
    (rest_of_handle_dce, rest_of_handle_dse): Added call to
    df_remove_problem.
    (fast_dce, fast_dce, rest_of_handle_fast_dce, run_fast_df_dce):
    Removed df_delete parameter.
    * df-scan.c (df_scan_free_bb_info): Changed call.
    (df_scan_alloc, df_scan_free): Added setting of
out_of_date_transfer_functions.
    (df_problem problem_SCAN): Added problem removal function.
    (df_scan_blocks): Added calls to df_refs_delete and df_bb_delete.
    (df_insn_create_insn_record): Added call to df_grow_insn_info.
    (df_insn_refs_delete): Renamed to df_insn_delete and removed dflow
    parameter.
    (df_bb_refs_delete): Renamed to df_bb_delete and removed dflow
    parameter.
    (df_refs_delete): Deleted.
    (df_insn_rescan, df_insn_change_bb): New function.
    (df_ref_create_structure): Removed DF_REF_DATA.
    * df-core.c (df_add_problem): Changed to use new form of problem
    dependency.
    (df_remove_problem): New function.
    (df_set_blocks): Does a better job of updating the proper blocks.
    (df_delete_basic_block): Removed df parameter and checks to see if
    block already had infomation.
    (df_get_bb_info): Returns NULL if no info was there.
    (df_set_bb_info): Checks to make sure problem block information.
    (df_mark_solutions_dirty, df_mark_bb_dirty, df_compact_blocks,
    df_bb_replace): New functions.
    * df.h (df_remove_problem_function): New typedef.
    (df_dependent_problem_function): Deleted typedef.
    (df_problem): Added remove_problem_fun and dependent_problem and
    deleted dependent_problem_fun.
    (df_ref.data): Removed.
    (df.out_of_date_transfer_functions, df.solutions_dirty): New
    variables.
    (DF_REF_DATA): Deleted macro. 
    * df-problems.c (problem_RU, problem_RD, problem_LR, problem_UR,
    problem_LIVE, problem_UREC, problem_CHAIN, problem_RI): Added
    problem removal function and changed dependent_function.
Index: cfg.c
===================================================================
--- cfg.c	(revision 118540)
+++ cfg.c	(working copy)
@@ -163,23 +163,28 @@ void
 compact_blocks (void)
 {
   int i;
-  basic_block bb;
 
   SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
   
-  i = NUM_FIXED_BLOCKS;
-  FOR_EACH_BB (bb)
+  if (df_current_instance)
+    df_compact_blocks ();
+  else 
     {
-      SET_BASIC_BLOCK (i, bb);
-      bb->index = i;
-      i++;
-    }
-  gcc_assert (i == n_basic_blocks);
-  
-  for (; i < last_basic_block; i++)
-    SET_BASIC_BLOCK (i, NULL);
+      basic_block bb;
+      
+      i = NUM_FIXED_BLOCKS;
+      FOR_EACH_BB (bb)
+	{
+	  SET_BASIC_BLOCK (i, bb);
+	  bb->index = i;
+	  i++;
+	}
+      gcc_assert (i == n_basic_blocks);
 
+      for (; i < last_basic_block; i++)
+	SET_BASIC_BLOCK (i, NULL);
+    }
   last_basic_block = n_basic_blocks;
 }
 
@@ -1192,3 +1197,4 @@ get_bb_copy (basic_block bb)
   else
     return NULL;
 }
+
Index: auto-inc-dec.c
===================================================================
--- auto-inc-dec.c	(revision 118540)
+++ auto-inc-dec.c	(working copy)
@@ -622,13 +622,9 @@ attempt_change (rtx new_addr_pat, rtx in
     }
 
   /* Recompute the df info for the insns that have changed. */
-  df_insn_refs_delete (scan_dflow, inc_insn.insn);
-  df_insn_create_insn_record (scan_dflow, inc_insn.insn);
+  delete_insn (inc_insn.insn);
 
-  SET_INSN_DELETED (inc_insn.insn);
-  df_insn_refs_delete (scan_dflow, mem_insn.insn);
-  df_insn_create_insn_record (scan_dflow, mem_insn.insn);
-  df_insn_refs_record (scan_dflow, bb, mem_insn.insn); 
+  df_insn_rescan (mem_insn.insn);
   if (mov_insn)
     {
       if (dump_file)
@@ -636,8 +632,7 @@ attempt_change (rtx new_addr_pat, rtx in
 	  fprintf (dump_file, "inserting mov ");
 	  dump_insn_slim (dump_file, mov_insn);
 	}
-      df_insn_create_insn_record (scan_dflow, mov_insn);
-      df_insn_refs_record (scan_dflow, bb, mov_insn); 
+      df_insn_rescan (scan_dflow, mov_insn);
     }
   df_recompute_luids (df, bb);
 
Index: haifa-sched.c
===================================================================
--- haifa-sched.c	(revision 118540)
+++ haifa-sched.c	(working copy)
@@ -2523,7 +2523,7 @@ schedule_block (basic_block *target_bb, 
             generate_recovery_code (insn);
 
 	  if (control_flow_insn_p (last_scheduled_insn)	     
-	      /* This is used to to switch basic blocks by request
+	      /* This is used to switch basic blocks by request
 		 from scheduler front-end (actually, sched-ebb.c only).
 		 This is used to process blocks with single fallthru
 		 edge.  If succeeding block has jump, it [jump] will try
Index: ifcvt.c
===================================================================
--- ifcvt.c	(revision 118540)
+++ ifcvt.c	(working copy)
@@ -92,16 +92,16 @@ static rtx last_active_insn (basic_block
 static basic_block block_fallthru (basic_block);
 static int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int);
 static rtx cond_exec_get_condition (rtx);
-static int cond_exec_process_if_block (struct df *, bitmap, ce_if_block_t *, int);
+static int cond_exec_process_if_block (bitmap, ce_if_block_t *, int);
 static rtx noce_get_condition (rtx, rtx *);
 static int noce_operand_ok (rtx);
-static int noce_process_if_block (struct df *, bitmap, ce_if_block_t *);
-static int process_if_block (struct df *, bitmap, ce_if_block_t *);
-static void merge_if_block (struct df *, bitmap, ce_if_block_t *);
-static int find_cond_trap (struct df *, bitmap, basic_block, edge, edge);
+static int noce_process_if_block (bitmap, ce_if_block_t *);
+static int process_if_block (bitmap, ce_if_block_t *);
+static void merge_if_block (bitmap, ce_if_block_t *);
+static int find_cond_trap (bitmap, basic_block, edge, edge);
 static basic_block find_if_header (struct df *, bitmap, basic_block, int);
 static int block_jumps_and_fallthru_p (basic_block, basic_block);
-static int find_if_block (struct df *, bitmap, ce_if_block_t *);
+static int find_if_block (bitmap, ce_if_block_t *);
 static int find_if_case_1 (struct df *, bitmap, basic_block, edge, edge);
 static int find_if_case_2 (struct df *, bitmap, basic_block, edge, edge);
 static int find_memory (rtx *, void *);
@@ -369,7 +369,7 @@ cond_exec_get_condition (rtx jump)
    converting the block.  */
 
 static int
-cond_exec_process_if_block (struct df *df, bitmap modified, 
+cond_exec_process_if_block (bitmap modified, 
 			    ce_if_block_t * ce_info,
 			    /* if block information */int do_multiple_p)
 {
@@ -573,7 +573,7 @@ cond_exec_process_if_block (struct df *d
 	     n_insns, (n_insns == 1) ? " was" : "s were");
 
   /* Merge the blocks!  */
-  merge_if_block (df, modified, ce_info);
+  merge_if_block (modified, ce_info);
   cond_exec_changed_p = TRUE;
   return TRUE;
 
@@ -2166,7 +2166,7 @@ noce_mem_write_may_trap_or_fault_p (rtx 
    successful at converting the block.  */
 
 static int
-noce_process_if_block (struct df *df, bitmap modified, struct ce_if_block * ce_info)
+noce_process_if_block (bitmap modified, struct ce_if_block * ce_info)
 {
   basic_block test_bb = ce_info->test_bb;	/* test block */
   basic_block then_bb = ce_info->then_bb;	/* THEN */
@@ -2393,7 +2393,7 @@ noce_process_if_block (struct df *df, bi
     }
 
   /* Merge the blocks!  */
-  merge_if_block (df, modified, ce_info);
+  merge_if_block (modified, ce_info);
 
   return TRUE;
 }
@@ -2469,7 +2469,7 @@ check_cond_move_block (basic_block bb, r
    converting the block.  */
 
 static int
-cond_move_process_if_block (struct df *df, bitmap modified, 
+cond_move_process_if_block (bitmap modified, 
 			    struct ce_if_block *ce_info)
 {
   basic_block then_bb = ce_info->then_bb;
@@ -2631,7 +2631,7 @@ cond_move_process_if_block (struct df *d
     }
   delete_insn (jump);
 
-  merge_if_block (df, modified, ce_info);
+  merge_if_block (modified, ce_info);
 
   return TRUE;
 }
@@ -2640,15 +2640,14 @@ cond_move_process_if_block (struct df *d
    straight line code.  Return true if successful.  */
 
 static int
-process_if_block (struct df *df, bitmap modified, 
-		  struct ce_if_block * ce_info)
+process_if_block (bitmap modified, struct ce_if_block * ce_info)
 {
   if (! reload_completed
-      && noce_process_if_block (df, modified, ce_info))
+      && noce_process_if_block (modified, ce_info))
     return TRUE;
 
   if (HAVE_conditional_move
-      && cond_move_process_if_block (df, modified, ce_info))
+      && cond_move_process_if_block (modified, ce_info))
     return TRUE;
 
   if (HAVE_conditional_execution && reload_completed)
@@ -2657,14 +2656,14 @@ process_if_block (struct df *df, bitmap 
          || tests into the conditional code, and if that fails, go back and
          handle it without the && and ||, which at present handles the && case
          if there was no ELSE block.  */
-      if (cond_exec_process_if_block (df, modified, ce_info, TRUE))
+      if (cond_exec_process_if_block (modified, ce_info, TRUE))
 	return TRUE;
 
       if (ce_info->num_multiple_test_blocks)
 	{
 	  cancel_changes (0);
 
-	  if (cond_exec_process_if_block (df, modified, ce_info, FALSE))
+	  if (cond_exec_process_if_block (modified, ce_info, FALSE))
 	    return TRUE;
 	}
     }
@@ -2675,7 +2674,7 @@ process_if_block (struct df *df, bitmap 
 /* Merge the blocks and mark for local life update.  */
 
 static void
-merge_if_block (struct df *df, bitmap modified, struct ce_if_block * ce_info)
+merge_if_block (bitmap modified, struct ce_if_block * ce_info)
 {
   basic_block test_bb = ce_info->test_bb;	/* last test block */
   basic_block then_bb = ce_info->then_bb;	/* THEN */
@@ -2700,7 +2699,6 @@ merge_if_block (struct df *df, bitmap mo
 	{
 	  bb = fallthru;
 	  fallthru = block_fallthru (bb);
-	  df_delete_basic_block (df, bb->index);
 	  merge_blocks (combo_bb, bb);
 	  num_true_changes++;
 	}
@@ -2713,7 +2711,6 @@ merge_if_block (struct df *df, bitmap mo
 
   if (then_bb)
     {
-      df_delete_basic_block (df, then_bb->index);
       merge_blocks (combo_bb, then_bb);
       num_true_changes++;
     }
@@ -2723,7 +2720,6 @@ merge_if_block (struct df *df, bitmap mo
      get their addresses taken.  */
   if (else_bb)
     {
-      df_delete_basic_block (df, else_bb->index);
       merge_blocks (combo_bb, else_bb);
       num_true_changes++;
     }
@@ -2766,7 +2762,6 @@ merge_if_block (struct df *df, bitmap mo
     {
       /* We can merge the JOIN cleanly and update the dataflow try
 	 again on this pass.*/
-      df_delete_basic_block (df, join_bb->index);
       merge_blocks (combo_bb, join_bb);
       num_true_changes++;
     }
@@ -2844,11 +2839,11 @@ find_if_header (struct df *df, bitmap mo
   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
 #endif
 
-  if (find_if_block (df, modified, &ce_info))
+  if (find_if_block (modified, &ce_info))
     goto success;
 
   if (HAVE_trap && HAVE_conditional_trap
-      && find_cond_trap (df, modified, test_bb, then_edge, else_edge))
+      && find_cond_trap (modified, test_bb, then_edge, else_edge))
     goto success;
 
   if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY
@@ -2943,7 +2938,7 @@ block_jumps_and_fallthru_p (basic_block 
    Return TRUE if we were successful at converting the block.  */
 
 static int
-find_if_block (struct df *df, bitmap modified, struct ce_if_block * ce_info)
+find_if_block (bitmap modified, struct ce_if_block * ce_info)
 {
   basic_block test_bb = ce_info->test_bb;
   basic_block then_bb = ce_info->then_bb;
@@ -3148,14 +3143,14 @@ find_if_block (struct df *df, bitmap mod
   ce_info->else_bb = else_bb;
   ce_info->join_bb = join_bb;
 
-  return process_if_block (df, modified, ce_info);
+  return process_if_block (modified, ce_info);
 }
 
 /* Convert a branch over a trap, or a branch
    to a trap, into a conditional trap.  */
 
 static int
-find_cond_trap (struct df *df, bitmap modified, 
+find_cond_trap (bitmap modified, 
 		basic_block test_bb, edge then_edge, edge else_edge)
 {
   basic_block then_bb = then_edge->dest;
@@ -3219,10 +3214,7 @@ find_cond_trap (struct df *df, bitmap mo
   /* Delete the trap block if possible.  */
   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
   if (EDGE_COUNT (trap_bb->preds) == 0)
-    {
-      df_delete_basic_block (df, trap_bb->index);
-      delete_basic_block (trap_bb);
-    }
+    delete_basic_block (trap_bb);
 
   bitmap_set_bit (modified, test_bb->index);
   bitmap_set_bit (modified, then_bb->index);
@@ -3239,7 +3231,7 @@ find_cond_trap (struct df *df, bitmap mo
       new_ce_info.then_bb = NULL;
       new_ce_info.else_bb = NULL;
       new_ce_info.join_bb = other_bb;
-      merge_if_block (df, modified, &new_ce_info);
+      merge_if_block (modified, &new_ce_info);
     }
   else
     {
@@ -3441,7 +3433,6 @@ find_if_case_1 (struct df *df, bitmap mo
   bitmap_set_bit (modified, else_bb->index);
 
   then_bb_index = then_bb->index;
-  df_delete_basic_block (df, then_bb_index);
   delete_basic_block (then_bb);
 
   /* Make rest of code believe that the newly created block is the THEN_BB
@@ -3450,7 +3441,7 @@ find_if_case_1 (struct df *df, bitmap mo
     {
       int old_index = new_bb->index;
       new_bb->index = then_bb_index;
-      SET_BASIC_BLOCK (then_bb_index, new_bb);
+      df_bb_replace (then_bb_index, new_bb);
       bitmap_set_bit (modified, then_bb_index);
       SET_BASIC_BLOCK (old_index, NULL);
       /* Since the fallthru edge was redirected from test_bb to new_bb,
@@ -3543,7 +3534,6 @@ find_if_case_2 (struct df *df, bitmap mo
 
   bitmap_set_bit (modified, test_bb->index);
   bitmap_set_bit (modified, then_bb->index);
-  df_delete_basic_block (df, else_bb->index);
   delete_basic_block (else_bb);
 
   num_true_changes++;
@@ -3869,9 +3859,7 @@ if_convert (void)
   basic_block bb;
   int pass;
   bitmap modified = BITMAP_ALLOC (NULL);
-  struct df * df = df_init (0, DF_LR_RUN_DCE);
-  df_lr_add_problem (df);
-  df_live_add_problem (df);
+  struct df * df;
 
   num_possible_if_blocks = 0;
   num_updated_if_blocks = 0;
@@ -3892,6 +3880,10 @@ if_convert (void)
   if (HAVE_conditional_execution)
     calculate_dominance_info (CDI_POST_DOMINATORS);
 
+  df = df_init (0, DF_LR_RUN_DCE);
+  df_lr_add_problem (df);
+  df_live_add_problem (df);
+
   /* Go through each of the basic blocks looking for things to convert.  If we
      have conditional execution, we make multiple passes to allow us to handle
      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
@@ -4007,6 +3999,7 @@ struct tree_opt_pass pass_rtl_ifcvt =
   0,                                    /* properties_destroyed */
   0,                                    /* todo_flags_start */
   TODO_df_finish |
+  TODO_verify_flow |
   TODO_dump_func,                       /* todo_flags_finish */
   'C'                                   /* letter */
 };
@@ -4044,6 +4037,7 @@ struct tree_opt_pass pass_if_after_combi
   0,                                    /* todo_flags_start */
   TODO_df_finish |
   TODO_dump_func |
+  TODO_verify_flow |
   TODO_ggc_collect,                     /* todo_flags_finish */
   'C'                                   /* letter */
 };
@@ -4079,8 +4073,7 @@ struct tree_opt_pass pass_if_after_reloa
   0,                                    /* todo_flags_start */
   TODO_df_finish |
   TODO_dump_func |
+  TODO_verify_flow |
   TODO_ggc_collect,                     /* todo_flags_finish */
   'E'                                   /* letter */
 };
-
-
Index: recog.c
===================================================================
--- recog.c	(revision 118540)
+++ recog.c	(working copy)
@@ -2845,28 +2848,6 @@ peep2_find_free_register (int from, int 
   return NULL_RTX;
 }
 
-/* Delete dataflow info and insn from START to FINISH.  */
-
-static void
-delete_insn_chain_and_dflow (struct dataflow *dflow, rtx start, rtx finish)
-{
-  rtx next;
-  rtx orig_start = start;
-
-  while (1)
-    {
-      next = NEXT_INSN (start);
-      if (INSN_P (start))
-	df_insn_refs_delete (dflow, start);
-
-      if (start == finish)
-	break;
-      start = next;
-    }
-
-  delete_insn_chain (orig_start, finish);
-}
-
 /* Perform the peephole2 optimization pass.  */
 
 static void
@@ -2882,11 +2863,9 @@ peephole2_optimize (void)
   bool do_cleanup_cfg = false;
   bool do_rebuild_jump_labels = false;
   struct df * df = df_init (0, DF_LR_RUN_DCE);
-  struct dataflow *dflow = df->problems_by_index [DF_SCAN];
 
   df_lr_add_problem (df);
   df_live_add_problem (df);
-  df_ru_add_problem (df);
   df_analyze (df);
 
   /* Initialize the regsets we're going to use.  */
@@ -3024,7 +3003,7 @@ peephole2_optimize (void)
 		  try = emit_insn_after_setloc (try, peep2_insn_data[i].insn,
 					        INSN_LOCATOR (peep2_insn_data[i].insn));
 		  before_try = PREV_INSN (insn);
-		  delete_insn_chain_and_dflow (dflow, insn, peep2_insn_data[i].insn);
+		  delete_insn_chain (insn, peep2_insn_data[i].insn);
 
 		  /* Re-insert the EH_REGION notes.  */
 		  if (note || (was_call && nonlocal_goto_handler_labels))
@@ -3092,7 +3071,6 @@ peephole2_optimize (void)
 		  x = try;
 		  do
 		    {
-		      df_insn_create_insn_record (dflow, insn);
 		      if (INSN_P (x))
 			{
 			  if (--i < 0)
@@ -3101,21 +3079,14 @@ peephole2_optimize (void)
 			      && peep2_insn_data[i].insn == NULL_RTX)
 			    peep2_current_count++;
 			  peep2_insn_data[i].insn = x;
-			  df_insn_refs_record (dflow, bb, insn);
-			  df_lr_simulate_one_insn (df, bb, insn, live);
-#if 0
-			  propagate_one_insn (pbi, x);
-			  gcc_assert (bitmap_equal_p (livep, live));
-#endif
+			  df_insn_rescan (x);
+			  df_lr_simulate_one_insn (df, bb, x, live);
 			  bitmap_copy (peep2_insn_data[i].live_before, live);
 			}
 		      x = PREV_INSN (x);
 		    }
 		  while (x != prev);
 
-		  /* ??? Should verify that LIVE now matches what we
-		     had before the new sequence.  */
-
 		  peep2_current = i;
 #endif
 
@@ -3302,7 +3273,7 @@ struct tree_opt_pass pass_split_all_insn
   0,                                    /* properties_provided */
   0,                                    /* properties_destroyed */
   0,                                    /* todo_flags_start */
-  TODO_dump_func,                       /* todo_flags_finish */
+ TODO_dump_func,                       /* todo_flags_finish */
   0                                     /* letter */
 };
 
@@ -3408,6 +3379,7 @@ struct tree_opt_pass pass_split_before_s
   0,                                    /* properties_provided */
   0,                                    /* properties_destroyed */
   0,                                    /* todo_flags_start */
+  TODO_verify_flow |
   TODO_dump_func,                       /* todo_flags_finish */
   0                                     /* letter */
 };
Index: emit-rtl.c
===================================================================
--- emit-rtl.c	(revision 118540)
+++ emit-rtl.c	(working copy)
@@ -57,6 +57,7 @@ Software Foundation, 51 Franklin Street,
 #include "debug.h"
 #include "langhooks.h"
 #include "tree-pass.h"
+#include "df.h"
 
 /* Commonly used modes.  */
 
@@ -3408,7 +3409,7 @@ add_insn_after (rtx insn, rtx after)
     {
       set_block_for_insn (insn, bb);
       if (INSN_P (insn))
-	bb->flags |= BB_DIRTY;
+	df_insn_rescan (insn);
       /* Should not happen as first in the BB is always
 	 either NOTE or LABEL.  */
       if (BB_END (bb) == after
@@ -3474,7 +3476,7 @@ add_insn_before (rtx insn, rtx before)
     {
       set_block_for_insn (insn, bb);
       if (INSN_P (insn))
-	bb->flags |= BB_DIRTY;
+	df_insn_rescan (insn);
       /* Should not happen as first in the BB is always either NOTE or
 	 LABEL.  */
       gcc_assert (BB_HEAD (bb) != insn
@@ -3489,6 +3491,20 @@ add_insn_before (rtx insn, rtx before)
     PREV_INSN (XVECEXP (PATTERN (before), 0, 0)) = insn;
 }
 
+
+/* Replace insn with an deleted instruction note.  */
+
+void set_insn_deleted (rtx insn)
+{
+  df_insn_delete (insn);
+  PUT_CODE (insn, NOTE);
+#ifndef USE_MAPPED_LOCATION
+  NOTE_SOURCE_FILE (insn) = 0;
+#endif
+  NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
+}
+
+
 /* Remove an insn from its doubly-linked list.  This function knows how
    to handle sequences.  */
 void
@@ -3498,6 +3514,8 @@ remove_insn (rtx insn)
   rtx prev = PREV_INSN (insn);
   basic_block bb;
 
+  df_insn_delete (insn);
+
   if (prev)
     {
       NEXT_INSN (prev) = next;
@@ -3659,7 +3677,10 @@ reorder_insns (rtx from, rtx to, rtx aft
 
       for (x = from; x != NEXT_INSN (to); x = NEXT_INSN (x))
 	if (!BARRIER_P (x))
-	  set_block_for_insn (x, bb);
+	  {
+	    set_block_for_insn (x, bb);
+	    df_insn_change_bb (x);
+	  }
     }
 }
 
@@ -3902,9 +3923,15 @@ emit_insn_after_1 (rtx first, rtx after)
       bb->flags |= BB_DIRTY;
       for (last = first; NEXT_INSN (last); last = NEXT_INSN (last))
 	if (!BARRIER_P (last))
-	  set_block_for_insn (last, bb);
+	  {
+	    set_block_for_insn (last, bb);
+	    df_insn_rescan (last);
+	  }
       if (!BARRIER_P (last))
-	set_block_for_insn (last, bb);
+	{
+	  set_block_for_insn (last, bb);
+	  df_insn_rescan (last);
+	}
       if (BB_END (bb) == after)
 	BB_END (bb) = last;
     }
Index: loop-invariant.c
===================================================================
--- loop-invariant.c	(revision 118540)
+++ loop-invariant.c	(working copy)
@@ -121,6 +121,11 @@ struct invariant
   unsigned stamp;
 };
 
+/* Table of invariants indexed by the df_ref uid field.  */
+
+static unsigned int invariant_table_size = 0;
+static struct invariant ** invariant_table;
+
 /* Entry for hash table of invariant expressions.  */
 
 struct invariant_expr_entry
@@ -156,6 +161,22 @@ static VEC(invariant_p,heap) *invariants
 
 static struct df *df = NULL;
 
+/* Check the size of the invariant table and realloc if necessary.  */
+
+static void 
+check_invariant_table_size (void)
+{
+  if (invariant_table_size < DF_DEFS_SIZE(df))
+    {
+      unsigned int new_size = DF_DEFS_SIZE (df) + (DF_DEFS_SIZE (df) / 4);
+      invariant_table = xrealloc (invariant_table, 
+				  sizeof (struct rtx_iv *) * new_size);
+      memset (&invariant_table[invariant_table_size], 0, 
+	      (new_size - invariant_table_size) * sizeof (struct rtx_iv *));
+      invariant_table_size = new_size;
+    }
+}
+
 /* Test for possibility of invariantness of X.  */
 
 static bool
@@ -240,13 +261,14 @@ invariant_for_use (struct df_ref *use)
   if (!defs || defs->next)
     return NULL;
   def = defs->ref;
-  if (!DF_REF_DATA (def))
+  check_invariant_table_size ();
+  if (!invariant_table[DF_REF_ID(def)])
     return NULL;
 
   def_bb = DF_REF_BB (def);
   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
     return NULL;
-  return DF_REF_DATA (def);
+  return invariant_table[DF_REF_ID(def)];
 }
 
 /* Computes hash value for invariant expression X in INSN.  */
@@ -618,6 +640,9 @@ find_defs (struct loop *loop, basic_bloc
 
   df_set_blocks (df, blocks);
   df_analyze (df);
+
+  check_invariant_table_size ();
+
   BITMAP_FREE (blocks);
 }
 
@@ -706,7 +731,8 @@ check_dependency (basic_block bb, struct
     return false;
   
   def = defs->ref;
-  inv = DF_REF_DATA (def);
+  check_invariant_table_size ();
+  inv = invariant_table[DF_REF_ID(def)];
   if (!inv)
     return false;
   
@@ -714,9 +740,10 @@ check_dependency (basic_block bb, struct
   gcc_assert (def_data != NULL);
   
   def_bb = DF_REF_BB (def);
-  /* Note that in case bb == def_bb, we know that the definition dominates
-     insn, because def has DF_REF_DATA defined and we process the insns
-     in the basic block bb sequentially.  */
+  /* Note that in case bb == def_bb, we know that the definition
+     dominates insn, because def has invariant_table[DF_REF_ID(def)]
+     defined and we process the insns in the basic block bb
+     sequentially.  */
   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
     return false;
   
@@ -810,7 +837,8 @@ find_invariant_insn (rtx insn, bool alwa
   if (simple)
     {
       ref = df_find_def (df, insn, dest);
-      DF_REF_DATA (ref) = inv;
+      check_invariant_table_size ();
+      invariant_table[DF_REF_ID(ref)] = inv;
     }
 }
 
@@ -1282,22 +1310,19 @@ free_inv_motion_data (void)
   struct def *def;
   struct invariant *inv;
 
+  check_invariant_table_size ();
   for (i = 0; i < DF_DEFS_SIZE (df); i++)
     {
-      struct df_ref * ref = DF_DEFS_GET (df, i);
-      if (!ref)
-	continue;
-
-      inv = DF_REF_DATA (ref);
-      if (!inv)
-	continue;
-
-      def = inv->def;
-      gcc_assert (def != NULL);
-
-      free_use_list (def->uses);
-      free (def);
-      DF_REF_DATA (ref) = NULL;
+      inv = invariant_table[i];
+      if (inv)
+	{
+	  def = inv->def;
+	  gcc_assert (def != NULL);
+	  
+	  free_use_list (def->uses);
+	  free (def);
+	  invariant_table[i] = NULL;
+	}
     }
 
   for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
@@ -1340,9 +1365,9 @@ move_loop_invariants (struct loops *loop
 {
   struct loop *loop;
   unsigned i;
-  df = df_init (DF_UD_CHAIN, DF_EQ_NOTES);
+  df = df_init (DF_UD_CHAIN + DF_DU_CHAIN, DF_EQ_NOTES);
   df_chain_add_problem (df);
- 
+
   /* Process the loops, innermost first.  */
   loop = loops->tree_root;
   while (loop->inner)
@@ -1366,6 +1391,10 @@ move_loop_invariants (struct loops *loop
     if (loops->parray[i])
       free_loop_data (loops->parray[i]);
 
+  free (invariant_table);
+  invariant_table = NULL;
+  invariant_table_size = 0;
+
 #ifdef ENABLE_CHECKING
   verify_flow_info ();
 #endif
Index: loop-iv.c
===================================================================
--- loop-iv.c	(revision 118540)
+++ loop-iv.c	(working copy)
@@ -92,9 +92,16 @@ struct biv_entry
   struct rtx_iv iv;	/* Value of the biv.  */
 };
 
+static bool clean_slate = true;
+
+static unsigned int iv_ref_table_size = 0;
+
+/* Table of rtx_ivs indexed by the df_ref uid field.  */
+static struct rtx_iv ** iv_ref_table;
+
 /* Induction variable stored at the reference.  */
-#define DF_REF_IV(REF) ((struct rtx_iv *) DF_REF_DATA (REF))
-#define DF_REF_IV_SET(REF, IV) DF_REF_DATA (REF) = (IV)
+#define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
+#define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
 
 /* The current loop.  */
 
@@ -172,6 +179,21 @@ lowpart_subreg (enum machine_mode outer_
 			      subreg_lowpart_offset (outer_mode, inner_mode));
 }
 
+static void 
+check_iv_ref_table_size (void)
+{
+  if (iv_ref_table_size < DF_DEFS_SIZE(df))
+    {
+      unsigned int new_size = DF_DEFS_SIZE (df) + (DF_DEFS_SIZE (df) / 4);
+      iv_ref_table = xrealloc (iv_ref_table, 
+			       sizeof (struct rtx_iv *) * new_size);
+      memset (&iv_ref_table[iv_ref_table_size], 0, 
+	      (new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
+      iv_ref_table_size = new_size;
+    }
+}
+
+
 /* Checks whether REG is a well-behaved register.  */
 
 static bool
@@ -206,16 +228,16 @@ clear_iv_info (void)
 {
   unsigned i, n_defs = DF_DEFS_SIZE (df);
   struct rtx_iv *iv;
-  struct df_ref *def;
 
+  check_iv_ref_table_size ();
   for (i = 0; i < n_defs; i++)
     {
-      def = DF_DEFS_GET (df, i);
-      iv = DF_REF_IV (def);
-      if (!iv)
-	continue;
-      free (iv);
-      DF_REF_IV_SET (def, NULL);
+      iv = iv_ref_table[i];
+      if (iv)
+	{
+	  free (iv);
+	  iv_ref_table[i] = NULL;
+	}
     }
 
   htab_empty (bivs);
@@ -245,16 +267,16 @@ iv_analysis_loop_init (struct loop *loop
   basic_block *body = get_loop_body_in_dom_order (loop), bb;
   bitmap blocks = BITMAP_ALLOC (NULL);
   unsigned i;
-  bool first_time = (df == NULL);
 
   current_loop = loop;
 
   /* Clear the information from the analysis of the previous loop.  */
-  if (first_time)
+  if (clean_slate)
     {
-      df = df_init (DF_UD_CHAIN, DF_EQ_NOTES);
+      df = df_init (DF_UD_CHAIN + DF_DU_CHAIN, DF_EQ_NOTES);
       df_chain_add_problem (df);
       bivs = htab_create (10, biv_hash, biv_eq, free);
+      clean_slate = false;
     }
   else
     clear_iv_info ();
@@ -265,7 +287,8 @@ iv_analysis_loop_init (struct loop *loop
       bitmap_set_bit (blocks, bb->index);
     }
   df_set_blocks (df, blocks);
-  df_analyze (df); 
+  df_analyze (df);
+  check_iv_ref_table_size ();
   BITMAP_FREE (blocks);
   free (body);
 }
@@ -785,6 +808,7 @@ record_iv (struct df_ref *def, struct rt
   struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
 
   *recorded_iv = *iv;
+  check_iv_ref_table_size ();
   DF_REF_IV_SET (def, recorded_iv);
 }
 
@@ -1030,7 +1054,8 @@ iv_analyze_def (struct df_ref *def, stru
       fprintf (dump_file, " in insn ");
       print_rtl_single (dump_file, insn);
     }
-
+  
+  check_iv_ref_table_size ();
   if (DF_REF_IV (def))
     {
       if (dump_file)
@@ -1238,9 +1263,12 @@ iv_analysis_done (void)
   if (df)
     {
       clear_iv_info ();
+      clean_slate = true;
       df_finish (df);
-      df = NULL;
       htab_delete (bivs);
+      free (iv_ref_table);
+      iv_ref_table = NULL;
+      iv_ref_table_size = 0;
       bivs = NULL;
     }
 }
Index: cfglayout.c
===================================================================
--- cfglayout.c	(revision 118540)
+++ cfglayout.c	(working copy)
@@ -807,19 +807,20 @@ fixup_reorder_chain (void)
 
   prev_bb = ENTRY_BLOCK_PTR;
   bb = ENTRY_BLOCK_PTR->next_bb;
-  index = NUM_FIXED_BLOCKS;
 
-  for (; bb; prev_bb = bb, bb = bb->aux, index ++)
+  for (; bb; prev_bb = bb, bb = bb->aux)
     {
-      bb->index = index;
-      SET_BASIC_BLOCK (index, bb);
-
       bb->prev_bb = prev_bb;
       prev_bb->next_bb = bb;
     }
   prev_bb->next_bb = EXIT_BLOCK_PTR;
   EXIT_BLOCK_PTR->prev_bb = prev_bb;
 
+  /* Now that the prev and next ptrs are in place, let compact_blocks
+     deal with the array and the indexes.  It knows how to keep the
+     dataflow up to date.  */
+  compact_blocks ();
+
   /* Annoying special case - jump around dead jumptables left in the code.  */
   FOR_EACH_BB (bb)
     {
@@ -829,7 +830,7 @@ fixup_reorder_chain (void)
       FOR_EACH_EDGE (e, ei, bb->succs)
 	if (e->flags & EDGE_FALLTHRU)
 	  break;
-
+      
       if (e && !can_fallthru (e->src, e->dest))
 	force_nonfallthru (e);
     }
Index: rtl.h
===================================================================
--- rtl.h	(revision 118540)
+++ rtl.h	(working copy)
@@ -832,20 +832,16 @@ extern const char * const reg_note_name[
 /* Opaque data.  */
 #define NOTE_DATA(INSN)	        RTL_CHECKC1 (INSN, 4, NOTE)
 #define NOTE_DELETED_LABEL_NAME(INSN) XCSTR (INSN, 4, NOTE)
+#define SET_INSN_DELETED(INSN) set_insn_deleted (INSN);
 #ifdef USE_MAPPED_LOCATION
 #define NOTE_SOURCE_LOCATION(INSN) XCUINT (INSN, 5, NOTE)
 #define NOTE_EXPANDED_LOCATION(XLOC, INSN)	\
   (XLOC) = expand_location (NOTE_SOURCE_LOCATION (INSN))
-#define SET_INSN_DELETED(INSN) \
-  (PUT_CODE (INSN, NOTE), NOTE_LINE_NUMBER (INSN) = NOTE_INSN_DELETED)
 #else
 #define NOTE_EXPANDED_LOCATION(XLOC, INSN)	\
   ((XLOC).file = NOTE_SOURCE_FILE (INSN),	\
    (XLOC).line = NOTE_LINE_NUMBER (INSN))
 #define NOTE_SOURCE_FILE(INSN)	XCSTR (INSN, 4, NOTE)
-#define SET_INSN_DELETED(INSN) \
-  (PUT_CODE (INSN, NOTE),  NOTE_SOURCE_FILE (INSN) = 0, \
-   NOTE_LINE_NUMBER (INSN) = NOTE_INSN_DELETED)
 #endif
 #define NOTE_BLOCK(INSN)	XCTREE (INSN, 4, NOTE)
 #define NOTE_EH_HANDLER(INSN)	XCINT (INSN, 4, NOTE)
@@ -1654,6 +1650,7 @@ extern enum machine_mode choose_hard_reg
 
 /* In emit-rtl.c  */
 extern rtx set_unique_reg_note (rtx, enum reg_note, rtx);
+extern void set_insn_deleted (rtx);
 
 /* Functions in rtlanal.c */
 
Index: Makefile.in
===================================================================
--- Makefile.in	(revision 118540)
+++ Makefile.in	(working copy)
@@ -2269,7 +2269,7 @@ emit-rtl.o : emit-rtl.c $(CONFIG_H) $(SY
    $(TREE_H) $(FLAGS_H) $(FUNCTION_H) $(REGS_H) insn-config.h $(RECOG_H) \
    $(GGC_H) $(EXPR_H) hard-reg-set.h bitmap.h toplev.h $(BASIC_BLOCK_H) \
    $(HASHTAB_H) $(TM_P_H) debug.h langhooks.h tree-pass.h gt-emit-rtl.h \
-   $(REAL_H)
+   $(REAL_H) $(DF_H)
 real.o : real.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
    toplev.h $(TM_P_H) $(REAL_H)
 dfp.o : dfp.c dfp.h $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H)	$(TREE_H) \
Index: sched-rgn.c
===================================================================
--- sched-rgn.c	(revision 118540)
+++ sched-rgn.c	(working copy)
@@ -3166,6 +3166,7 @@ struct tree_opt_pass pass_sched =
   0,                                    /* todo_flags_start */
   TODO_df_finish |
   TODO_dump_func |
+  TODO_verify_flow |
   TODO_ggc_collect,                     /* todo_flags_finish */
   'S'                                   /* letter */
 };
@@ -3185,6 +3186,7 @@ struct tree_opt_pass pass_sched2 =
   0,                                    /* todo_flags_start */
   TODO_df_finish |
   TODO_dump_func |
+  TODO_verify_flow |
   TODO_ggc_collect,                     /* todo_flags_finish */
   'R'                                   /* letter */
 };
Index: cfgrtl.c
===================================================================
--- cfgrtl.c	(revision 118540)
+++ cfgrtl.c	(working copy)
@@ -307,7 +307,6 @@ create_basic_block_structure (rtx head, 
   update_bb_for_insn (bb);
   BB_SET_PARTITION (bb, BB_UNPARTITIONED);
 
-  
 
   /* Tag the block so that we know it has been used when considering
      other basic block notes.  */
@@ -342,7 +341,6 @@ rtl_create_basic_block (void *headp, voi
 
   bb = create_basic_block_structure (head, end, NULL, after);
   bb->aux = NULL;
-
   return bb;
 }
 
@@ -390,6 +388,8 @@ rtl_delete_block (basic_block b)
   /* Selectively delete the entire chain.  */
   BB_HEAD (b) = NULL;
   delete_insn_chain (insn, end);
+
+  df_delete_basic_block (b->index);
 }
 
 /* Records the basic block struct in BLOCK_FOR_INSN for every insn.  */
@@ -473,7 +473,10 @@ update_bb_for_insn (basic_block bb)
   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
     {
       if (!BARRIER_P (insn))
-	set_block_for_insn (insn, bb);
+	{
+	  set_block_for_insn (insn, bb);
+	  df_insn_rescan (insn);
+	}
       if (insn == BB_END (bb))
 	break;
     }
@@ -622,17 +625,23 @@ rtl_merge_blocks (basic_block a, basic_b
       rtx x;
 
       for (x = a_end; x != b_end; x = NEXT_INSN (x))
-	set_block_for_insn (x, a);
+	{
+	  set_block_for_insn (x, a);
+	  df_insn_change_bb (x);
+	}
 
       set_block_for_insn (b_end, a);
+      df_insn_change_bb (b_end);
 
       a_end = b_end;
     }
 
+  df_delete_basic_block (b->index);
   BB_END (a) = a_end;
 
 }
 
+
 /* Return true when block A and B can be merged.  */
 static bool
 rtl_can_merge_blocks (basic_block a,basic_block b)
@@ -829,7 +838,10 @@ try_redirect_by_replacing_jump (edge e, 
 
 	      for (tmp = NEXT_INSN (BB_END (src)); tmp != barrier;
 		   tmp = NEXT_INSN (tmp))
-		set_block_for_insn (tmp, src);
+		{
+		  set_block_for_insn (tmp, src);
+	      	  df_insn_change_bb (tmp);
+		}
 
 	      NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
 	      PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
@@ -2608,7 +2620,11 @@ cfg_layout_merge_blocks (basic_block a, 
       for (insn = BB_HEAD (b);
 	   insn != NEXT_INSN (BB_END (b));
 	   insn = NEXT_INSN (insn))
-	set_block_for_insn (insn, a);
+	{
+	  set_block_for_insn (insn, a);
+	  df_insn_change_bb (insn);
+	}
+
       insn = BB_HEAD (b);
       /* Skip possible DELETED_LABEL insn.  */
       if (!NOTE_INSN_BASIC_BLOCK_P (insn))
@@ -2619,6 +2635,8 @@ cfg_layout_merge_blocks (basic_block a, 
       delete_insn (insn);
     }
 
+  df_delete_basic_block (b->index);
+
   /* Possible tablejumps and barriers should appear after the block.  */
   if (b->il.rtl->footer)
     {
@@ -3030,7 +3048,7 @@ struct cfg_hooks rtl_cfg_hooks = {
 /* We do not want to declare these functions in a header file, since they
    should only be used through the cfghooks interface, and we do not want to
    move them here since it would require also moving quite a lot of related
-   code.  */
+   code.  They are in cfglayout.c.  */
 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
 extern basic_block cfg_layout_duplicate_bb (basic_block);
 
Index: dce.c
===================================================================
--- dce.c	(revision 118540)
+++ dce.c	(working copy)
@@ -212,11 +212,10 @@ init_dce (bool fast)
    DF_DELETE is true.  */
 
 static void
-delete_unmarked_insns (bool df_delete)
+delete_unmarked_insns (void)
 {
   basic_block bb;
   rtx insn, next;
-  struct dataflow *dflow = dce_df->problems_by_index[DF_SCAN];
 
   something_changed = false;
   FOR_EACH_BB (bb)
@@ -228,8 +227,6 @@ delete_unmarked_insns (bool df_delete)
 	    fprintf (dump_file, "DCE: Deleting insn %d\n", INSN_UID (insn));
 	  /* XXX: This may need to be changed to delete_insn_and_edges */
 	  delete_insn (insn);
-	  if (df_delete)
-	    df_insn_refs_delete (dflow, insn);
 	  something_changed = true;
 	}
 }
@@ -362,6 +359,9 @@ rest_of_handle_dce (void)
   while (VEC_length (rtx, worklist) > 0)
     mark_reg_dependencies (VEC_pop (rtx, worklist));
 
+  /* df_remove_problem (dce_df, dce_df->problems_by_index[DF_RD]); */
+  df_remove_problem (dce_df, dce_df->problems_by_index[DF_CHAIN]);
+  delete_unmarked_insns ();
   end_dce ();
   return 0;
 }
@@ -559,7 +559,7 @@ dce_process_block (basic_block bb, bool 
 }
 
 static void
-fast_dce (bool df_delete)
+fast_dce (void)
 {
   int *postorder = df_get_postorder (dce_df);
   int n_blocks = df_get_n_blocks (dce_df);
@@ -624,7 +624,7 @@ fast_dce (bool df_delete)
 
 	  /* So something was deleted that requires a redo.  Do it on
 	     the cheap.  */
-	  delete_unmarked_insns (df_delete);
+	  delete_unmarked_insns ();
 	  bitmap_clear (marked);
 	  bitmap_clear (processed);
 	  bitmap_clear (redo_out);
@@ -644,7 +644,7 @@ fast_dce (bool df_delete)
       loop_count++;
     }
 
-  delete_unmarked_insns (df_delete);
+  delete_unmarked_insns ();
 
   BITMAP_FREE (processed);
   BITMAP_FREE (changed);
@@ -659,7 +659,7 @@ static unsigned int
 rest_of_handle_fast_dce (void)
 {
   init_dce (true);
-  fast_dce (false);
+  fast_dce ();
   end_fast_dce ();
   return 0;
 }
@@ -680,7 +680,7 @@ run_fast_df_dce (struct df *df)
 {
   dce_df = df;
   init_dce (true);
-  fast_dce (true);
+  fast_dce ();
   BITMAP_FREE (marked);
   BITMAP_FREE (marked_libcalls);
   dce_df = NULL;
@@ -1691,7 +1691,9 @@ rest_of_handle_dse (void)
       mark_reg_dependencies (insn);
       mark_dependent_stores (insn);
     }
-  delete_unmarked_insns (false);
+  /* df_remove_problem (dce_df, dce_df->problems_by_index[DF_RD]); */
+  df_remove_problem (dce_df, dce_df->problems_by_index[DF_CHAIN]);
+  delete_unmarked_insns ();
   if (stores.stores)
     {
       end_unmarked_stores ();
Index: df-scan.c
===================================================================
--- df-scan.c	(revision 118540)
+++ df-scan.c	(working copy)
@@ -237,7 +237,7 @@ df_scan_free_bb_info (struct dataflow *d
   struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
   if (bb_info)
     {
-      df_bb_refs_delete (dflow, bb->index);
+      df_bb_delete (bb->index);
       pool_free (dflow->block_pool, bb_info);
     }
 }
@@ -308,6 +308,7 @@ df_scan_alloc (struct dataflow *dflow, b
       bb_info->artificial_uses = NULL;
     }
 
+  df->out_of_date_transfer_functions = BITMAP_ALLOC (NULL);
   df->hardware_regs_used = BITMAP_ALLOC (NULL);
   df->regular_block_artificial_uses = BITMAP_ALLOC (NULL);
   df->eh_block_artificial_uses = BITMAP_ALLOC (NULL);
@@ -332,6 +333,8 @@ df_scan_free (struct dataflow *dflow)
   if (df->blocks_to_analyze)
     BITMAP_FREE (df->blocks_to_analyze);
 
+  BITMAP_FREE (df->out_of_date_transfer_functions);
+
   free (dflow);
 }
 
@@ -398,6 +401,7 @@ static struct df_problem problem_SCAN =
   NULL,                       /* Transfer function.  */
   NULL,                       /* Finalize function.  */
   df_scan_free,               /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   df_scan_start_dump,         /* Debugging.  */
   df_scan_start_block,        /* Debugging start block.  */
   NULL,                       /* Debugging end block.  */
@@ -491,11 +495,10 @@ df_grow_ref_info (struct df_ref_info *re
 }
 
 
-/* Check and grow the ref information if necessary.
-   This routine guarantees bitmap_size + bitmap_add 
-   amount of entries in refs array.
-   It updates ref_info->refs_size only
-   and does not change ref_info->bitmap_size.  */
+/* Check and grow the ref information if necessary.  This routine
+   guarantees bitmap_size + BITMAP_ADDEND amount of entries in refs
+   array.  It updates ref_info->refs_size only and does not change
+   ref_info->bitmap_size.  */
 
 static void
 df_check_and_grow_ref_info (struct df_ref_info *ref_info, 
@@ -508,6 +511,7 @@ df_check_and_grow_ref_info (struct df_re
     }
 }
 
+
 /* Grow the ref information.  If the current size is less than the
    number of instructions, grow to 25% more than the number of
    instructions.  */
@@ -605,7 +609,10 @@ df_scan_blocks (struct df *df, bitmap bl
 	    BITMAP_FREE (blocks_to_reset);
 	}
 
-      df_refs_delete (dflow, local_blocks_to_scan);
+      EXECUTE_IF_SET_IN_BITMAP (local_blocks_to_scan, 0, bb_index, bi)
+	{
+	  df_bb_delete (bb_index);
+	}
 
       /* This may be a mistake, but if an explicit blocks is passed in
          and the set of blocks to analyze has been explicitly set, add
@@ -878,8 +885,10 @@ df_insn_create_insn_record (struct dataf
   struct df *df = dflow->df;
   struct df_scan_problem_data *problem_data
     = (struct df_scan_problem_data *) dflow->problem_data;
+  struct df_insn_info *insn_rec;
 
-  struct df_insn_info *insn_rec = DF_INSN_GET (df, insn);
+  df_grow_insn_info (df);
+  insn_rec = DF_INSN_GET (df, insn);
   if (!insn_rec)
     {
       insn_rec = pool_alloc (problem_data->insn_pool);
@@ -892,14 +901,20 @@ df_insn_create_insn_record (struct dataf
 /* Delete all of the refs information from INSN.  */
 
 void 
-df_insn_refs_delete (struct dataflow *dflow, rtx insn)
+df_insn_delete (rtx insn)
 {
-  struct df *df = dflow->df;
+  struct df *df = df_current_instance;
+  struct dataflow *dflow;
   unsigned int uid = INSN_UID (insn);
   struct df_insn_info *insn_info = NULL;
   struct df_ref *ref;
-  struct df_scan_problem_data *problem_data
-    = (struct df_scan_problem_data *) dflow->problem_data;
+  struct df_scan_problem_data *problem_data;
+
+  if (!df)
+    return;
+
+  dflow = df->problems_by_index[DF_SCAN];
+  problem_data = (struct df_scan_problem_data *) dflow->problem_data;
 
   if (uid < DF_INSN_SIZE (df))
     insn_info = DF_INSN_UID_GET (df, uid);
@@ -944,23 +959,32 @@ df_insn_refs_delete (struct dataflow *df
 /* Delete all of the refs information from basic_block with BB_INDEX.  */
 
 void
-df_bb_refs_delete (struct dataflow *dflow, int bb_index)
+df_bb_delete (unsigned int bb_index)
 {
   struct df_ref *def;
   struct df_ref *use;
-
-  struct df_scan_bb_info *bb_info 
-    = df_scan_get_bb_info (dflow, bb_index);
+  struct df *df = df_current_instance;
+  struct dataflow *dflow;
+  struct df_scan_bb_info *bb_info = NULL; 
   rtx insn;
   basic_block bb = BASIC_BLOCK (bb_index);
+
+  if (!df)
+    return;
+
+  dflow = df->problems_by_index[DF_SCAN];
+
   FOR_BB_INSNS (bb, insn)
     {
       if (INSN_P (insn))
 	{
 	  /* Record defs within INSN.  */
-	  df_insn_refs_delete (dflow, insn);
+	  df_insn_delete (insn);
 	}
     }
+
+  if (bb_index < dflow->block_info_size)
+    bb_info = df_scan_get_bb_info (dflow, bb_index);
   
   /* Get rid of any artificial uses or defs.  */
   if (bb_info)
@@ -977,24 +1001,46 @@ df_bb_refs_delete (struct dataflow *dflo
 }
 
 
-/* Delete all of the refs information from BLOCKS.  */
+/* Rescan INSN.  Return TRUE if the rescanning produced any changes.  */
 
-void 
-df_refs_delete (struct dataflow *dflow, bitmap blocks)
+bool 
+df_insn_rescan (rtx insn)
 {
-  bitmap_iterator bi;
-  unsigned int bb_index;
+  struct df *df = df_current_instance;
+  struct dataflow *dflow;
+  bool changed = true;
+  unsigned int uid = INSN_UID (insn);
+  struct df_insn_info *insn_info = NULL;
+  basic_block bb = BLOCK_FOR_INSN (insn);
 
-  EXECUTE_IF_SET_IN_BITMAP (blocks, 0, bb_index, bi)
-    {
-      df_bb_refs_delete (dflow, bb_index);
-    }
+  if (!df)
+    return false;
+
+  dflow = df->problems_by_index[DF_SCAN];
+  df_grow_bb_info (dflow);
+  df_grow_reg_info (dflow);
+
+  /* This is really bad code and will be replaced soon by Seongbae.  */
+
+  if (uid < DF_INSN_SIZE (df))
+    insn_info = DF_INSN_UID_GET (df, uid);
+  if (insn_info)
+    df_insn_delete (insn);
+
+  df_insn_create_insn_record (dflow, insn);
+
+  df_insn_refs_record (dflow, bb, insn); 
+  /* End of really bad code.  */
+
+  if (changed)
+    df_mark_bb_dirty (bb);
+  return changed;
 }
 
 
 
 /* Take build ref table for either the uses or defs from the reg-use
-   or reg-def chains.  */ 
+   or reg-def chains.  */
 
 static void 
 df_reorganize_refs (struct df *df,
@@ -1056,6 +1102,77 @@ df_reorganize_refs (struct df *df,
 }
 
 
+/* Change all of the basic block references in INSN to use the insn's
+   current basic block.  This function is called from routines that move 
+   instructions from one block to another.  */  
+
+void
+df_insn_change_bb (rtx insn)
+{
+  struct df *df = df_current_instance;
+  basic_block new_bb = BLOCK_FOR_INSN (insn);
+  basic_block old_bb = NULL;
+  struct df_insn_info *insn_info;
+  unsigned int uid = INSN_UID (insn);
+  bool changed = false;
+  struct df_ref *ref;
+
+  if (!df)
+    return;
+
+  if (uid < DF_INSN_SIZE (df))
+    insn_info = DF_INSN_UID_GET (df, uid);
+  else 
+    {
+      df_insn_rescan (insn);
+      return;
+    }
+
+  if (!insn_info)
+    {
+      df_insn_rescan (insn);
+      return;
+    }
+
+  for (ref = insn_info->defs; ref; ref = DF_REF_NEXT_REF (ref))
+    if (DF_REF_BB (ref) == new_bb)
+      return;
+    else
+      {
+	old_bb = DF_REF_BB (ref);
+	DF_REF_BB (ref) = new_bb;
+	changed = true;
+      }
+
+  for (ref = insn_info->uses; ref; ref = DF_REF_NEXT_REF (ref))
+    if (DF_REF_BB (ref) == new_bb)
+      return;
+    else
+      {
+	old_bb = DF_REF_BB (ref);
+	DF_REF_BB (ref) = new_bb;
+	changed = true;
+      }
+
+  for (ref = insn_info->eq_uses; ref; ref = DF_REF_NEXT_REF (ref))
+    if (DF_REF_BB (ref) == new_bb)
+      return;
+    else
+      {
+	old_bb = DF_REF_BB (ref);
+	DF_REF_BB (ref) = new_bb;
+	changed = true;
+      }
+
+  if (changed)
+    {
+      if (old_bb)
+	df_mark_bb_dirty (old_bb);
+      df_mark_bb_dirty (new_bb);
+    }
+}
+
+
 /* If the use refs in DF are not organized, reorganize them.  */
 
 void 
@@ -1349,7 +1466,6 @@ df_ref_create_structure (struct dataflow
   DF_REF_CHAIN (this_ref) = NULL;
   DF_REF_TYPE (this_ref) = ref_type;
   DF_REF_FLAGS (this_ref) = ref_flags;
-  DF_REF_DATA (this_ref) = NULL;
   DF_REF_BB (this_ref) = bb;
   DF_REF_NEXT_REF (this_ref) = NULL;
 
Index: df-core.c
===================================================================
--- df-core.c	(revision 118540)
+++ df-core.c	(working copy)
@@ -333,7 +333,7 @@ df_init (enum df_permanent_flags permane
   return df;
 }
 
-/* Add PROBLEM to the DF instance.  */
+/* Add PROBLEM (and any dependent problems) to the DF instance.  */
 
 struct dataflow *
 df_add_problem (struct df *df, struct df_problem *problem)
@@ -341,8 +341,8 @@ df_add_problem (struct df *df, struct df
   struct dataflow *dflow;
 
   /* First try to add the dependent problem. */
-  if (problem->dependent_problem_fun)
-    (problem->dependent_problem_fun) (df);
+  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
@@ -363,6 +363,40 @@ df_add_problem (struct df *df, struct df
 }
 
 
+/* Delete a PROBLEM (and any problems that depend on this problem) to
+   the DF instance.  */
+
+void
+df_remove_problem (struct df *df, struct dataflow *dflow)
+{
+  struct df_problem *problem = dflow->problem;
+  int i;
+
+  gcc_assert (problem->remove_problem_fun);
+  df->problems_by_index[dflow->problem->id] = NULL;
+
+  /* Delete any problems that depended on this problem first.  */
+  for (i = 0; i < df->num_problems_defined; i++)
+    if (df->problems_in_order[i]->problem->dependent_problem == problem)
+      df_remove_problem (df, df->problems_in_order[i]);
+
+  /* Now remove this problem.  */
+  for (i = 0; i < df->num_problems_defined; i++)
+    if (df->problems_in_order[i] == dflow)
+      {
+	int j;
+	for (j = i + 1; j < df->num_problems_defined; j++)
+	  df->problems_in_order[j-1] = df->problems_in_order[j];
+	df->problems_in_order[j] = NULL;
+	df->num_problems_defined--;
+	break;
+      }
+
+  (problem->remove_problem_fun) (dflow);
+  free (dflow);
+}
+
+
 /* Set the MASK flags in the DFLOW problem.  The old flags are
    returned.  If a flag is not allowed to be changed this will fail if
    checking is enabled.  */
@@ -416,9 +450,12 @@ df_set_blocks (struct df *df, bitmap blo
 		      basic_block bb = BASIC_BLOCK (bb_index);
 		      if (bb)
 			{
-			  dflow->problem->free_bb_fun
-			    (dflow, bb, df_get_bb_info (dflow, bb_index));
-			  df_set_bb_info (dflow, bb_index, NULL); 
+			  void *bb_info = df_get_bb_info (dflow, bb_index);
+			  if (bb_info)
+			    {
+			      dflow->problem->free_bb_fun (dflow, bb, bb_info);
+			      df_set_bb_info (dflow, bb_index, NULL);
+			    }
 			}
 		    }
 		}
@@ -475,19 +512,26 @@ df_set_blocks (struct df *df, bitmap blo
    problem will be reanalyzed.  */
 
 void
-df_delete_basic_block (struct df *df, int bb_index)
+df_delete_basic_block (int bb_index)
 {
+  struct df *df = df_current_instance;
   basic_block bb = BASIC_BLOCK (bb_index);
   int i;
+
+  if (!df)
+    return;
   
   for (i = 0; i < df->num_problems_defined; i++)
     {
       struct dataflow *dflow = df->problems_in_order[i];
       if (dflow->problem->free_bb_fun)
 	{
-	  dflow->problem->free_bb_fun 
-	    (dflow, bb, df_get_bb_info (dflow, bb_index)); 
-	  df_set_bb_info (dflow, bb_index, NULL);
+	  void *bb_info = df_get_bb_info (dflow, bb_index);
+	  if (bb_info)
+	    {
+	      dflow->problem->free_bb_fun (dflow, bb, bb_info); 
+	      df_set_bb_info (dflow, bb_index, NULL);
+	    }
 	}
     }
 }
@@ -916,6 +960,10 @@ df_simple_iterative_dataflow (enum df_fl
 static void *
 df_get_bb_info (struct dataflow *dflow, unsigned int index)
 {
+  if (dflow->block_info == NULL)
+    return NULL;
+  if (index >= dflow->block_info_size)
+    return NULL;
   return (struct df_scan_bb_info *) dflow->block_info[index];
 }
 
@@ -926,9 +974,170 @@ static void
 df_set_bb_info (struct dataflow *dflow, unsigned int index, 
 		void *bb_info)
 {
+  gcc_assert (dflow->block_info);
   dflow->block_info[index] = bb_info;
 }
 
+
+/* Mark the solutions as being out of date.  */
+
+void 
+df_mark_solutions_dirty (struct df *df)
+{
+  df->solutions_dirty = true;
+}
+
+
+/* Mark BB as needing it's transfer functions as being out of
+   date.  */
+
+void 
+df_mark_bb_dirty (basic_block bb)
+{
+  struct df *df = df_current_instance;
+
+  df_mark_solutions_dirty (df);
+  bitmap_set_bit (df->out_of_date_transfer_functions, bb->index);
+}
+
+
+/* Called from the rtl_compact_blocks to reorganize the problems basic
+   block info.  */
+
+void 
+df_compact_blocks (void)
+{
+  struct df *df = df_current_instance;
+  int i, p;
+  basic_block bb;
+  void **problem_temps;
+  int size = last_basic_block *sizeof (void *);
+  bitmap tmp = BITMAP_ALLOC (NULL);
+  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++)
+	    {
+	      basic_block bb = BASIC_BLOCK (i); 
+	      if (problem_temps[i] && bb)
+		dflow->problem->free_bb_fun
+		  (dflow, bb, problem_temps[i]);
+	    }
+	}
+    }
+
+  /* Shuffle the bits in the basic_block indexed arrays.  */
+
+  if (df->blocks_to_scan)
+    {
+      bitmap_copy (tmp, df->blocks_to_scan);
+      bitmap_clear (df->blocks_to_scan);
+      i = NUM_FIXED_BLOCKS;
+      FOR_EACH_BB (bb) 
+	{
+	  if (bitmap_bit_p (tmp, bb->index))
+	    bitmap_set_bit (df->blocks_to_scan, i);
+	  i++;
+	}
+    }
+
+  bitmap_copy (tmp, df->out_of_date_transfer_functions);
+  bitmap_clear (df->out_of_date_transfer_functions);
+  i = NUM_FIXED_BLOCKS;
+  FOR_EACH_BB (bb) 
+    {
+      if (bitmap_bit_p (tmp, bb->index))
+	bitmap_set_bit (df->out_of_date_transfer_functions, i);
+      i++;
+    }
+
+  if (df->blocks_to_analyze)
+    {
+      bitmap_copy (tmp, df->blocks_to_analyze);
+      bitmap_clear (df->blocks_to_analyze);
+      i = NUM_FIXED_BLOCKS;
+      FOR_EACH_BB (bb) 
+	{
+	  if (bitmap_bit_p (tmp, bb->index))
+	    bitmap_set_bit (df->blocks_to_analyze, i);
+	  i++;
+	}
+    }
+
+  BITMAP_FREE (tmp);
+
+  free (problem_temps);
+
+  i = NUM_FIXED_BLOCKS;
+  FOR_EACH_BB (bb) 
+    {
+      SET_BASIC_BLOCK (i, bb);
+      bb->index = i;
+      i++;
+    }
+
+  gcc_assert (i == n_basic_blocks);
+
+  for (; i < last_basic_block; i++)
+    SET_BASIC_BLOCK (i, NULL);
+}
+
+
+/* Shove NEW_BLOCK in at OLD_INDEX.  Called from ifcvt to hack a
+   block.  There is no excuse for people to do this kind of thing.  */
+
+void 
+df_bb_replace (int old_index, basic_block new_block)
+{
+  struct df *df = df_current_instance;
+  int p;
+  gcc_assert (df);
+
+  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);
+	}
+    }
+
+  SET_BASIC_BLOCK (old_index, new_block);
+  new_block->index = old_index;
+}
+
+
 /*----------------------------------------------------------------------------
    PUBLIC INTERFACES TO QUERY INFORMATION.
 ----------------------------------------------------------------------------*/
Index: df.h
===================================================================
--- df.h	(revision 118540)
+++ df.h	(working copy)
@@ -182,16 +182,17 @@ typedef void (*df_finalizer_function) (s
 /* Function to free all of the problem specific datastructures.  */
 typedef void (*df_free_function) (struct dataflow *);
 
+/* Function to remove this problem from the stack of dataflow problems
+   without effecting the other problems in the stack except for those
+   that depend on this problem.  */
+typedef void (*df_remove_problem_function) (struct dataflow *);
+
 /* Function to dump basic block independent results to FILE.  */
 typedef void (*df_dump_problem_function) (struct dataflow *, FILE *);
 
 /* Function to dump top or bottom of basic block results to FILE.  */
 typedef void (*df_dump_bb_problem_function) (struct dataflow *, basic_block, FILE *);
 
-/* Function to add problem a dataflow problem that must be solved
-   before this problem can be solved.  */
-typedef struct dataflow * (*df_dependent_problem_function) (struct df *);
-
 /* The static description of a dataflow problem to solve.  See above
    typedefs for doc for the function fields.  */
 
@@ -211,10 +212,11 @@ struct df_problem {
   df_transfer_function trans_fun;
   df_finalizer_function finalize_fun;
   df_free_function free_fun;
+  df_remove_problem_function remove_problem_fun;
   df_dump_problem_function dump_start_fun;
   df_dump_bb_problem_function dump_top_fun;
   df_dump_bb_problem_function dump_bottom_fun;
-  df_dependent_problem_function dependent_problem_fun;
+  struct df_problem *dependent_problem;
 };
 
 
@@ -303,7 +305,6 @@ struct df_ref
   /* 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.  */
 };
 
 /* These links are used for two purposes:
@@ -366,6 +367,7 @@ struct df_reg_info
   unsigned int n_refs;
 };
 
+
 /*----------------------------------------------------------------------------
    Problem data for the scanning dataflow problem.  Unlike the other
    dataflow problems, the problem data for scanning is fully exposed and
@@ -397,6 +399,13 @@ struct df
      for analysis.  */ 
   bitmap blocks_to_analyze;
 
+  /* The set of blocks whose transfer functions are out of date.  */
+  bitmap out_of_date_transfer_functions;
+
+  /* True if the something has changed which invalidates the dataflow
+     solutions.  */
+  bool solutions_dirty;
+
   /* 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.  */
@@ -485,7 +494,6 @@ struct df
 #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.  */
 
@@ -667,10 +675,11 @@ extern struct df *df_current_instance;
 
 extern struct df *df_init (enum df_permanent_flags, enum df_changeable_flags);
 extern struct dataflow *df_add_problem (struct df *, struct df_problem *);
+extern void df_remove_problem (struct df *, struct dataflow *);
 extern enum df_changeable_flags df_set_flags (struct df *, enum df_changeable_flags);
 extern enum df_changeable_flags df_clear_flags (struct df *, enum df_changeable_flags);
 extern void df_set_blocks (struct df*, bitmap);
-extern void df_delete_basic_block (struct df *, int);
+extern void df_delete_basic_block (int);
 extern void df_finish1 (struct df *);
 extern void df_analyze_problem (struct dataflow *, bitmap, bitmap, bitmap, int *, int, bool);
 extern void df_analyze (struct df *);
@@ -679,6 +688,10 @@ extern int *df_get_postorder (struct df 
 extern void df_simple_iterative_dataflow (enum df_flow_dir, df_init_function,
 					  df_confluence_function_0, df_confluence_function_n,
 					  df_transfer_function, bitmap, int *, int);
+extern void df_mark_solutions_dirty (struct df *);
+extern void df_mark_bb_dirty (basic_block);
+extern void df_compact_blocks (void);
+extern void df_bb_replace (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);
@@ -753,12 +766,13 @@ extern void df_reg_chain_create (struct 
 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_create_insn_record (struct dataflow *, rtx);
-extern void df_insn_refs_delete (struct dataflow *, rtx);
-extern void df_bb_refs_delete (struct dataflow *, int);
-extern void df_refs_delete (struct dataflow *, bitmap);
+extern void df_insn_delete (rtx);
+extern void df_bb_delete (unsigned int);
+extern bool df_insn_rescan (rtx);
 extern void df_insn_refs_record (struct dataflow *, basic_block, rtx);
 extern bool df_has_eh_preds (basic_block);
 extern void df_recompute_luids (struct df *, basic_block);
+extern void df_insn_change_bb (rtx);
 extern void df_maybe_reorganize_use_refs (struct df *);
 extern void df_maybe_reorganize_def_refs (struct df *);
 extern void df_hard_reg_init (void);
Index: df-problems.c
===================================================================
--- df-problems.c	(revision 118540)
+++ df-problems.c	(working copy)
@@ -59,86 +59,6 @@ static bitmap seen_in_insn = NULL;
 /*----------------------------------------------------------------------------
    Public functions access functions for the dataflow problems.
 ----------------------------------------------------------------------------*/
-
-/* 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.  */
 
@@ -841,6 +761,7 @@ static struct df_problem problem_RU =
   df_ru_transfer_function,    /* Transfer function.  */
   NULL,                       /* Finalize function.  */
   df_ru_free,                 /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   df_ru_start_dump,           /* Debugging.  */
   df_ru_top_dump,             /* Debugging start block.  */
   df_ru_bottom_dump,          /* Debugging end block.  */
@@ -1391,6 +1312,7 @@ static struct df_problem problem_RD =
   df_rd_transfer_function,    /* Transfer function.  */
   NULL,                       /* Finalize function.  */
   df_rd_free,                 /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   df_rd_start_dump,           /* Debugging.  */
   df_rd_top_dump,             /* Debugging start block.  */
   df_rd_bottom_dump,          /* Debugging end block.  */
@@ -1924,6 +1846,7 @@ static struct df_problem problem_LR =
   df_lr_transfer_function,    /* Transfer function.  */
   df_lr_local_finalize,       /* Finalize function.  */
   df_lr_free,                 /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   NULL,                       /* Debugging.  */
   df_lr_top_dump,             /* Debugging start block.  */
   df_lr_bottom_dump,          /* Debugging end block.  */
@@ -2246,10 +2169,11 @@ static struct df_problem problem_UR =
   df_ur_transfer_function,    /* Transfer function.  */
   NULL,                       /* Finalize function.  */
   df_ur_free,                 /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   NULL,                       /* Debugging.  */
   df_ur_top_dump,             /* Debugging start block.  */
   df_ur_bottom_dump,          /* Debugging end block.  */
-  df_lr_add_problem           /* Dependent problem.  */
+  &problem_LR                 /* Dependent problem.  */
 };
 
 
@@ -2440,10 +2364,11 @@ static struct df_problem problem_LIVE =
   NULL,                       /* Transfer function.  */
   df_live_local_finalize,     /* Finalize function.  */
   df_live_free,               /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   NULL,                       /* Debugging.  */
   df_live_top_dump,           /* Debugging start block.  */
   df_live_bottom_dump,        /* Debugging end block.  */
-  df_ur_add_problem           /* Dependent problem.  */
+  &problem_UR                 /* Dependent problem.  */
 };
 
 
@@ -3076,10 +3001,11 @@ static struct df_problem problem_UREC =
   df_urec_transfer_function,  /* Transfer function.  */
   df_urec_local_finalize,     /* Finalize function.  */
   df_urec_free,               /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   NULL,                       /* Debugging.  */
   df_urec_top_dump,           /* Debugging start block.  */
   df_urec_bottom_dump,        /* Debugging end block.  */
-  df_lr_add_problem           /* Dependent problem.  */
+  &problem_LR                 /* Dependent problem.  */
 };
 
 
@@ -3106,6 +3032,82 @@ df_urec_add_problem (struct df *df)
    the reaching defs information (the dependent problem).
 ----------------------------------------------------------------------------*/
 
+
+
+/* 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;
+	    }
+	}
+      DF_REF_CHAIN (ref) = NULL;
+      pool_free (dflow->block_pool, link);
+    }
+  else
+    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;
+    }
+}
+
+
 /* Create def-use or use-def chains.  */
 
 static void  
@@ -3416,6 +3418,23 @@ df_chain_finalize (struct dataflow *dflo
 }
 
 
+/* Remove this problem from the stack of dataflow problems.  */
+
+static void
+df_chain_remove_problem (struct dataflow *dflow)
+{
+  basic_block bb;
+
+  FOR_ALL_BB (bb)
+    {
+      df_chain_bb_reset (dflow, bb->index);
+    }
+
+  free_alloc_pool (dflow->block_pool);
+  dflow->block_pool = NULL;
+}
+
+
 /* Free all storage associated with the problem.  */
 
 static void
@@ -3501,10 +3520,11 @@ static struct df_problem problem_CHAIN =
   NULL,                       /* Transfer function.  */
   df_chain_finalize,          /* Finalize function.  */
   df_chain_free,              /* Free all of the problem information.  */
+  df_chain_remove_problem,    /* Remove this problem from the stack of dataflow problems.  */
   df_chain_start_dump,        /* Debugging.  */
   NULL,                       /* Debugging start block.  */
   NULL,                       /* Debugging end block.  */
-  df_rd_add_problem           /* Dependent problem.  */
+  &problem_RD                 /* Dependent problem.  */
 };
 
 
@@ -4241,6 +4261,7 @@ static struct df_problem problem_RI =
   NULL,                       /* Transfer function.  */
   NULL,                       /* Finalize function.  */
   df_ri_free,                 /* Free all of the problem information.  */
+  NULL,                       /* Remove this problem from the stack of dataflow problems.  */
   df_ri_start_dump,           /* Debugging.  */
   NULL,                       /* Debugging start block.  */
   NULL,                       /* Debugging end block.  */
@@ -4248,7 +4269,7 @@ static struct df_problem problem_RI =
   /* Technically this is only dependent on the live registers problem
      but it will produce information if built one of uninitialized
      register problems (UR, UREC) is also run.  */
-  df_lr_add_problem           /* Dependent problem.  */
+  &problem_LR                 /* Dependent problem.  */
 };
 
 

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]