RFA: Fix liveness calculation in caller-save.c

Richard Sandiford rdsandiford@googlemail.com
Sun Jan 11 12:05:00 GMT 2009


This patch fixes a wrong-code bug in gcc.c-torture/execute/20040805-1.c
for MIPS16 code.  The testcase has an instruction:

   I1: (set (reg $2) (plus (reg $2) (reg PSEUDO)))

where PSEUDO is allocated a call-clobbered register.  This register is
on the stack before I1, so caller-save.c inserts a restore before it:

   I2: (set (reg PSEUDO) (mem ADDR))
   I1: (set (reg $2) (plus (reg $2) (reg PSEUDO)))

caller-save.c has to set up the live_throughout and dead_or_set sets
for I2, but it wrongly excludes $2 from the former.  Reload then choses
to use $2 to reload ADDR, thus clobbering the input to I1.

The problem is easy to see.  When inserting a new instruction before
an existing instruction, caller-save.c uses the following code to
calculate the new instruction's live_throughout set:

-----------------------------------------------------------------------------
      /* ??? It would be nice if we could exclude the already / still saved
	 registers from the live sets.  */
      COPY_REG_SET (&new_chain->live_throughout, &chain->live_throughout);
      /* Registers that die in CHAIN->INSN still live in the new insn.
	 Likewise for those which are autoincremented or autodecremented.  */
      for (link = REG_NOTES (chain->insn); link; link = XEXP (link, 1))
	{
	  enum reg_note kind = REG_NOTE_KIND (link);
	  if (kind == REG_DEAD || kind == REG_INC)
	    {
	      rtx reg = XEXP (link, 0);
	      int regno, i;

	      gcc_assert (REG_P (reg));
	      regno = REGNO (reg);
	      if (regno >= FIRST_PSEUDO_REGISTER)
		regno = reg_renumber[regno];
	      if (regno < 0)
		continue;
	      for (i = hard_regno_nregs[regno][GET_MODE (reg)] - 1;
		   i >= 0; i--)
		SET_REGNO_REG_SET (&new_chain->live_throughout, regno + i);
	    }
	}

      /* If CHAIN->INSN is a call, then the registers which contain
	 the arguments to the function are live in the new insn.  */
      if (CALL_P (chain->insn))
	{
	  for (link = CALL_INSN_FUNCTION_USAGE (chain->insn);
	       link != NULL_RTX;
	       link = XEXP (link, 1))
	    {
	      rtx arg = XEXP (link, 0);

	      if (GET_CODE (arg) == USE)
		{
		  rtx reg = XEXP (arg, 0);

		  if (REG_P (reg))
		    {
		      int i, regno = REGNO (reg);

		      /* Registers in CALL_INSN_FUNCTION_USAGE are always
			 hard registers.  */
		      gcc_assert (regno < FIRST_PSEUDO_REGISTER);

		      for (i = hard_regno_nregs[regno][GET_MODE (reg)] - 1;
			   i >= 0; i--)
			SET_REGNO_REG_SET (&new_chain->live_throughout, regno + i);
		    }
		}
	    }
	}
-----------------------------------------------------------------------------

But REG_DEAD notes are not needed if a register is both set and used
in an instruction (and they haven't been needed for some time):

-----------------------------------------------------------------------------
/* The value in REG dies in this insn (i.e., it is not needed past
   this insn).  If REG is set in this insn, the REG_DEAD note may,
   but need not, be omitted.  */
REG_NOTE (DEAD)
-----------------------------------------------------------------------------

And if chain->insn sets a register, that register is rightly excluded
from chain->live_throughout, so a used-and-set register never gets added
to new_chain->live_throughout.

The patch below fixes this by using note_uses instead.  We can do this
for both the instruction's pattern and its CALL_INSN_FUNCTION_USAGE.


I do not like this patch.  It looks like both the before_p and !before_p
blocks in caller-save.c:insert_one_insn are trying to recalculate liveness
information that we had previously (in global.c:build_insn_chain), but using
a different algorithm.  That doesn't seem like a good idea.  The same
could be said of the "note_stores (..., mark_set_regs, ...)" calls in
setup_save_areas and save_call_clobbered_regs.

Those objections account for all the routines in caller-save.c that
use this liveness information (although it doesn't account for all
the uses of the information within those routines).  The only other
consumer of this information is reload1.c:find_reload_reg and its
subroutines.  Those routines always want the _union_ of live_throughout
and dead_or_set (i.e. they want a conflict set).  In some cases they
need a special regset simply to avoid double-counting an instruction
that's in both sets.

All in all, I'm not convinced we have the best choice of liveness
sets here, so I suspect the proper fix would be to replace them
with something else.  We obviously can't do that at this stage of
development though.  We'd also have to be careful not to store too
much information in what is a per-instruction data structure.

I hope the patch is at least an incremental improvement on what
we have now.

Tested on mips64el-linux-gnu, where it fixes 20040805-1.c.
OK to install?

Richard


gcc/
	* caller-save.c (add_used_regs_1, add_used_regs): New functions.
	(insert_one_insn): Use them instead of REG_DEAD and REG_INC notes.
	Also use them when walking CALL_INSN_FUNCTION_USAGE.

Index: gcc/caller-save.c
===================================================================
--- gcc/caller-save.c	2009-01-10 12:35:10.000000000 +0000
+++ gcc/caller-save.c	2009-01-10 16:59:06.000000000 +0000
@@ -1179,6 +1179,39 @@ insert_save (struct insn_chain *chain, i
   return numregs - 1;
 }
 
+/* A for_each_rtx callback used by add_used_regs.  Add the hard-register
+   equivalent of each REG to regset DATA.  */
+
+static int
+add_used_regs_1 (rtx *loc, void *data)
+{
+  int regno, i;
+  regset live;
+  rtx x;
+
+  x = *loc;
+  live = (regset) data;
+  if (REG_P (x))
+    {
+      regno = REGNO (x);
+      if (!HARD_REGISTER_NUM_P (regno))
+	regno = reg_renumber[regno];
+      if (regno >= 0)
+	for (i = hard_regno_nregs[regno][GET_MODE (x)]; i-- > 0; )
+	  SET_REGNO_REG_SET (live, regno + i);
+    }
+  return 0;
+}
+
+/* A note_uses callback used by insert_one_insn.  Add the hard-register
+   equivalent of each REG to regset DATA.  */
+
+static void
+add_used_regs (rtx *loc, void *data)
+{
+  for_each_rtx (loc, add_used_regs_1, data);
+}
+
 /* Emit a new caller-save insn and set the code.  */
 static struct insn_chain *
 insert_one_insn (struct insn_chain *chain, int before_p, int code, rtx pat)
@@ -1216,58 +1249,16 @@ insert_one_insn (struct insn_chain *chai
       /* ??? It would be nice if we could exclude the already / still saved
 	 registers from the live sets.  */
       COPY_REG_SET (&new_chain->live_throughout, &chain->live_throughout);
-      /* Registers that die in CHAIN->INSN still live in the new insn.
-	 Likewise for those which are autoincremented or autodecremented.  */
-      for (link = REG_NOTES (chain->insn); link; link = XEXP (link, 1))
-	{
-	  enum reg_note kind = REG_NOTE_KIND (link);
-	  if (kind == REG_DEAD || kind == REG_INC)
-	    {
-	      rtx reg = XEXP (link, 0);
-	      int regno, i;
-
-	      gcc_assert (REG_P (reg));
-	      regno = REGNO (reg);
-	      if (regno >= FIRST_PSEUDO_REGISTER)
-		regno = reg_renumber[regno];
-	      if (regno < 0)
-		continue;
-	      for (i = hard_regno_nregs[regno][GET_MODE (reg)] - 1;
-		   i >= 0; i--)
-		SET_REGNO_REG_SET (&new_chain->live_throughout, regno + i);
-	    }
-	}
-
+      note_uses (&PATTERN (chain->insn), add_used_regs,
+		 &new_chain->live_throughout);
       /* If CHAIN->INSN is a call, then the registers which contain
 	 the arguments to the function are live in the new insn.  */
       if (CALL_P (chain->insn))
-	{
-	  for (link = CALL_INSN_FUNCTION_USAGE (chain->insn);
-	       link != NULL_RTX;
-	       link = XEXP (link, 1))
-	    {
-	      rtx arg = XEXP (link, 0);
-
-	      if (GET_CODE (arg) == USE)
-		{
-		  rtx reg = XEXP (arg, 0);
-
-		  if (REG_P (reg))
-		    {
-		      int i, regno = REGNO (reg);
-
-		      /* Registers in CALL_INSN_FUNCTION_USAGE are always
-			 hard registers.  */
-		      gcc_assert (regno < FIRST_PSEUDO_REGISTER);
-
-		      for (i = hard_regno_nregs[regno][GET_MODE (reg)] - 1;
-			   i >= 0; i--)
-			SET_REGNO_REG_SET (&new_chain->live_throughout, regno + i);
-		    }
-		}
-	    }
-	  
-	}
+	for (link = CALL_INSN_FUNCTION_USAGE (chain->insn);
+	     link != NULL_RTX;
+	     link = XEXP (link, 1))
+	  note_uses (&XEXP (link, 0), add_used_regs,
+		     &new_chain->live_throughout);
 
       CLEAR_REG_SET (&new_chain->dead_or_set);
       if (chain->insn == BB_HEAD (BASIC_BLOCK (chain->block)))



More information about the Gcc-patches mailing list