Load hoisting bug

Load hoisting bug

[David Edelsohn]

	We have not had enough fun with loop optimizations lately, so I
found one...

	The divconst-3.c regression on AIX which appeared at the beginning
of November is due to GCC miscompiling itself.  The miscompilation is
caused by a loop optimization which was not safe.

Prior to loop optimization:

(note 47 177 53 NOTE_INSN_LOOP_BEG)

(insn 68 66 69 (set (reg:SI 4 r4)
        (subreg:SI (reg/v:DI 119) 4)) 289 {*movsi_internal1} (nil)
    (nil))

(insn 69 68 71 (parallel[ 
            (set (reg:DI 3 r3)
                (mult:DI (sign_extend:DI (reg:SI 3 r3))
                    (sign_extend:DI (reg:SI 4 r4))))
            (clobber (scratch:SI))
            (clobber (reg:SI 0 r0))
        ] ) 76 {mull_call} (nil)
    (nil))

After loop optimization:

Insn 68: regno 4 (life 1), savings 1  moved to 178

(insn 178 177 179 (set (reg:SI 4 r4)
        (subreg:SI (reg/v:DI 119) 4)) -1 (nil)
    (nil))

(note 47 205 202 NOTE_INSN_LOOP_BEG)

(insn 69 66 71 (parallel[ 
            (set (reg:DI 3 r3)
                (mult:DI (sign_extend:DI (reg:SI 3 r3))
                    (sign_extend:DI (reg:SI 4 r4))))
            (clobber (scratch:SI))
            (clobber (reg:SI 0 r0))
        ] ) -1 (nil)
    (nil))


scan_loop() decides that it can move the SET of r4 out of the loop,
placing it on the move_movables list.

	The register only is used within the loop (prior to register
allocation).  loop_invariant_p() returns true which seems incorrect to me.
The value is invariant, but the register is not invariant.

(set (reg:DI 3) ...) uses the register pair r3 and r4 on a 32-bit target!
The instruction clobbers r3, so it needs to be restored on each iteration
(as gcc-3.0 correctly performed), but the mainline now is hoisting the
load out of the loop although the register is modified in the loop.  The
loop information array has r4 listed as set_in_loop=1.

	Is GCC getting confused by the use of a hard register?  Is GCC
getting confused because of DImode?  The pattern could explicitly clobber
r4, but GCC should know that DImode requires a pair of GPRs.

	I still am trying to figure out the origin of the problem.  Any
guidance would be appreciated.

Thanks, David

Re: Load hoisting bug

[law]

  > 	We have not had enough fun with loop optimizations lately, so I
  > found one...
  > 
  > 	The divconst-3.c regression on AIX which appeared at the beginning
  > of November is due to GCC miscompiling itself.  The miscompilation is
  > caused by a loop optimization which was not safe.
[ ... ]
Note that the handling of hard registers in loops changed in early November.
I believe this is the patch:

        * loop.c (loop_regs_scan):  Don't invalidate PIC register.

You might try without that patch and see if this problem goes away.
jeff

Re: Load hoisting bug

[Richard Henderson]

On Fri, Dec 07, 2001 at 07:00:56PM -0500, David Edelsohn wrote:
> (set (reg:DI 3) ...) uses the register pair r3 and r4 on a 32-bit target!

Blah.  Gimme a preprocessed file and I'll look at it.


r~

Re: Load hoisting bug

[Richard Henderson]

On Fri, Dec 07, 2001 at 05:16:28PM -0700, law@redhat.com wrote:
>   > 	We have not had enough fun with loop optimizations lately, so I
>   > found one...
>   > 
>   > 	The divconst-3.c regression on AIX which appeared at the beginning
>   > of November is due to GCC miscompiling itself.  The miscompilation is
>   > caused by a loop optimization which was not safe.
> [ ... ]
> Note that the handling of hard registers in loops changed in early November.
> I believe this is the patch:
> 
>         * loop.c (loop_regs_scan):  Don't invalidate PIC register.
> 
> You might try without that patch and see if this problem goes away.

It will go away.  The problem is almost certainly the DImode.
There's a missing HARD_REGNO_NREGS somewhere in the loop code.


r~

Re: Load hoisting bug

[David Edelsohn]

>>>>> Richard Henderson writes:

Richard> It will go away.  The problem is almost certainly the DImode.
Richard> There's a missing HARD_REGNO_NREGS somewhere in the loop code.

	Unfortunately, it's not just "somewhere", it's everywhere.  This
code probably should use set and the bitmaps routines if it weren't going
away soon (hopefully).

	The following patch adds HARD_REGNO_NREGS and loops over nregs and
fixes the hoisting bug.  I wanted to get some more eyes on it before I
start testing it extensively.

David


	* loop.c: Record regno information for all hard registers when a
	mode requires multiple hard registers.

Index: loop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.c,v
retrieving revision 1.369
diff -c -p -r1.369 loop.c
*** loop.c	2001/11/15 23:44:56	1.369
--- loop.c	2001/12/13 18:27:38
*************** scan_loop (loop, flags)
*** 522,528 ****
  {
    struct loop_info *loop_info = LOOP_INFO (loop);
    struct loop_regs *regs = LOOP_REGS (loop);
!   int i;
    rtx loop_start = loop->start;
    rtx loop_end = loop->end;
    rtx p;
--- 522,528 ----
  {
    struct loop_info *loop_info = LOOP_INFO (loop);
    struct loop_regs *regs = LOOP_REGS (loop);
!   int i, nregs;
    rtx loop_start = loop->start;
    rtx loop_end = loop->end;
    rtx p;
*************** scan_loop (loop, flags)
*** 808,814 ****
  				   SET_DEST (set), copy_rtx (SET_SRC (set)));
  
  		  delete_insn (p);
! 		  regs->array[regno].set_in_loop = 0;
  		  continue;
  		}
  
--- 808,818 ----
  				   SET_DEST (set), copy_rtx (SET_SRC (set)));
  
  		  delete_insn (p);
! 		  nregs = regno < FIRST_PSEUDO_REGISTER
! 		    ? HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (set)))
! 		    : 1;
! 		  for (i = 0; i < nregs; i++)
! 		    regs->array[regno+i].set_in_loop = 0;
  		  continue;
  		}
  
*************** scan_loop (loop, flags)
*** 838,844 ****
  	      m->savings = regs->array[regno].n_times_set;
  	      if (find_reg_note (p, REG_RETVAL, NULL_RTX))
  		m->savings += libcall_benefit (p);
! 	      regs->array[regno].set_in_loop = move_insn ? -2 : -1;
  	      /* Add M to the end of the chain MOVABLES.  */
  	      loop_movables_add (movables, m);
  
--- 842,852 ----
  	      m->savings = regs->array[regno].n_times_set;
  	      if (find_reg_note (p, REG_RETVAL, NULL_RTX))
  		m->savings += libcall_benefit (p);
! 	      nregs = regno < FIRST_PSEUDO_REGISTER
! 		? HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (set)))
! 		: 1;
! 	      for (i = 0; i < nregs; i++)
! 		regs->array[regno+i].set_in_loop = move_insn ? -2 : -1;
  	      /* Add M to the end of the chain MOVABLES.  */
  	      loop_movables_add (movables, m);
  
*************** scan_loop (loop, flags)
*** 939,945 ****
  		  m->match = 0;
  		  m->lifetime = LOOP_REG_LIFETIME (loop, regno);
  		  m->savings = 1;
! 		  regs->array[regno].set_in_loop = -1;
  		  /* Add M to the end of the chain MOVABLES.  */
  		  loop_movables_add (movables, m);
  		}
--- 947,957 ----
  		  m->match = 0;
  		  m->lifetime = LOOP_REG_LIFETIME (loop, regno);
  		  m->savings = 1;
! 		  nregs = regno < FIRST_PSEUDO_REGISTER
! 		    ? HARD_REGNO_NREGS (regno, GET_MODE (SET_DEST (set)))
! 		    : 1;
! 		  for (i = 0; i < nregs; i++)
! 		    regs->array[regno+i].set_in_loop = -1;
  		  /* Add M to the end of the chain MOVABLES.  */
  		  loop_movables_add (movables, m);
  		}
*************** move_movables (loop, movables, threshold
*** 2060,2066 ****
  
  	      /* The reg set here is now invariant.  */
  	      if (! m->partial)
! 		regs->array[regno].set_in_loop = 0;
  
  	      m->done = 1;
  
--- 2072,2084 ----
  
  	      /* The reg set here is now invariant.  */
  	      if (! m->partial)
! 		{
! 		  int i, n = regno < FIRST_PSEUDO_REGISTER
! 		    ? HARD_REGNO_NREGS (regno, GET_MODE (m->set_dest))
! 		    : 1;
! 		  for (i = 0; i < n; i++)
! 		    regs->array[regno+i].set_in_loop = 0;
! 		}
  
  	      m->done = 1;
  
*************** move_movables (loop, movables, threshold
*** 2120,2126 ****
  		      /* The reg merged here is now invariant,
  			 if the reg it matches is invariant.  */
  		      if (! m->partial)
! 			regs->array[m1->regno].set_in_loop = 0;
  		    }
  	    }
  	  else if (loop_dump_stream)
--- 2138,2150 ----
  		      /* The reg merged here is now invariant,
  			 if the reg it matches is invariant.  */
  		      if (! m->partial)
! 			{
! 			  int i, n = regno < FIRST_PSEUDO_REGISTER
! 			    ? HARD_REGNO_NREGS (regno, GET_MODE (m1->set_dest))
! 			    : 1;
! 			  for (i = 0; i < n; i++)
! 			    regs->array[m1->regno+i].set_in_loop = 0;
! 			}
  		    }
  	    }
  	  else if (loop_dump_stream)
*************** count_one_set (regs, insn, x, last_set)
*** 3360,3382 ****
  	dest = XEXP (dest, 0);
        if (GET_CODE (dest) == REG)
  	{
  	  int regno = REGNO (dest);
! 	  /* If this is the first setting of this reg
! 	     in current basic block, and it was set before,
! 	     it must be set in two basic blocks, so it cannot
! 	     be moved out of the loop.  */
! 	  if (regs->array[regno].set_in_loop > 0
! 	      && last_set == 0)
! 	    regs->array[regno].may_not_optimize = 1;
! 	  /* If this is not first setting in current basic block,
! 	     see if reg was used in between previous one and this.
! 	     If so, neither one can be moved.  */
! 	  if (last_set[regno] != 0
! 	      && reg_used_between_p (dest, last_set[regno], insn))
! 	    regs->array[regno].may_not_optimize = 1;
! 	  if (regs->array[regno].set_in_loop < 127)
! 	    ++regs->array[regno].set_in_loop;
! 	  last_set[regno] = insn;
  	}
      }
  }
--- 3384,3413 ----
  	dest = XEXP (dest, 0);
        if (GET_CODE (dest) == REG)
  	{
+ 	  int i;
  	  int regno = REGNO (dest);
! 	  int nregs = regno < FIRST_PSEUDO_REGISTER
! 	    ? HARD_REGNO_NREGS (regno, GET_MODE (dest))
! 	    : 1;
! 	  for (i = 0; i < nregs; i++)
! 	    {
! 	      /* If this is the first setting of this reg
! 		 in current basic block, and it was set before,
! 		 it must be set in two basic blocks, so it cannot
! 		 be moved out of the loop.  */
! 	      if (regs->array[regno].set_in_loop > 0
! 		  && last_set == 0)
! 		regs->array[regno+i].may_not_optimize = 1;
! 	      /* If this is not first setting in current basic block,
! 		 see if reg was used in between previous one and this.
! 		 If so, neither one can be moved.  */
! 	      if (last_set[regno] != 0
! 		  && reg_used_between_p (dest, last_set[regno], insn))
! 		regs->array[regno+i].may_not_optimize = 1;
! 	      if (regs->array[regno+i].set_in_loop < 127)
! 		++regs->array[regno+i].set_in_loop;
! 	      last_set[regno+i] = insn;
! 	    }
  	}
      }
  }

Re: Load hoisting bug

[Richard Henderson]

On Thu, Dec 13, 2001 at 01:33:08PM -0500, David Edelsohn wrote:
> 	The following patch adds HARD_REGNO_NREGS and loops over nregs and
> fixes the hoisting bug.  I wanted to get some more eyes on it before I
> start testing it extensively.

All the places you changed look right.


r~