This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [tree-ssa] Speedup alias analysis [patch]
On Tue, 2003-06-24 at 09:43, Diego Novillo wrote:
> On Tue, 2003-06-24 at 08:12, Andrew MacLeod wrote:
> > So you changed SSA->Normal to turn ptr_8 = VDEF <ptr_5> into a copy
> > operation? If'n we were going to do that, we'd be better off forcing the
> > coalesce early when possible, and copying only when necessary.
> >
> Right, and that's exactly what we do. We only emit a copy when the
> variables on either side of the VDEF end up in different partitions.
>
HOw do you know which VDEFs are significant? because there is no real
def of them?
> I thought about trying to force them into the same partition early, but
> I'm not sure that we can know before hand what VDEFs will need to be
> considered. If we tried to force coalescing to every VDEF in the
> program, wouldn't we end up tied up in knots? This is the part I wanted
> to talk with you about.
Yes, we would. All the tables and graphs and everything would be muich
larger for no useful reason most of the time.
>
>
> > I need to see a really good argument for this that I can't refute. And
> > what kind of optimizations are we going to miss?
> >
> Right now we are not handling .GLOBAL_VAR very gracefully, so when we
> have a function call to 'foo (&a, &b)', all references to 'a' and 'b'
> get tossed into virtual operands to .GLOBAL_VAR. I'm working on this
> now. We do have some gains in that the dominator optimization passes
> are able to do more propagate 1% more copies and eliminate 2% more
> redundant expressions.
>
So what does GLOBAL_VARs have to do with mixing virtual and non-virtual
operands? Its going to produce mixes like this which you are
demonstrating?
>
> The only unaliased virtual ops are non-scalar data references. Or you
> mean a must-alias pass? In the first case we need a scalarizer of some
> kind. In the second one, we'd prove that 'p' always points to 'a' and
> replace every reference to '*p' with 'a' directly.
>
The stuff we talked about in ottawa which allows promotion of a VDEF'd
variable to a real one when all its VUSES can be real uses. This allowed
effective live-range splitting of variables into aliasined and
non-aliased parts. Or something to that effect.
> This case is slightly different, we have a may-alias relation between
> 'p' and 'a', so every time we dereference 'p', we'll have a virtual
> operand for 'a', but when we access 'a' directly, we will have a real
> operand for it.
>
> After all, this is exactly the semantics of a VDEF operation. In the
> following function, ignore the fact that we really have a must-alias
> situation:
>
> foo()
> {
> int *p, a;
>
> p = &a;
> *p = 10;
> if (a == 10)
> a++;
> return a;
> }
>
> Using the previous alias analysis, we would've rewritten this function
> into:
>
> foo ()
> {
> int * p, a;
>
> # VUSE <a_2>;
> p_3 = &a;
>
> # a_4 = VDEF <a_2>;
> *p_3 = 10;
>
> # VUSE <a_4>;
> if (a == 10)
> {
> # a_5 = VDEF <a_4>;
> # VUSE <a_4>;
> a = a + 1
> };
> # a_1 = PHI <a_5(1), a_4(2)>;
>
> # VUSE <a_1>;
> return a;
> }
>
> Instead, we now re-write it into:
>
> foo ()
> {
> int * p, a;
>
> # VUSE <a_2>;
> p_3 = &a;
>
> # a_4 = VDEF <a_2>;
> *p_3 = 10;
> if (a_4 == 10)
> {
> a_5 = 11
> };
> # a_1 = PHI <a_5(1), a_4(2)>;
>
> # int_7 = VDEF <int_6>;
> return a_1;
> }
>
>
SO, a couple of things.
First, why isnt the first one
p_3 = &a_2 ?
I thought we were going to expose that into the IL... otherwise
rewriting it is a pain because I have to delve into the stmt to find the
variable to rewrite if a_2 didn't get coalesced with the storage for
'a'.
> Notice that we now generate fewer virtual operands, the meaning of the
> analysis is the same and we can get more optimizations done inside the
> body of the if(). Yes, it's a silly example, but it illustrates the
> idea.
And thats a very good thing.
I have to go to the dentist <drill, whirl, buzz> I'll think about it
whilst Im out.
Andrew