calculate_global_regs_live

calculate_global_regs_live

[Eric Botcazou]

Hi,

Is it a feature or an oversight that calculate_global_regs_live doesn't clear 
the regsets containing the liveness information for each BB before calculing 
them again?

The algorithm is explained by the following comment:

  /* We work through the queue until there are no more blocks.  What
     is live at the end of this block is precisely the union of what
     is live at the beginning of all its successors.  So, we set its
     GLOBAL_LIVE_AT_END field based on the GLOBAL_LIVE_AT_START field
     for its successors.  Then, we compute GLOBAL_LIVE_AT_START for
     this block by walking through the instructions in this block in
     reverse order and updating as we go.  If that changed
     GLOBAL_LIVE_AT_START, we add the predecessors of the block to the
     queue; they will now need to recalculate GLOBAL_LIVE_AT_END.

     We are guaranteed to terminate, because GLOBAL_LIVE_AT_START
     never shrinks.  If a register appears in GLOBAL_LIVE_AT_START, it
     must either be live at the end of the block, or used within the
     block.  In the latter case, it will certainly never disappear
     from GLOBAL_LIVE_AT_START.  In the former case, the register
     could go away only if it disappeared from GLOBAL_LIVE_AT_START
     for one of the successor blocks.  By induction, that cannot
     occur.  */

If GLOBAL_LIVE_AT_START starts as non-zero, it can shrink and the reasoning 
above doesn't apply anymore.  I have a testcase which causes an infinite 
oscillation in the function because of this problem.

-- 
Eric Botcazou

Re: calculate_global_regs_live

[Jim Wilson]

Eric Botcazou wrote:
> Is it a feature or an oversight that calculate_global_regs_live doesn't clear 
> the regsets containing the liveness information for each BB before calculing 
> them again?

In gcc-2.95, I see that life_analysis_1 computes these fields.  It 
allocates the fields before computing them, so they are always zero.

In gcc-3.0, we now have update_life_info/calculate_global_regs_live, and 
update_life_info is now called from multiple places, only one of which 
allocates the fields before the call.  So some calls could already have 
data when we enter.

In gcc-3.1, update_life_info now calls calculate_global_regs_live in a 
loop, so it is called multiple times with one update_life_info call. 
The calculate_global_regs_live comment you quoted appears, but it seems 
to be the same algorithm, so it appears to be just a documentation 
improvement.

On mainline, there is code in update_life_info to clear the fields in 
question at the end of the loop before calling 
calculate_globals_regs_live again.  So it appears that someone has 
already noticed a similar problem to yours.

Maybe this clearing needs to be done at the top of the loop?  We don't 
need this for the very first call to update_life_info, but it may not be 
worth optimizing that case.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: calculate_global_regs_live

[Eric Botcazou]

> In gcc-3.1, update_life_info now calls calculate_global_regs_live in a
> loop, so it is called multiple times with one update_life_info call.
> The calculate_global_regs_live comment you quoted appears, but it seems
> to be the same algorithm, so it appears to be just a documentation
> improvement.

Yes, it was added by a comment-only patch by Mark Mitchell.

> On mainline, there is code in update_life_info to clear the fields in
> question at the end of the loop before calling
> calculate_globals_regs_live again.  So it appears that someone has
> already noticed a similar problem to yours.

Oh! I managed to miss it on mainline (the problem I see is on the 3.3 
branch).  The code was added by

2003-01-30  Richard Henderson  <rth@redhat.com>

	* flow.c (update_life_info): Zap life info after cleanup_cfg.
	(regno_uninitialized): Use correct live at function entry set.
	(regno_clobbered_at_setjmp): Likewise.

but, according to the comment, not for the problem I ran into.  I'll update 
the comment on mainline.

Do you think it is safe to backport the patch (or only part of it) to the 3.3 
branch? It's PR optimization/12158, originating from Debian.

Thanks.

-- 
Eric Botcazou

Re: calculate_global_regs_live

[Jim Wilson]

On Fri, 2003-12-12 at 01:12, Eric Botcazou wrote:
> Do you think it is safe to backport the patch (or only part of it) to the 3.3 
> branch? It's PR optimization/12158, originating from Debian.

It seems reasonably safe to me.
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: calculate_global_regs_live

[Eric Botcazou]

> It seems reasonably safe to me.

Ok.  It turns out that we need more as you correctly supposed: we really need 
to clear the regsets at the top of the loop.

-- 
Eric Botcazou

Re: calculate_global_regs_live

[Eric Botcazou]

> Ok.  It turns out that we need more as you correctly supposed: we really
> need to clear the regsets at the top of the loop.

Well, it turns out that this doesn't work either: by doing so, we may clear 
the liveness information on a BB which will not be processed by 
calculate_global_regs_live because it is not referenced in 'blocks', thus 
causing a checking failure in verify_wide_reg later.  And I think Richard's 
patch might be questionable for the very same reason.

I think the situation is rather messy:
- to be sure that calculate_global_regs_live will terminate, we need to make 
it so that GLOBAL_LIVE_AT_START never shrinks for any modified BB.  This 
means in practice that we need to clear GLOBAL_LIVE_AT_START before entering 
calculate_global_regs_live for any BB that will be modified;
- as I said above, if GLOBAL_LIVE_AT_START is cleared for a BB that will not 
be modified, we'll run into problems during later passes;
- so we need to clear GLOBAL_LIVE_AT_START for the exact set of BBs that will 
be modified;
- when 'blocks' is non-zero, the set of BBs that will be modified may be a 
strict superset of 'blocks', unless 'blocks' contains all BBs.  And we don't 
have this information before calling calculate_global_regs_live.

Hence the conclusion: we need to always clear GLOBAL_LIVE_AT_START for all 
BBs and always recalculate it for all BBs.  This means that 'blocks' must 
contain all BBs as soon as 'extent' is not UPDATE_LIFE_LOCAL in 
update_life_info.  With probably an effect on compile-time.

However, given that infinite loops in calculate_global_regs_live appear to be 
seldom seen in practice, we might want to use only a partial solution: 
clearing GLOBAL_LIVE_AT_START at the top of the loop only for BBs that are 
referenced in 'blocks'.  This is enough to fix PR opt/12158 and we are 
guaranteed not to wrongly clear liveness information.  But, of course, this 
still doesn't guarantee that calculate_global_regs_live will always 
terminate, only that there are fewer chances it won't.

-- 
Eric Botcazou

Re: calculate_global_regs_live

[Jim Wilson]

On Wed, 2003-12-17 at 10:47, Eric Botcazou wrote:
> I think the situation is rather messy:

It does sound a bit messy.

I tried looking at callers of update_life_info.  It looks like most of
them already pass all blocks when extent != UPDATE_LIFE_LOCAL. 
Exceptions:
  cfgrtl.c purge_all_dead_edges
  recog.c split_all_insns
  sched-rgn.c schedule_insns
Since the majority already do this, I suspect the run time performance
won't be impacted too much if we assume this.

There is a particularly interesting bit in flow.c in the function
update_life_info_in_dirty_blocks.  If called with a subset of blocks,
and extent is not UPDATE_LIFE_LOCAL, then it already adds in all
blocks.  There is a comment that says this was needed to fix a pentium4
bootstrap failure.  So again, it seems someone ran into a related
problem.  And not surprisingly, it was Richard Henderson again.  See
	http://gcc.gnu.org/ml/gcc-patches/2002-05/msg02253.html
This message refers to suggestions from Jan to solve the problem you are
looking into.  Maybe you can find them on the mailing list archive?  Or
maybe Jan remembers?
-- 
Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

Re: calculate_global_regs_live

[Eric Botcazou]

> I tried looking at callers of update_life_info.  It looks like most of
> them already pass all blocks when extent != UPDATE_LIFE_LOCAL.
> Exceptions:
>   cfgrtl.c purge_all_dead_edges
>   recog.c split_all_insns
>   sched-rgn.c schedule_insns

Yes, I did the same search.

> Since the majority already do this, I suspect the run time performance
> won't be impacted too much if we assume this.

I don't know (but of course I don't have your experience).  There is perhaps 
a trade-off here, because infinite loops in c_g_r_l appear to be very rare.  
And we could make them even rarer by clearing the BBs in 'blocks'.

> There is a particularly interesting bit in flow.c in the function
> update_life_info_in_dirty_blocks.  If called with a subset of blocks,
> and extent is not UPDATE_LIFE_LOCAL, then it already adds in all
> blocks.  There is a comment that says this was needed to fix a pentium4
> bootstrap failure.  So again, it seems someone ran into a related
> problem.  And not surprisingly, it was Richard Henderson again.  See
> 	http://gcc.gnu.org/ml/gcc-patches/2002-05/msg02253.html

Oh! yes, the very same problem.  Could you lend me your glasses (or your eyes 
if you prefer)? :-)

> This message refers to suggestions from Jan to solve the problem you are
> looking into.  Maybe you can find them on the mailing list archive?  Or
> maybe Jan remembers?

Jan, do you have any recollection about suggestions to guarantee that 
calculate_global_regs_live from flow.c will always terminate?

The problem is described here:
   http://gcc.gnu.org/ml/gcc/2003-12/msg00698.html
It was also reported here:
   http://gcc.gnu.org/ml/gcc/2001-02/msg00476.html
And Richard hinted at your suggestions here:
   http://gcc.gnu.org/ml/gcc-patches/2002-05/msg02253.html

-- 
Eric Botcazou

Re: calculate_global_regs_live

[Jan Hubicka]

> > I tried looking at callers of update_life_info.  It looks like most of
> > them already pass all blocks when extent != UPDATE_LIFE_LOCAL.
> > Exceptions:
> >   cfgrtl.c purge_all_dead_edges
> >   recog.c split_all_insns
> >   sched-rgn.c schedule_insns
> 
> Yes, I did the same search.
> 
> > Since the majority already do this, I suspect the run time performance
> > won't be impacted too much if we assume this.
> 
> I don't know (but of course I don't have your experience).  There is perhaps 
> a trade-off here, because infinite loops in c_g_r_l appear to be very rare.  
> And we could make them even rarer by clearing the BBs in 'blocks'.
> 
> > There is a particularly interesting bit in flow.c in the function
> > update_life_info_in_dirty_blocks.  If called with a subset of blocks,
> > and extent is not UPDATE_LIFE_LOCAL, then it already adds in all
> > blocks.  There is a comment that says this was needed to fix a pentium4
> > bootstrap failure.  So again, it seems someone ran into a related
> > problem.  And not surprisingly, it was Richard Henderson again.  See
> > 	http://gcc.gnu.org/ml/gcc-patches/2002-05/msg02253.html
> 
> Oh! yes, the very same problem.  Could you lend me your glasses (or your eyes 
> if you prefer)? :-)
> 
> > This message refers to suggestions from Jan to solve the problem you are
> > looking into.  Maybe you can find them on the mailing list archive?  Or
> > maybe Jan remembers?
> 
> Jan, do you have any recollection about suggestions to guarantee that 
> calculate_global_regs_live from flow.c will always terminate?
> 
> The problem is described here:
>    http://gcc.gnu.org/ml/gcc/2003-12/msg00698.html
> It was also reported here:
>    http://gcc.gnu.org/ml/gcc/2001-02/msg00476.html
> And Richard hinted at your suggestions here:
>    http://gcc.gnu.org/ml/gcc-patches/2002-05/msg02253.html

It is kind of feature to limit work needed to update liveness, but it is
broken as it ineed don't have to converge.  In the past we always
somehow papered around.
There is patch by Zdenek to ensure finitarity of the propagation that I
think is best compromise sollution for this problem unless we want to go
for DJ-graphs based liveness computation that is much more involved and
can't embedde dead code removal as we do right now.
http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html

Honza

> 
> -- 
> Eric Botcazou

Re: calculate_global_regs_live

[Eric Botcazou]

> It is kind of feature to limit work needed to update liveness, but it is
> broken as it ineed don't have to converge.  In the past we always
> somehow papered around.

It indeed appears to be a long-standing problem, that I rediscovered again.  
If we can't find a definitive solution, I'll add large comments in the code 
so that the next guy doesn't have to go through the same discovery process.

Thanks for the quick response.

> There is patch by Zdenek to ensure finitarity of the propagation that I
> think is best compromise sollution for this problem unless we want to go
> for DJ-graphs based liveness computation that is much more involved and
> can't embedde dead code removal as we do right now.
> http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html

What happened to this patch, Zdenek?  Was it even reviewed?

-- 
Eric Botcazou

Re: calculate_global_regs_live

[Zdenek Dvorak]

Hello,

> > There is patch by Zdenek to ensure finitarity of the propagation that I
> > think is best compromise sollution for this problem unless we want to go
> > for DJ-graphs based liveness computation that is much more involved and
> > can't embedde dead code removal as we do right now.
> > http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html
> 
> What happened to this patch, Zdenek?  Was it even reviewed?

IIRC I was asked to provide a testcase demonstrating the problem,
but I had none at that time.  At that the point the patch got stuck.

Zdenek

Re: calculate_global_regs_live

[Jan Hubicka]

> > It is kind of feature to limit work needed to update liveness, but it is
> > broken as it ineed don't have to converge.  In the past we always
> > somehow papered around.
> 
> It indeed appears to be a long-standing problem, that I rediscovered again.  
> If we can't find a definitive solution, I'll add large comments in the code 
> so that the next guy doesn't have to go through the same discovery process.
> 
> Thanks for the quick response.
> 
> > There is patch by Zdenek to ensure finitarity of the propagation that I
> > think is best compromise sollution for this problem unless we want to go
> > for DJ-graphs based liveness computation that is much more involved and
> > can't embedde dead code removal as we do right now.
> > http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html
> 
> What happened to this patch, Zdenek?  Was it even reviewed?

I remember some at least partial review done by Zack, but it apparently
never was rejected or accepted.  Zdenek will know more.

Honza
> 
> -- 
> Eric Botcazou

Re: calculate_global_regs_live

[Joern Rennecke]

> Hello,
> 
> > > There is patch by Zdenek to ensure finitarity of the propagation that I
> > > think is best compromise sollution for this problem unless we want to go
> > > for DJ-graphs based liveness computation that is much more involved and
> > > can't embedde dead code removal as we do right now.
> > > http://gcc.gnu.org/ml/gcc-patches/2003-01/msg02059.html
> > 
> > What happened to this patch, Zdenek?  Was it even reviewed?
> 
> IIRC I was asked to provide a testcase demonstrating the problem,
> but I had none at that time.  At that the point the patch got stuck.

FWIW, a customer of ours has run into this problem recently with a
lex-generated parser; it's the yylex function that was affected, with some
7000 instructions.  Zdenek's patch cures the problem.

However, we are using a compiler based on an older gcc version with a
number of patches for efficient and correct code generation for the SH,
and the testcase doesn't trigger the problem on a 3.3.2 based compiler or
on mainline.  I would in fact expect any testcase to be good for only
a few snapshots, or just for a single one, due to the complex
interactions with earlier passes.