Re: Global variable clobbering and statics

[Diego Novillo <dnovillo at redhat dot com>]

On Tuesday 11 October 2005 22:16, Daniel Berlin wrote:
> On Tue, 2005-10-11 at 20:44 -0400, Diego Novillo wrote:
> > On Tuesday 11 October 2005 20:30, Daniel Berlin wrote:
> > > BTW, you are also screwing up the upwards fud-chains in cases where
> > > it really does clobber A, since you'll get the exact same as above,
> > > and thus, A_1 won't be linked to the may-def at the clobber site,
> > > but to the "real def" that last occurs.
> >
> > No.  Without GV, there *will* be a VMD for A at the call to foo().
>
> Uh, no, no there won't.
> Look at get_call_expr_operands, at the not_read/not_written stuff.
>
You snipped too much from our original conversation.  For the benefit of 
the list, the original code was:

static int a;
int q;
static int foo ()
{
  *q = 5;
  return *q;
}
 

int main(void)
{
   a = 6;
   foo ();
   printf ("%d\n", a);
}

(I suppose you meant 'int *q', but that's OK).  I said that if we decide 
*not* to use .GLOBAL_VAR (GV), we would get a V_MAY_DEF for 'a' at the 
call to foo().  The IPA info for 'a' better not think that foo() is 
harmless to 'a'.  In cases where foo() does nothing to 'a', yes I agree 
'a' will not get a VMD, and that's the whole point behind the global 
static opts.

> The ipa-reference info will say it isn't clobbered by the call to foo.
> Thus, we normally won't add a VMD for it.
> You will get exactly the representation i sent you, without GV's.  I
> checked it before i sent it to you :).  This is, after all, why the
> static clobber avoidance stuff was implemented
>
I'm puzzled.  Why do you think this is related at all to the problem I'm 
trying to fix?  I am not actively trying to break the global statics 
optimization.  I am only trying to improve our handling of .GLOBAL_VAR.  
Once .GLOBAL_VAR is involved, both global static optimization and per-site 
clobbering are disabled.  And that is just a natural side-effect of 
grouping call-clobbered variables.

> Just to publicly followup on the original email, I think that for the PR
> in question, The single var (IE just GV everywhere) scheme works better
> than what you plan on, for the following reasons:
> 
> 1. The single var scheme, while losing all optimization for global
> variables, is correct in the FUD chains. ?Every def is linked to the
> nearest redef site, and if you walked them, they are conservatively
> correct.
>
Yes, that is true.  However,  I am looking for graceful degradation 
mechanisms, while trying to keep SSA semantics.  I would like to be able 
to trigger grouping mechanisms both in call-clobbering and aliasing 
without just Giving Up Hard.  To add insult to injury, we give up too late 
(as one of the test cases in this PR shows).

Two things happen currently:

(1) We have set .GLOBAL_VAR's threshold way too high.  We obviously need to 
lower it, but that would penalize large-and-not-necessarily-ridiculous 
programs, so I'm trying to find that balance.  If we had a more graceful 
grouping mechanism, we could give up and not worry too much about it.

(2) We are modelling .GLOBAL_VAR as an alias of the call-clobbered 
variables.  Convenient but unnecessarily slow.  Both problems are 
orthogonal and this one may be easy to fix for 4.1.

There is a third problem, actually.  We are trigger-happy when marking 
call-clobbered symbols.  You are fixing that on the alias branch, so this 
will be less of a problem soon.

> This seems wonky, and is sure to confuse people :).
>
Exactly.  As I stated in http://gcc.gnu.org/ml/gcc/2005-03/msg00604.html
this is precisely what I don't like about the scheme.
 
> Also, since it's just the same as the above, why bother wasting memory
> with more vuses?  You still need phis for the GV's in some cases, you
> can't avoid that, but why not just add an extra int somewhere to
> represent the global version number instead of a whole new vop per
> statement?  Seems like if you are trying to make things save
> memory/faster, that would be the way to go.
>
That's even more intrusive.  You can't associate that number to the SSA 
name and you still have the problem of SSA_NAME_DEF_STMT pointing to the 
store that generated it, not the function.  Say you have

	foo ()
	# VUSE <X_3>
	... = X

	bar ()
	# VUSE <X_3>
	... = X

The idea with the VUSE of .GLOBAL_VAR  (.GV) was to block optimizations 
across the function call:

	# .GV_9 = V_MAY_DEF <.GV_8>
	foo ()

	# VUSE <X_3>
	# VUSE <.GV_9>
	... = X

	# .GV_10 = V_MAY_DEF <.GV_9>
	bar ()

	# VUSE <X_3>
	# VUSE <.GV_10>
	... = X

The two VUSEs of X_3 do not have the same value number, so optimizations 
would be prevented from doing anything.  If you wanted to avoid emitting a 
VUSE for .GV everywhere, you'd have to encode it in the statement itself.  
At that point, you are asking optimizers to check that explicitly, instead 
of doing the standard loop collecting VUSEs.

I had other schemes in mind, one using two SSA version numbers for global 
variables (this one in particular would have gotten me lynched).  But they 
all have problems of their own.  Mostly, we need to avoid creating many 
new SSA names, that's what gets us into most trouble.
Andrew had another idea in http://gcc.gnu.org/ml/gcc/2005-03/msg00848.html
but he did not particularly care for it either.

So far, the only approach I've come up with that shows some promise is to 
expand on the FIXME note I added a long time ago in 
maybe_create_global_var, and you and Andrew mentioned as well.  Have 
several .GLOBAL_VARs representing different call-clobbered variables.

We can group them aribtrarily.  For instance, we could use types.  But we 
could also use a simple distance heuristic: group under the same .GV all 
the symbols that are used "far appart".  It's easy to get carried away 
here, too.  But it should be possible to find something quick, we already 
have the set of call-clobbered variables and have information about where 
they're used in the program.  This is clearly a 4.2 item.

For 4.1, I will fix #2 above and lower the threshold for .GLOBAL_VAR.  
500,000 is a bit too large.  I'd love to find a good solution for problem 
#1 that doesn't just cause us to Give Up.

Thoughts?  Suggestions?