Re: Invalid shortcut in calculate_global_regs_live

[Bernd Schmidt <bernds at redhat dot com>]

On Thu, 23 Nov 2000, Richard Henderson wrote:

> On Thu, Nov 23, 2000 at 06:45:17PM +0000, Bernd Schmidt wrote:
> > After the second iteration, reg 1 also becomes live at the start of block B.
> > However, now we do not recognize a change in global_live_at_end of block A:
> > the set is unchanged, so we find no reason to rescan.  This is incorrect; the
> > register must now be marked as live at the start of A.
> 
> Ah yes, this explanation I follow.  Tricky.
> 
> I think it's clear we need to track the set of registers that are
> locally conditionally set as well.  We then rescan the block if
> any of these registers are live_at_end, regardless of observed
> change in liveness.
> 
> We still terminate because we do nothing when we find the set of
> live_at_start has not changed.
> 
> Given the expense of a forced rescan, it would probably be worth
> the effort to compute the set of registers that are _only_ ever
> conditionally set, and never unconditionally set.  This would seem
> to require two new regsets during propagate_block.

Why two?  The patch below only uses one (it changes the meaning of the
local_set regset and adds a new cond_local_set regset that only holds
the registers that are never unconditionally set).

> I also recommend removing local_set from struct basic_block, and
> having compute_global_regs_live put a structure in bb->aux just
> like other passes do.

That's an unrelated cleanup which I'll do eventually.

I've applied the patch below, which bootstraps on i686-linux and ia64-linux.
However, the ia64-linux bootstrap fails with an apparently unrelated problem
(it also fails for a clean tree) while building libstdc++-v3.  Unfortunately
I no longer have the original testcase to verify the bug is fixed (but since
it was a preprocessed version of insn-recog.c, I suppose the bootstrap would
have shown the problem).


Bernd

	* flow.c (entry_exit_blocks): Add entry for cond_local_set.
	(struct propagate_block_info): Add new member cond_local_set.
	(propagate_block): Accept new arg cond_local_set.  All callers
	changed.
	(init_propagate_block_info): Likewise.
	(calculate_global_regs_live): Allocate & free cond_local_set.  Always
	rescan if there's overlap between cond_local_set and new_live_at_end.
	(mark_set_1): Set bits either in cond_local_set or local_set, as
	appropriate.
	* basic-block.h (struct basic_block_def): New field cond_local_set.
	(propagate_block, init_propagate_block_info): Update prototypes.

Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.352
diff -u -p -r1.352 flow.c
--- flow.c	2000/11/24 23:45:08	1.352
+++ flow.c	2000/11/27 16:42:29
@@ -193,6 +193,7 @@ struct basic_block_def entry_exit_blocks
     NULL,			/* pred */
     NULL,			/* succ */
     NULL,			/* local_set */
+    NULL,			/* cond_local_set */
     NULL,			/* global_live_at_start */
     NULL,			/* global_live_at_end */
     NULL,			/* aux */
@@ -207,6 +208,7 @@ struct basic_block_def entry_exit_blocks
     NULL,			/* pred */
     NULL,			/* succ */
     NULL,			/* local_set */
+    NULL,			/* cond_local_set */
     NULL,			/* global_live_at_start */
     NULL,			/* global_live_at_end */
     NULL,			/* aux */
@@ -293,9 +295,14 @@ struct propagate_block_info
      elimination.  */
   rtx mem_set_list;
 
-  /* If non-null, record the set of registers set in the basic block.  */
+  /* If non-null, record the set of registers set unconditionally in the
+     basic block.  */
   regset local_set;
 
+  /* If non-null, record the set of registers set conditionally in the
+     basic block.  */
+  regset cond_local_set;
+
 #ifdef HAVE_conditional_execution
   /* Indexed by register number, holds a reg_cond_life_info for each
      register that is not unconditionally live or dead.  */
@@ -1544,7 +1551,7 @@ split_block (bb, insn)
 	 at the end of the original basic block and get
 	 propagate_block to determine which registers are live.  */
       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
-      propagate_block (new_bb, new_bb->global_live_at_start, NULL, 0);
+      propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
       COPY_REG_SET (bb->global_live_at_end, 
 		    new_bb->global_live_at_start);
     }
@@ -2966,7 +2973,7 @@ update_life_info (blocks, extent, prop_f
 	  basic_block bb = BASIC_BLOCK (i);
 
 	  COPY_REG_SET (tmp, bb->global_live_at_end);
-	  propagate_block (bb, tmp, (regset) NULL, prop_flags);
+	  propagate_block (bb, tmp, NULL, NULL, prop_flags);
 
 	  if (extent == UPDATE_LIFE_LOCAL)
 	    verify_local_live_at_start (tmp, bb);
@@ -2979,7 +2986,7 @@ update_life_info (blocks, extent, prop_f
 	  basic_block bb = BASIC_BLOCK (i);
 
 	  COPY_REG_SET (tmp, bb->global_live_at_end);
-	  propagate_block (bb, tmp, (regset) NULL, prop_flags);
+	  propagate_block (bb, tmp, NULL, NULL, prop_flags);
 
 	  if (extent == UPDATE_LIFE_LOCAL)
 	    verify_local_live_at_start (tmp, bb);
@@ -3378,6 +3385,7 @@ calculate_global_regs_live (blocks_in, b
       if (bb->local_set == NULL)
 	{
 	  bb->local_set = OBSTACK_ALLOC_REG_SET (&flow_obstack);
+	  bb->cond_local_set = OBSTACK_ALLOC_REG_SET (&flow_obstack);
 	  rescan = 1;
 	}
       else
@@ -3392,6 +3400,20 @@ calculate_global_regs_live (blocks_in, b
 
 	  if (! rescan)
 	    {
+	      /* If any of the registers in the new live_at_end set are
+		 conditionally set in this basic block, we must rescan.
+	         This is because conditional lifetimes at the end of the
+		 block do not just take the live_at_end set into account,
+		 but also the liveness at the start of each successor
+		 block.  We can miss changes in those sets if we only
+		 compare the new live_at_end against the previous one.  */
+	      CLEAR_REG_SET (tmp);
+	      rescan = bitmap_operation (tmp, new_live_at_end,
+					 bb->cond_local_set, BITMAP_AND);
+	    }
+
+	  if (! rescan)
+	    {
 	      /* Find the set of changed bits.  Take this opportunity
 		 to notice that this set is empty and early out.  */
 	      CLEAR_REG_SET (tmp);
@@ -3434,7 +3456,8 @@ calculate_global_regs_live (blocks_in, b
 
 	  /* Rescan the block insn by insn to turn (a copy of) live_at_end
 	     into live_at_start.  */
-	  propagate_block (bb, new_live_at_end, bb->local_set, flags);
+	  propagate_block (bb, new_live_at_end, bb->local_set,
+			   bb->cond_local_set, flags);
 
 	  /* If live_at start didn't change, no need to go farther.  */
 	  if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
@@ -3467,6 +3490,7 @@ calculate_global_regs_live (blocks_in, b
 	{
 	  basic_block bb = BASIC_BLOCK (i);
 	  FREE_REG_SET (bb->local_set);
+	  FREE_REG_SET (bb->cond_local_set);
 	});
     }
   else
@@ -3475,6 +3499,7 @@ calculate_global_regs_live (blocks_in, b
 	{
 	  basic_block bb = BASIC_BLOCK (i);
 	  FREE_REG_SET (bb->local_set);
+	  FREE_REG_SET (bb->cond_local_set);
 	}
     }
 
@@ -3811,10 +3836,9 @@ propagate_one_insn (pbi, insn)
    the user can use the regsets provided here.  */
 
 struct propagate_block_info *
-init_propagate_block_info (bb, live, local_set, flags)
+init_propagate_block_info (bb, live, local_set, cond_local_set, flags)
      basic_block bb;
-     regset live;
-     regset local_set;
+     regset live, local_set, cond_local_set;
      int flags;
 {
   struct propagate_block_info *pbi = xmalloc (sizeof (*pbi));
@@ -3823,6 +3847,7 @@ init_propagate_block_info (bb, live, loc
   pbi->reg_live = live;
   pbi->mem_set_list = NULL_RTX;
   pbi->local_set = local_set;
+  pbi->cond_local_set = cond_local_set;
   pbi->cc0_live = 0;
   pbi->flags = flags;
 
@@ -4000,20 +4025,28 @@ free_propagate_block_info (pbi)
    When called, REG_LIVE contains those live at the end.  On return, it
    contains those live at the beginning.
 
-   LOCAL_SET, if non-null, will be set with all registers killed by
-   this basic block.  */
+   LOCAL_SET, if non-null, will be set with all registers killed
+   unconditionally by this basic block.
+   Likewise, COND_LOCAL_SET, if non-null, will be set with all registers
+   killed conditionally by this basic block.  If there is any unconditional
+   set of a register, then the corresponding bit will be set in LOCAL_SET
+   and cleared in COND_LOCAL_SET.
+   It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set.  In this
+   case, the resulting set will be equal to the union of the two sets that
+   would otherwise be computed.  */
 
 void
-propagate_block (bb, live, local_set, flags)
+propagate_block (bb, live, local_set, cond_local_set, flags)
      basic_block bb;
      regset live;
      regset local_set;
+     regset cond_local_set;
      int flags;
 {
   struct propagate_block_info *pbi;
   rtx insn, prev;
 
-  pbi = init_propagate_block_info (bb, live, local_set, flags);
+  pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags);
 
   if (flags & PROP_REG_INFO)
     {
@@ -4635,7 +4668,16 @@ mark_set_1 (pbi, code, reg, cond, insn, 
 	{
 	  int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
 	  if (pbi->local_set)
-	    SET_REGNO_REG_SET (pbi->local_set, i);
+	    {
+	      /* Order of the set operation matters here since both
+		 sets may be the same.  */
+	      CLEAR_REGNO_REG_SET (pbi->cond_local_set, i);
+	      if (cond != NULL_RTX
+		  && ! REGNO_REG_SET_P (pbi->local_set, i))
+		SET_REGNO_REG_SET (pbi->cond_local_set, i);
+	      else
+		SET_REGNO_REG_SET (pbi->local_set, i);
+	    }
 	  if (code != CLOBBER)
 	    SET_REGNO_REG_SET (pbi->new_set, i);
 
Index: recog.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/recog.c,v
retrieving revision 1.85
diff -u -p -r1.85 recog.c
--- recog.c	2000/11/10 00:07:52	1.85
+++ recog.c	2000/11/27 16:42:30
@@ -3053,9 +3053,9 @@ peephole2_optimize (dump_file)
       COPY_REG_SET (peep2_insn_data[MAX_INSNS_PER_PEEP2].live_before, live);
 
 #ifdef HAVE_conditional_execution
-      pbi = init_propagate_block_info (bb, live, NULL, 0);
+      pbi = init_propagate_block_info (bb, live, NULL, NULL, 0);
 #else
-      pbi = init_propagate_block_info (bb, live, NULL, PROP_DEATH_NOTES);
+      pbi = init_propagate_block_info (bb, live, NULL, NULL, PROP_DEATH_NOTES);
 #endif
 
       for (insn = bb->end; ; insn = prev)
Index: ifcvt.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ifcvt.c,v
retrieving revision 1.35
diff -u -p -r1.35 ifcvt.c
--- ifcvt.c	2000/11/14 09:58:40	1.35
+++ ifcvt.c	2000/11/27 16:42:30
@@ -1973,7 +1973,7 @@ dead_or_predicable (test_bb, merge_bb, o
       /* ??? bb->local_set is only valid during calculate_global_regs_live,
 	 so we must recompute usage for MERGE_BB.  Not so bad, I suppose, 
          since we've already asserted that MERGE_BB is small.  */
-      propagate_block (merge_bb, tmp, merge_set, 0);
+      propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
 
       /* For small register class machines, don't lengthen lifetimes of
 	 hard registers before reload.  */
@@ -1993,7 +1993,8 @@ dead_or_predicable (test_bb, merge_bb, o
 	 Moreover, we're interested in the insns live from OTHER_BB.  */
 
       COPY_REG_SET (test_live, other_bb->global_live_at_start);
-      pbi = init_propagate_block_info (test_bb, test_live, test_set, 0);
+      pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
+				       0);
 
       for (insn = jump; ; insn = prev)
 	{
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/basic-block.h,v
retrieving revision 1.81
diff -u -p -r1.81 basic-block.h
--- basic-block.h	2000/11/14 09:58:40	1.81
+++ basic-block.h	2000/11/27 16:42:30
@@ -165,6 +165,7 @@ typedef struct basic_block_def {
      not reflect the use of regs in phi functions, since the liveness
      of these regs may depend on which edge was taken into the block.  */
   regset local_set;
+  regset cond_local_set;
   regset global_live_at_start;
   regset global_live_at_end;
 
@@ -489,12 +490,13 @@ extern void life_analysis	PARAMS ((rtx, 
 extern void update_life_info	PARAMS ((sbitmap, enum update_life_extent,
 					 int));
 extern int count_or_remove_death_notes	PARAMS ((sbitmap, int));
-extern void propagate_block	PARAMS ((basic_block, regset, regset, int));
+extern void propagate_block	PARAMS ((basic_block, regset, regset, regset,
+					 int));
 
 struct propagate_block_info;
 extern rtx propagate_one_insn	PARAMS ((struct propagate_block_info *, rtx));
 extern struct propagate_block_info *init_propagate_block_info
-  PARAMS ((basic_block, regset, regset, int));
+  PARAMS ((basic_block, regset, regset, regset, int));
 extern void free_propagate_block_info PARAMS ((struct propagate_block_info *));
 
 /* In lcm.c */