Problem with the special live analyzer in global alloc

Problem with the special live analyzer in global alloc

[Andreas Krebbel]

Hello,

the 920501-4.c testcase currently fails on s390x with a
"fatal error: internal consistency failure" in reg rename.

The example uses an uninitialized variable. Normal live analysis
consideres this variable to be live over all basic blocks.
But global alloc uses a special liveness checker considering
variables which are read uninitialized to never conflict with others.
In the example an uninitialized variable is assigned to the same hard register
as a pseudo assigned by local alloc. This leads to an ICE when the
normal live analysis is used for consistency checks as it is done in
reg rename.

Consider the locally allocated hard reg to be r1 in basic block 1. bb1
contains an insn setting r1 and another using and clobbering it. 
Live analysis recognizes r1 to be dead at the begin of bb1 and after
the insn clobbering r1.
If r1 is also used for the uninitialized variable, r1 is live at the
end of bb1! Reg rename now renames r1 locally to r2 and re-performs
live analysis in order to check whether the local change has global
impact. Because r1 is not used anymore in bb1 and is live at end it
has to be considered live at start too. Hence the live at start
register set has changed which triggers the ICE.

As already stated I think that the usage of different algorithms for
calculating live info causes the problem. Is there a reason that the
live analysis used by global alloc isn't used everywhere?


Bye,

-Andreas-

Re: Problem with the special live analyzer in global alloc

[Daniel Berlin]

> As already stated I think that the usage of different algorithms for
> calculating live info causes the problem. Is there a reason that the
> live analysis used by global alloc isn't used everywhere?
Vlad promised to update it to use df.c once it wasn't "1% slower", which
would make it easily reusable elsewhere, but never did.
Of course, you could reuse it without that, but then someone will
invariably come along and mess with it.

> 
> 
> Bye,
> 
> -Andreas-

Re: Problem with the special live analyzer in global alloc

[Andreas Krebbel]

Hello,

sorry for the late answer.

> Vlad promised to update it to use df.c once it wasn't "1% slower", which
> would make it easily reusable elsewhere, but never did.
> Of course, you could reuse it without that, but then someone will
> invariably come along and mess with it.

Ok I understand that implementing the special lifeness analyzers in global alloc
using the df.c framework would ease reusing it somewhere else. But my question
was more basic.
So do you agree that using one lifeness analyzer for checking what
an optimizer step has done based on a second lifeness analyzers output
is wrong? If so what is the way to fix this? Going back to the normal analyzer to
be used in global alloc would make global alloc creating worse code. But on the other hand
using the global alloc lifeness analyzer everywhere else would be a change 
which nobody would agree with in the current development stage.

Because this is a regression from 4.0 to 4.1 this should be fixed as soon as possible.

Bye,

-Andreas-

Re: Problem with the special live analyzer in global alloc

[Bernd Schmidt]

Andreas Krebbel wrote:

> Ok I understand that implementing the special lifeness analyzers in global alloc
> using the df.c framework would ease reusing it somewhere else. But my question
> was more basic.
> So do you agree that using one lifeness analyzer for checking what
> an optimizer step has done based on a second lifeness analyzers output
> is wrong? If so what is the way to fix this? Going back to the normal analyzer to
> be used in global alloc would make global alloc creating worse code. But on the other hand
> using the global alloc lifeness analyzer everywhere else would be a change 
> which nobody would agree with in the current development stage.

Jim Wilson once suggested we should just emit insns to make sure every 
register is initialized and be done with it - problem solved.  I had 
started to work on that, if people think it's a good idea I can dig that 
stuff out again.


Bernd

Re: Problem with the special live analyzer in global alloc

[Daniel Berlin]

On Tue, 2005-08-23 at 16:44 +0200, Bernd Schmidt wrote:
> Andreas Krebbel wrote:
> 
> > Ok I understand that implementing the special lifeness analyzers in global alloc
> > using the df.c framework would ease reusing it somewhere else. But my question
> > was more basic.
> > So do you agree that using one lifeness analyzer for checking what
> > an optimizer step has done based on a second lifeness analyzers output
> > is wrong? If so what is the way to fix this? Going back to the normal analyzer to
> > be used in global alloc would make global alloc creating worse code. But on the other hand
> > using the global alloc lifeness analyzer everywhere else would be a change 
> > which nobody would agree with in the current development stage.
> 
> Jim Wilson once suggested we should just emit insns to make sure every 
> register is initialized and be done with it - problem solved.  

But doesn't this actually the information you get worse?

Partial liveness gives you an answer, which is "It's not really live
here, because it's not defined"

If you make them all defined, then it's going to be live where it wasn't
before, even though it's not really *used* over those paths.


> I had 
> started to work on that, if people think it's a good idea I can dig that 
> stuff out again.
> 
> 
> Bernd

Re: Problem with the special live analyzer in global alloc

[Bernd Schmidt]

Daniel Berlin wrote:

> If you make them all defined, then it's going to be live where it wasn't
> before, even though it's not really *used* over those paths.

The idea is to put the initialization insns only on the paths where the 
register will be uninitialized.


Bernd

Re: Problem with the special live analyzer in global alloc

[Steven Bosscher]

On Tuesday 23 August 2005 17:06, Bernd Schmidt wrote:
> The idea is to put the initialization insns only on the paths where the
> register will be uninitialized.

int foo (int n)
{
  int a;

  while (--n)
    a = n;

  return a;
}

Not knowing n, how can you be sure whether "a" is uninitialized for
the "return" statement or not?

Gr.
Steven

Re: Problem with the special live analyzer in global alloc

[Bernd Schmidt]

Steven Bosscher wrote:
> On Tuesday 23 August 2005 17:06, Bernd Schmidt wrote:
> 
>>The idea is to put the initialization insns only on the paths where the
>>register will be uninitialized.
> 
> 
> int foo (int n)
> {
>   int a;
> 
>   while (--n)
>     a = n;
> 
>   return a;
> }
> 
> Not knowing n, how can you be sure whether "a" is uninitialized for
> the "return" statement or not?

In this case, assuming nothing interesting happens to the loop, you'll 
have to conservatively initialize "a" near the top of the function.  In 
many cases you can do better and either initialize just before the use, 
or initialize on an edge on which the register is uninitialized.  For 
register allocation purposes however, this should be as good as using 
Vlad's new liveness analysis.

As Jim points out, we may have to do that for IA64 anyway, so we could 
consider doing it on all targets.  Dan is correct that this can 
introduce new code that won't be eliminated.  One question is how often 
this is going to occur in practice.


Bernd

Re: Problem with the special live analyzer in global alloc

[Peter Bergner]

On Tue, 2005-08-23 at 21:26 +0200, Bernd Schmidt wrote:
> As Jim points out, we may have to do that for IA64 anyway, so we could 
> consider doing it on all targets.  Dan is correct that this can 
> introduce new code that won't be eliminated.  One question is how often 
> this is going to occur in practice.

The IBM iSeries (aka AS/400) compiler actually inserts definitions
on edges where a pseudo/register is undefined.  However, unlike the
discussion here, our "pseudo" definitions never lead to generated
code.  Our pseudo definitions were added to simplify some analysis
phases in the compiler (eg, liveness can be simplified down to LIVE
rather than LIVE & AVAL).  Note that we needed to handle these pseudo
definitions specially in some cases so they don't reduce optimization
opportunities.  If I remember correctly (it's been a while since I
left the team):

    1) All pseudo defs get the value of <bottom> so rematerialization,
       etc. are not pessimized.
    2) Pseudo definitions are ignored during the interference graph
       construction (ie, they never cause edges to be added to the
       interference graph).
    3) More things I can't think of at the moment.

This was a win for the iSeries compiler since a fair number of
applications were/are written in RPG which is essentially a one
procedure application, so the number of basic blocks and live
ranges/webs can be quite high.  I recall one program we ran into
that had about 150K basic blocks and about 1.5M live ranges.

I know we used to have a white paper describing the internals of the
iSeries compiler (titled "The AS/400 Optimizing Translator"), but all
of the links I can find are stale.  However, I did come across their
patent (5,761,514) describing the idea: "Register allocation method
and apparatus for truncating runaway lifetimes of program variables
in a computer system".  I have no idea whether this was one of the
patents made available by IBM for use by the OSS community or not.

Peter

--
Peter Bergner
Linux on Power Toolchain
IBM Linux Technology Center

Re: Problem with the special live analyzer in global alloc

[Daniel Berlin]

On Tue, 2005-08-23 at 22:10 -0500, Peter Bergner wrote:
> On Tue, 2005-08-23 at 21:26 +0200, Bernd Schmidt wrote:
> > As Jim points out, we may have to do that for IA64 anyway, so we could 
> > consider doing it on all targets.  Dan is correct that this can 
> > introduce new code that won't be eliminated.  One question is how often 
> > this is going to occur in practice.
> 
> The IBM iSeries (aka AS/400) compiler actually inserts definitions
> on edges where a pseudo/register is undefined.  However, unlike the
> discussion here, our "pseudo" definitions never lead to generated
> code
I listed that as a possible option, the problem is that you have to know
that they are pseudo definitions, and teach other things this too.
This is the part i alluded to being probably uglier than partial
liveness analysis itself.
> .  Our pseudo definitions were added to simplify some analysis
> phases in the compiler (eg, liveness can be simplified down to LIVE
> rather than LIVE & AVAL).  Note that we needed to handle these pseudo
> definitions specially in some cases so they don't reduce optimization
> opportunities. 
Like this :)

Is LIVE & AVAIL really that much slower these days for most programs?

I imagine if you have 300k bb's or 1.5 million live pseudos to consider,
it probably makes a real difference, but that's not *too* common in our
supported languages (30k bb's/150k pseudos is probably the practical
upper limit of what we see, though i'm sure someone is going to say
they've seen larger :P)


> I know we used to have a white paper describing the internals of the
> iSeries compiler (titled "The AS/400 Optimizing Translator"), but all
> of the links I can find are stale.  However, I did come across their
> patent (5,761,514) describing the idea: "Register allocation method
> and apparatus for truncating runaway lifetimes of program variables
> in a computer system".  I have no idea whether this was one of the
> patents made available by IBM for use by the OSS community or not.

Just FYI, I've read this patent, and regardless of whether you think
this is something should have patented, etc, the claims are broad enough
to cover any way as long as you are doing liveness analysis and then
inserting something into the instruction stream to truncate the ranges
(real, fake, whatever) .

However, if this is what you guys want to do, please don't let that stop
you.  Let me know if you want to go this route, and we'll work on
getting IBM to release it.

--Dan

Re: Problem with the special live analyzer in global alloc

[Peter Bergner]

On Wed, 2005-08-24 at 00:07 -0400, Daniel Berlin wrote:
> I imagine if you have 300k bb's or 1.5 million live pseudos to consider,
> it probably makes a real difference, but that's not *too* common in our
> supported languages (30k bb's/150k pseudos is probably the practical
> upper limit of what we see, though i'm sure someone is going to say
> they've seen larger :P)

I wasn't trying to argue that it's the right answer for GCC, just that
is was useful for the iSeries compiler.  But like you alluded to and
I mentioned, if you go this route, you really need to handle these new
definitions specially otherwise you'll lose optimization opportunities. 

Peter

Re: Problem with the special live analyzer in global alloc

[Daniel Berlin]

On Wed, 2005-08-24 at 08:47 -0500, Peter Bergner wrote:
> On Wed, 2005-08-24 at 00:07 -0400, Daniel Berlin wrote:
> > I imagine if you have 300k bb's or 1.5 million live pseudos to consider,
> > it probably makes a real difference, but that's not *too* common in our
> > supported languages (30k bb's/150k pseudos is probably the practical
> > upper limit of what we see, though i'm sure someone is going to say
> > they've seen larger :P)
> 
> I wasn't trying to argue that it's the right answer for GCC, just that
> is was useful for the iSeries compiler. 

Sure.
I was actually genuinely curious if you thought it would be useful for
other languages that weren't like RPG :)

You do, after all, know a little bit about this stuff :)

Re: Problem with the special live analyzer in global alloc

[Daniel Berlin]

On Tue, 2005-08-23 at 17:06 +0200, Bernd Schmidt wrote:
> Daniel Berlin wrote:
> 
> > If you make them all defined, then it's going to be live where it wasn't
> > before, even though it's not really *used* over those paths.
> 
> The idea is to put the initialization insns only on the paths where the 
> register will be uninitialized.

Again, that will just make the register live over those paths, when it
wasn't before, which makes your information about liveness worse.

IE if you had

int foo(void)
{
int a;

if (blah)
  a = 5;

<use a>
}

and you transform this to:
int foo(void)
{
int a;

if (blah)
  a = 5;
else
  a = 0;

<use a>
}

a is now considered live over both paths of the branch.whereas, with the
partial availability liveness, it will only be considered live over the
path it is actually initialized before use, which is the if branch.

Conservatively initialization will also lead to sets you can't
eliminate, and will generate real code, even if unreachable in practice.

Consider:
int argc;

int foo(void) {
int a;

while (argc--)
  a = <value>

<use a>
}
Because you don't know the value of argc, dataflow will tell you it may
be uninitialized here.
To make it initialized, you'd have to conservatively transform this to:
int a;

a = 0;
while (argc--)
  a = <value>

<use a>

Because you still don't know the value of argc, you won't be able to
remove the a = 0.

Besides not being able to remove them, you have to worry about placement
when it comes to loops.
Consider the  simple nested loops

for i = 1 to 10
{
  while (argv--)
     {
        a = <value>
     }
}
<use a>

If you just "stupidly" place the initializations (IE don't do LCM like
dataflow to determine where they can go), you will transform this into:

for i = 1 to 10
{
  a = 0;
  while (argv--)
     {
        a = <value>
     }
}
<use a>



You could avoid all but the "worse information" problem by tracking
which sets you added, and thus, know you can remove the sets if things
get bad,  since they don't affect the original program.

However, this probably ends up being just as ugly as the partial
liveness stuff.
--Dan

Re: Problem with the special live analyzer in global alloc

[James E Wilson]

On Tue, 2005-08-23 at 07:44, Bernd Schmidt wrote:
> Jim Wilson once suggested we should just emit insns to make sure every 
> register is initialized and be done with it - problem solved.  I had 
> started to work on that, if people think it's a good idea I can dig that 
> stuff out again.

I'd like this because of an IA-64 specific problem.

IA-64 has Not-a-Thing (NaT) bits, which are used for speculation.  If a
speculative load fails, the NaT bit is set, which indicates that we must
refetch the value before using it.  NaT bits propagate through most
operations, allowing us to speculate a series of instructions instead of
just loads.  However, they will generate an illegal instruction
exception if used in an operation with side-effects, like a store.

So the problem here is that any use of an uninitialized register may
generate an exception, if the instruction has side-effects, and the
uninitialized register just happens to have the NaT bit set.

Mostly we get by because gcc doesn't have speculation support yet, but
it is only a matter of time before someone writes it.  Meanwhile, there
are some hand-written glibc routines that do use speculation, and could
potentially trigger this problem.  This is a disaster waiting to happen
for anyone using gcc on IA-64 machines.

I created PR 21111 for this problem, and it contains an artificial
testcase that demonstrates the problem using bitfield assignments.
-- 
Jim Wilson, GNU Tools Support, http://www.specifix.com

Re: Problem with the special live analyzer in global alloc

[Andreas Krebbel]

Hello,

I've opened a bugzilla for this: #24034

Bye,

-Andreas-

Re: Problem with the special live analyzer in global alloc

[Daniel Berlin]

On Fri, 2005-09-23 at 15:50 +0200, Andreas Krebbel wrote:
> Hello,
> 
> I've opened a bugzilla for this: #24034

Just as an FYI, Kenny and I have replaced the global liveness analyzer
with one from df.c, and removed the need for make_accurate_live_analysis
(ie df.c now does the partial avail liveness stuff).

We are currently in the process of changing all the other users of life
analysis to use the df.c liveness, which should solve this problem
(since they will all then use the accurate life analysis).

> 
> Bye,
> 
> -Andreas-

[RFC] Don't emit REG_DEAD for clobbers if reg stays live

[Andreas Krebbel]

Hello,

> Just as an FYI, Kenny and I have replaced the global liveness analyzer
> with one from df.c, and removed the need for make_accurate_live_analysis
> (ie df.c now does the partial avail liveness stuff).
> 
> We are currently in the process of changing all the other users of life
> analysis to use the df.c liveness, which should solve this problem
> (since they will all then use the accurate life analysis).

Good to hear! Unfortunately this will come too late to fix the bug in gcc 
4.1. What about the following workaround? This one could be fine for 
the 4.1.0 release:

Remember the situation after reload. r1 is used for an uninitialized variable
hence it is live from the beginning to the read of the variable.
The special liveness analyzer in global alloc not considering uninitialized 
quantities to conflict with others assigns r1 also to a local pseudo.

bb 1 start: r1 dead
  insn 1: r1 = 0;
  insn 2: use r1; clobber r1; REG_DEAD (r1) !!!
bb 1 end: r1 live

Due to the REG_DEAD note regrename assumes it is safe to rename r1 locally to r5
resulting in:

bb 1 start: r1 live !!!
  insn 1: r5 = 0;
  insn 2: use r5; clobber r5; REG_DEAD (r5)
bb 1 end: r1 live

Because live at start has changed due to a local change an assertion in flow is
triggered.

The cause of the problem is that we already enter regrename with wrong liveness
info which in turn is caused by using a different liveness analyzer in global alloc
than elsewhere.  We have the register r1 live at the end of the basic block but the
last rtx writing this value is a clobber.  This situation should only occur if we had 
overlapping live ranges which were assigned to the same hard reg. Under normal
circumstances this should be considered a bug and an assertion would be the right
choice. But knowing that this could only be caused by the global alloc liveness 
analyzer the flow analyzer should avoid emitting a REG_DEAD note. That way the
value of the uninitialized variable (which is undefined anyway) would be clobbered
what should not cause any trouble.

The attached patch modifies mark_set_1 to consider a CLOBBER a normal SET if the
clobbered register is live afterwards.

So as a rfc what do you (or anybody else) think about the attached patch for 
mainline gcc.

Bootstrapped on i686, s390 and s390x without testsuite regressions.

This patch fixes the 920501-4.c regression on s390x.

Bye,

-Andreas-


2005-10-13  Andreas Krebbel  <krebbel1@de.ibm.com>

	* flow.c (mark_set_1): Handle CLOBBERs like SETs if the register
	is live afterwards.


Index: gcc/flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.635
diff -p -c -r1.635 flow.c
*** gcc/flow.c	22 Aug 2005 16:58:46 -0000	1.635
--- gcc/flow.c	13 Oct 2005 09:25:51 -0000
*************** mark_set_1 (struct propagate_block_info 
*** 2819,2825 ****
  	      else
  		SET_REGNO_REG_SET (pbi->local_set, i);
  	    }
! 	  if (code != CLOBBER)
  	    SET_REGNO_REG_SET (pbi->new_set, i);
  
  	  some_was_live |= needed_regno;
--- 2819,2825 ----
  	      else
  		SET_REGNO_REG_SET (pbi->local_set, i);
  	    }
! 	  if (code != CLOBBER || needed_regno)
  	    SET_REGNO_REG_SET (pbi->new_set, i);
  
  	  some_was_live |= needed_regno;

[RFC] Flow: Handle CLOBBERs like SETs if the reg stays live

[Andreas Krebbel]

I had posted this at first under a somewhat misleading subject (someone could
say completely wrong) - hope that has improved yet ;-)

Hello,

> Just as an FYI, Kenny and I have replaced the global liveness analyzer
> with one from df.c, and removed the need for make_accurate_live_analysis
> (ie df.c now does the partial avail liveness stuff).
> 
> We are currently in the process of changing all the other users of life
> analysis to use the df.c liveness, which should solve this problem
> (since they will all then use the accurate life analysis).

Good to hear! Unfortunately this will come too late to fix the bug in gcc 
4.1. What about the following workaround? This one could be fine for 
the 4.1.0 release:

Remember the situation after reload. r1 is used for an uninitialized variable
hence it is live from the beginning to the read of the variable.
The special liveness analyzer in global alloc not considering uninitialized 
quantities to conflict with others assigns r1 also to a local pseudo.

bb 1 start: r1 dead
  insn 1: r1 = 0;
  insn 2: use r1; clobber r1; REG_DEAD (r1) !!!
bb 1 end: r1 live

Due to the REG_DEAD note regrename assumes it is safe to rename r1 locally to r5
resulting in:

bb 1 start: r1 live !!!
  insn 1: r5 = 0;
  insn 2: use r5; clobber r5; REG_DEAD (r5)
bb 1 end: r1 live

Because live at start has changed due to a local change an assertion in flow is
triggered.

The cause of the problem is that we already enter regrename with wrong liveness
info which in turn is caused by using a different liveness analyzer in global alloc
than elsewhere.  We have the register r1 live at the end of the basic block but the
last rtx writing this value is a clobber.  This situation should only occur if we had 
overlapping live ranges which were assigned to the same hard reg. Under normal
circumstances this should be considered a bug and an assertion would be the right
choice. But knowing that this could only be caused by the global alloc liveness 
analyzer the flow analyzer should avoid emitting a REG_DEAD note. That way the
value of the uninitialized variable (which is undefined anyway) would be clobbered
what should not cause any trouble.

The attached patch modifies mark_set_1 to consider a CLOBBER a normal SET if the
clobbered register is live afterwards.

So as a rfc what do you (or anybody else) think about the attached patch for 
mainline gcc.

Bootstrapped on i686, s390 and s390x without testsuite regressions.

This patch fixes the 920501-4.c regression on s390x.

Bye,

-Andreas-


2005-10-13  Andreas Krebbel  <krebbel1@de.ibm.com>

	* flow.c (mark_set_1): Handle CLOBBERs like SETs if the register
	is live afterwards.


Index: gcc/flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.635
diff -p -c -r1.635 flow.c
*** gcc/flow.c	22 Aug 2005 16:58:46 -0000	1.635
--- gcc/flow.c	13 Oct 2005 09:25:51 -0000
*************** mark_set_1 (struct propagate_block_info 
*** 2819,2825 ****
  	      else
  		SET_REGNO_REG_SET (pbi->local_set, i);
  	    }
! 	  if (code != CLOBBER)
  	    SET_REGNO_REG_SET (pbi->new_set, i);
  
  	  some_was_live |= needed_regno;
--- 2819,2825 ----
  	      else
  		SET_REGNO_REG_SET (pbi->local_set, i);
  	    }
! 	  if (code != CLOBBER || needed_regno)
  	    SET_REGNO_REG_SET (pbi->new_set, i);
  
  	  some_was_live |= needed_regno;