Re: Global variable clobbering and statics

[Daniel Berlin <dberlin at dberlin dot org>]

> 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).

Sometimes, giving up hard is the right thing to do.

> 
> 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.

The GV heuristic is actually wrong in a lot of cases, in part because we
post-process the call-clobbered set a lot right now (IE we don't remove
unmodifiable vars up front, etc).  So it comes up with numbers that are
off quite a lot of the time (on the high side).

There are other reasons it's wrong, that's just something i noticed when
comparing the estimate the heuristic came up with with the actual
numbers that we now print as stats on the improved-aliasing-branch.

> 
> (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.

Yeah, this is a problem, but it's easy to fix, i *think*. :)

> 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.

> 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.

LLVM actually does something like this to make their alias analysis
faster.
They come up with global equivalence sets, because they won't be able to
discern the difference between certain globals anyway.
This seems like the natural thing to do in such a situation.

> 
> 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?

Personally, i think there is no good solution in some cases, and we
should just give up, for the testcases in the PR :)
I believe that grouping GV in some cases will do okay there for medium
size problems in speed and size.

The only real global var optimization we get these days is from
single-function "heavy global var users", SFT's for global vars causing
propagation of some sort, or luck.

You really can't get any good global var optimization without
whole-program anyway, since they always escape.