[PATCH] Unbreak forward simulation of liveness (!)

[PATCH] Unbreak forward simulation of liveness (!)

[Paolo Bonzini]

Hi all,

this patch is the main reason why I've not yet submitted the patch to 
restore memory usage of fwprop.  The patch had a regression and I found 
time to analyze it only now.

It seems that forward simulation of liveness is totally broken, in that 
it never adds a register to the set!  So, we get (way) too many dead 
registers.  In the case of fwprop this would call a missed optimization, 
with one single exception: this is PR39543, where the missed propagation 
causes reload failures.

The problem is that while scanning forwards, a def will _generate_ 
liveness!  The reason is that during the solution of the problem, the 
def had killed liveness towards the top of the basic block; now we have 
to assume that liveness was generated and use REG_UNUSED notes to clean 
up extra bits.

df_simulate_initialize_forwards is broken in the same way.  I have no 
time right now to fix it, and it is safe for fwprop, so I would 
appreciate if Kenny took a look at it.  The simplest way seems to be to 
restore DF_LR_TOP/DF_LIVE_TOP, and then use that in fwprop.  Possibly 
you could make that a changeable flag.

Finally, there's also df_simulate_finalize_forwards, which I think we 
can delete (it's just computing DF_LR_OUT in an expensive way).

The patch has been regtested together with the fwprop patch; a full 
bootstrap is in progress.  Ok when it finishes?

Paolo

Re: [PATCH] Unbreak forward simulation of liveness (!)

[Paolo Bonzini]

[-- Attachment #1: Type: text/plain, Size: 1477 bytes --]

On 11/08/2009 04:27 PM, Paolo Bonzini wrote:
> Hi all,
>
> this patch is the main reason why I've not yet submitted the patch to
> restore memory usage of fwprop. The patch had a regression and I found
> time to analyze it only now.
>
> It seems that forward simulation of liveness is totally broken, in that
> it never adds a register to the set! So, we get (way) too many dead
> registers. In the case of fwprop this would call a missed optimization,
> with one single exception: this is PR39543, where the missed propagation
> causes reload failures.
>
> The problem is that while scanning forwards, a def will _generate_
> liveness! The reason is that during the solution of the problem, the def
> had killed liveness towards the top of the basic block; now we have to
> assume that liveness was generated and use REG_UNUSED notes to clean up
> extra bits.
>
> df_simulate_initialize_forwards is broken in the same way. I have no
> time right now to fix it, and it is safe for fwprop, so I would
> appreciate if Kenny took a look at it. The simplest way seems to be to
> restore DF_LR_TOP/DF_LIVE_TOP, and then use that in fwprop. Possibly you
> could make that a changeable flag.
>
> Finally, there's also df_simulate_finalize_forwards, which I think we
> can delete (it's just computing DF_LR_OUT in an expensive way).
>
> The patch has been regtested together with the fwprop patch; a full
> bootstrap is in progress. Ok when it finishes?

And the patch is here.

Paolo

[-- Attachment #2: broken-forwards-scan.patch --]
[-- Type: text/plain, Size: 1079 bytes --]

2009-11-08  Paolo Bonzini  <bonzini@gnu.org>

	* df-problems.c (df_simulate_one_insn_forwards): Fix typo;
	use df_simulate_find_defs.

Index: df-problems.c
===================================================================
--- df-problems.c	(revision 153680)
+++ df-problems.c	(working copy)
@@ -3927,10 +3927,15 @@ df_simulate_one_insn_forwards (basic_blo
   if (! INSN_P (insn))
     return;	
 
-  /* Make sure that the DF_NOTES really is an active df problem.  */ 
+  /* Make sure that DF_NOTE really is an active df problem.  */ 
   gcc_assert (df_note);
 
-  df_simulate_defs (insn, live);
+  /* Note that this is the opposite as how the problem is defined, because
+     int the LR problem defs _kill_ liveness.  However, they do so backwards,
+     while here the scan is performed forwards!  So, first assume that the
+     def is live, and if this is not true REG_UNUSED notes will rectify the
+     situation.  */
+  df_simulate_find_defs (insn, live);
 
   /* Clear all of the registers that go dead.  */
   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))

Re: [PATCH] Unbreak forward simulation of liveness (!)

[Eric Botcazou]

> The patch has been regtested together with the fwprop patch; a full
> bootstrap is in progress.  Ok when it finishes?

OK by me *only if* you also fix all the wrong comments and add ??? for the 
remaining wrong stuff:

/*----------------------------------------------------------------------------
   Functions for simulating the effects of single insns.  

   You can either simulate in the forwards direction, starting from
   the top of a block or the backwards direction from the end of the
   block.  The main difference is that if you go forwards, the uses
   are examined first then the defs, and if you go backwards, the defs
   are examined first then the uses.

That's not what the code does in the forwards case.


   df_simulate_initialize_forwards should be called first with a
   bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
   df_simulate_one_insn_forwards should be called for each insn in
   the block, starting with the last on.

"with the first one".


/* Apply the artificial uses and defs at the top of BB in a backwards
   direction.  */

"in a forwards direction"


void 
df_simulate_initialize_forwards (basic_block bb, bitmap live)
{
  df_ref *def_rec;
  int bb_index = bb->index;
  
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
    {
      df_ref def = *def_rec;
      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
	bitmap_clear_bit (live, DF_REF_REGNO (def));
    }
}

Add the ??? comment or a stopgap fix.


/* Simulate the backwards effects of INSN on the bitmap LIVE.  */

"forwards effects"


void 
df_simulate_one_insn_forwards (basic_block bb, rtx insn, bitmap live)
{
  rtx link;
  if (! INSN_P (insn))
    return;	

  /* Make sure that DF_NOTE really is an active df problem.  */ 
  gcc_assert (df_note);
 
  /* Note that this is the opposite as how the problem is defined, because
     int the LR problem defs _kill_ liveness.  However, they do so backwards,
     while here the scan is performed forwards!  So, first assume that the
     def is live, and if this is not true REG_UNUSED notes will rectify the
     situation.  */
  df_simulate_find_defs (insn, live);

"in the LR problem".


/* Apply the artificial uses and defs at the end of BB in a backwards
   direction.  */

"forwards"


void 
df_simulate_finalize_forwards (basic_block bb, bitmap live)
{
  df_ref *def_rec;
  int bb_index = bb->index;
  
  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
    {
      df_ref def = *def_rec;
      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
	bitmap_clear_bit (live, DF_REF_REGNO (def));
    }
}

Add the ??? comment or a stopgap fix.

-- 
Eric Botcazou

Re: [PATCH] Unbreak forward simulation of liveness (!)

[Paolo Bonzini]

On 11/08/2009 06:04 PM, Eric Botcazou wrote:
> Add the ??? comment or a stopgap fix.

I'll remove df_simulate_finalize_forwards altogether

Thanks for the review, I'll wait for Kenny's remarks.

Paolo

Re: [PATCH] Unbreak forward simulation of liveness (!)

[Kenneth Zadeck]

Paolo Bonzini wrote:
> On 11/08/2009 06:04 PM, Eric Botcazou wrote:
>> Add the ??? comment or a stopgap fix.
>
> I'll remove df_simulate_finalize_forwards altogether
>
> Thanks for the review, I'll wait for Kenny's remarks.
>
> Paolo
the patch is fine if you fix the typo in the second line of the second
comment.

s/int/in/

kenny