[dataflow]: PATCH COMMITTED to keep luids up to date.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

This patch changes the way that the kill and gen sets are created for
the ur problem. 
The sets are now computed with a forwards scan of the block.  This is
much faster and has the advantage that the luids for the block can be
updated at the same time almost for free. 

Updating the luid at calls to df_analyze allows us to get rid of many of
the calls to df_recompute_luids and paves the way for some other compile
time improvements by bonzini. 

This has been bootstrapped and tested with no regressions on ia-64,
x86-32, x86-32 and ppc under linux. 

Kenny

2007-02-20  Kenneth Zadeck <zadeck@naturalbridge.com>

    * fwprop.c (forward_propagate_into): Removed call to
    df_recompute_luids.
    * see.c (see_free_data_structures): Ditto.
    * loop-iv.c (iv_analysis_loop_init): Ditto.
    * dce.c (prescan_insns_for_dse): Ditto.
    * auto-inc-dec.c (merge_in_block): Moved call to
    df_recompute_luids so that it only happens on subsequent passes of
    block.
    * df-scan.c (df_grow_insn_info): Made public.
    * df.h (df_grow_insn_info): Made public.
    * df-core.c: Fixed comments.
    * df-problems.c (df_ur_bb_local_compute): Reversed order of
    processing insns.  Removed usage of seen_in_block and
    seen_in_insn.  Update luid.
        (df_ur_local_compute, df_ur_verify_transfer_functions): Added call
    to df_grow_insn_info and deleted calls to df_set_seen, df_unset_seen.

Index: fwprop.c
===================================================================
--- fwprop.c	(revision 122136)
+++ fwprop.c	(working copy)
@@ -917,8 +917,6 @@ forward_propagate_into (struct df_ref *u
 static void
 fwprop_init (void)
 {
-  basic_block bb;
-
   num_changes = 0;
   calculate_dominance_info (CDI_DOMINATORS);
 
@@ -933,8 +931,6 @@ fwprop_init (void)
      put the dataflow solver to work.  */
   df_set_flags (DF_EQ_NOTES);
   df_chain_add_problem (DF_UD_CHAIN);
-  FOR_EACH_BB (bb)
-    df_recompute_luids (bb);
   df_analyze ();
   df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
   df_set_flags (DF_DEFER_INSN_RESCAN);
Index: see.c
===================================================================
--- see.c	(revision 122136)
+++ see.c	(working copy)
@@ -1327,15 +1327,12 @@ see_free_data_structures (void)
 static void
 see_initialize_data_structures (void)
 {
-  basic_block bb;
   unsigned int max_reg = max_reg_num ();
   unsigned int i;
 
   /* Build the df object. */
   df_set_flags (DF_EQ_NOTES);
   df_chain_add_problem (DF_DU_CHAIN + DF_UD_CHAIN);
-  FOR_EACH_BB (bb)
-    df_recompute_luids (bb);
   df_analyze ();
   df_set_flags (DF_DEFER_INSN_RESCAN);
 
Index: loop-iv.c
===================================================================
--- loop-iv.c	(revision 122136)
+++ loop-iv.c	(working copy)
@@ -272,7 +272,6 @@ iv_analysis_loop_init (struct loop *loop
     {
       bb = body[i];
       bitmap_set_bit (blocks, bb->index);
-      df_recompute_luids (bb);
     }
   /* Get rid of the ud chains before processing the rescans.  Then add
      the problem back.  */
Index: dce.c
===================================================================
--- dce.c	(revision 122136)
+++ dce.c	(working copy)
@@ -1705,7 +1705,6 @@ prescan_insns_for_dse (void)
   init_value_store_group (&local_value_stores);
   FOR_EACH_BB (bb)
     {
-      df_recompute_luids (bb);
       cselib_clear_table ();
       cselib_discard_hook = remove_useless_values;
       FOR_BB_INSNS (bb, insn)
Index: auto-inc-dec.c
===================================================================
--- auto-inc-dec.c	(revision 122136)
+++ auto-inc-dec.c	(working copy)
@@ -1379,8 +1379,6 @@ merge_in_block (int max_reg, basic_block
   if (dump_file)
     fprintf (dump_file, "\n\nstarting bb %d\n", bb->index);
 
-  df_recompute_luids (bb);
-
   FOR_BB_INSNS_REVERSE_SAFE (bb, insn, curr)
     {
       unsigned int uid = INSN_UID (insn);
@@ -1496,6 +1494,7 @@ merge_in_block (int max_reg, basic_block
       memset (reg_next_use, 0, max_reg * sizeof(rtx));
       memset (reg_next_inc_use, 0, max_reg * sizeof(rtx));
       memset (reg_next_def, 0, max_reg * sizeof(rtx));
+      df_recompute_luids (bb);
       merge_in_block (max_reg, bb);
     }
 }
Index: df-scan.c
===================================================================
--- df-scan.c	(revision 122136)
+++ df-scan.c	(working copy)
@@ -124,7 +124,6 @@ static void df_record_exit_block_uses (b
 static void df_get_exit_block_use_set (bitmap);
 static void df_get_entry_block_def_set (bitmap);
 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
-static void df_grow_insn_info (void);
 static void df_ref_chain_delete_du_chain (struct df_ref **);
 static void df_ref_chain_delete (struct df_ref **);
 
@@ -551,7 +550,7 @@ df_check_and_grow_ref_info (struct df_re
    number of instructions, grow to 25% more than the number of
    instructions.  */
 
-static void 
+void 
 df_grow_insn_info (void)
 {
   unsigned int new_size = get_max_uid () + 1;
Index: df-core.c
===================================================================
--- df-core.c	(revision 122136)
+++ df-core.c	(working copy)
@@ -285,10 +285,10 @@ ACCESSING INSNS:
    to the ordering of the uses or refs in an instruction.
 
 3) Each insn has a logical uid field (LUID).  When properly set, this
-   is an integer that numbers each insn in the basic block, in order
-   from the start of the block.  The numbers are only correct after a
-   call to df_recompute_luid.  They will rot after insns are added
-   deleted or moved around.
+   is an integer that numbers each insn in the basic block, in order from
+   the start of the block.  The numbers are only correct after a call to
+   df_analyse.  They will rot after insns are added deleted or moved
+   around.
 
 ACCESSING REFS:
 
Index: df.h
===================================================================
--- df.h	(revision 122136)
+++ df.h	(working copy)
@@ -320,9 +320,9 @@ struct df_insn_info
   /* Head of insn-use chain for uses in REG_EQUAL/EQUIV notes.  */
   struct df_ref **eq_uses;       
   struct df_mw_hardreg **mw_hardregs;
-  /* The logical uid of the insn in the basic block.  This is only
-     valid after df_recompute_luids has been run on the basic block
-     containing the insn. */
+  /* The logical uid of the insn in the basic block.  This is valid
+     after any call to df_analyze but may rot after insns are added,
+     deleted or moved. */
   int luid; 
 };
 
@@ -912,6 +912,7 @@ extern void df_scan_alloc (bitmap);
 extern struct df_scan_bb_info *df_scan_get_bb_info (unsigned int);
 extern void df_scan_add_problem (void);
 extern void df_grow_reg_info (void);
+extern void df_grow_insn_info (void);
 extern void df_scan_blocks (void);
 extern struct df_ref *df_ref_create (rtx, rtx *, rtx,basic_block, 
 				     enum df_ref_type, enum df_ref_flags);
Index: df-problems.c
===================================================================
--- df-problems.c	(revision 122136)
+++ df-problems.c	(working copy)
@@ -2246,75 +2246,57 @@ df_ur_bb_local_compute (unsigned int bb_
   struct df_ur_bb_info *bb_info = df_ur_get_bb_info (bb_index);
   rtx insn;
   struct df_ref **def_rec;
-
-  bitmap_clear (seen_in_block);
-  bitmap_clear (seen_in_insn);
+  int luid = 0;
 
   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {
       struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
-	{
-	  unsigned int regno = DF_REF_REGNO (def);
-	  if (!bitmap_bit_p (seen_in_block, regno))
-	    {
-	      bitmap_set_bit (seen_in_block, regno);
-	      bitmap_set_bit (bb_info->gen, regno);
-	    }
-	}
+      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
+	bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
     }
 
-  FOR_BB_INSNS_REVERSE (bb, insn)
+  FOR_BB_INSNS (bb, insn)
     {
       unsigned int uid = INSN_UID (insn);
+      struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
+
+      /* Inserting labels does not always trigger the incremental
+	 rescanning.  */
+      if (!insn_info)
+	{
+	  gcc_assert (!INSN_P (insn));
+	  df_insn_create_insn_record (insn);
+	}
+
+      DF_INSN_LUID (insn) = luid;
       if (!INSN_P (insn))
 	continue;
 
+      luid++;
       for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
 	{
 	  struct df_ref *def = *def_rec;
 	  unsigned int regno = DF_REF_REGNO (def);
-	  /* Only the last def counts.  */
-	  if (!bitmap_bit_p (seen_in_block, regno))
-	    {
-              if (DF_REF_FLAGS_IS_SET (def,
-                                       DF_REF_PARTIAL
-                                       | DF_REF_CONDITIONAL))
-                {
-                  /* All partial or conditional def
-                     seen are included in the gen set. */
-                  bitmap_set_bit (bb_info->gen, regno);
-                }
-              else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
-                {
-		  /* Only must clobbers for the entire reg destroy the
-		     value.  */
-                  bitmap_set_bit (seen_in_insn, regno);
-                  bitmap_set_bit (bb_info->kill, regno);
-		}
-              else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
-		{
-                  bitmap_set_bit (seen_in_insn, regno);
-		  bitmap_set_bit (bb_info->gen, regno);
-                }
-	    }
+
+	  if (DF_REF_FLAGS_IS_SET (def,
+				   DF_REF_PARTIAL | DF_REF_CONDITIONAL))
+	    /* All partial or conditional def
+	       seen are included in the gen set. */
+	    bitmap_set_bit (bb_info->gen, regno);
+	  else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
+	    /* Only must clobbers for the entire reg destroy the
+	       value.  */
+	    bitmap_set_bit (bb_info->kill, regno);
+	  else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
+	    bitmap_set_bit (bb_info->gen, regno);
 	}
-      bitmap_ior_into (seen_in_block, seen_in_insn);
-      bitmap_clear (seen_in_insn);
     }
 
   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {
       struct df_ref *def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-	{
-	  unsigned int regno = DF_REF_REGNO (def);
-	  if (!bitmap_bit_p (seen_in_block, regno))
-	    {
-	      bitmap_set_bit (seen_in_block, regno);
-	      bitmap_set_bit (bb_info->gen, regno);
-	    }
-	}
+      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
+	bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
     }
 }
 
@@ -2327,15 +2309,15 @@ df_ur_local_compute (bitmap all_blocks A
   unsigned int bb_index;
   bitmap_iterator bi;
 
-  df_set_seen ();
+  df_grow_insn_info ();
 
-  EXECUTE_IF_SET_IN_BITMAP (df_ur->out_of_date_transfer_functions, 0, bb_index, bi)
+  EXECUTE_IF_SET_IN_BITMAP (df_ur->out_of_date_transfer_functions, 
+			    0, bb_index, bi)
     {
       df_ur_bb_local_compute (bb_index);
     }
 
   bitmap_clear (df_ur->out_of_date_transfer_functions);
-  df_unset_seen ();
 }
 
 
@@ -2603,7 +2585,7 @@ df_ur_verify_transfer_functions (void)
   saved_kill = BITMAP_ALLOC (NULL);
   all_blocks = BITMAP_ALLOC (NULL);
 
-  df_set_seen ();
+  df_grow_insn_info ();
 
   FOR_ALL_BB (bb)
     {
@@ -2644,8 +2626,6 @@ df_ur_verify_transfer_functions (void)
   /* Make sure there are no dirty bits in blocks that have been deleted.  */
   gcc_assert (!bitmap_intersect_compl_p (df_ur->out_of_date_transfer_functions, 
 					 all_blocks)); 
-  df_unset_seen ();
-
   BITMAP_FREE (saved_gen);
   BITMAP_FREE (saved_kill);
   BITMAP_FREE (all_blocks);