Re: should MEM tracking be able to optimize this?

[Daniel Berlin <dan@cgsoftware.com>]

On Saturday, November 17, 2001, at 05:16  PM, Zack Weinberg wrote:

> On Fri, Nov 16, 2001 at 12:47:30PM -0800, Dan Nicolaescu wrote:
>>
>> The following 2 functions should generate very similar assembly, right?
> ...
>
> This is purely a sticking-my-nose-in comment, but I looked into it
> briefly and it does appear to be a genuinely hard problem with our
> intermediate representation.
Well, at the RTL level, yes.
At the tree level, in the ast-optimizer branch, it's not that  difficult 
to implement.

> At the RTL level, loads and stores in calc1 look like
>
> (insn 45 43 47 (set (reg:SF 123)
>         (mem/s:SF (plus:SI (reg/f:SI 111)
>                 (reg:SI 115)) [4 A S4 A32])) -1 (nil)
>     (nil))
>
> where in calc2 they look like
>
> (insn 85 83 86 (set (reg:SF 150)
>         (mem/s:SF (plus:SI (reg/f:SI 145)
>                 (reg:SI 148)) [4 p S4 A32])) -1 (nil)
>     (nil))
>
> alias.c uses the information in square brackets to make decisions
> about whether memory refs can conflict.  [4 A S4 A32] means alias set
> 4, variable 'A', unit size 4 (bytes), alignment 32 (bits).
>
> In theory, if we had a thing we could stick into that structure that
> meant "A.p" instead of "A", that would be enough to get identical
> assembly for both loops.
No, it wouldn't.
Think of unions, for instance.
It's not that simple to differentiate between field accesses, and 
whether two given field accesses overlap.  This is partially because 
it's impossible to precisely compute may and must-alias relations in C 
(See "Undecidability of static analysis" by William Landi, or "The 
undecidability of aliasing" by G. Ramalingam).


>   The trouble is that we don't.
>
This is because you'd need an access path or something (see papers on 
non-type based alias analysis, or Muchnick's advanced compiler design 
and implementation) that can properly take into account pointer 
dereferencing, address taking, field accesses, etc. Where properly means 
"conservative enough to not get it wrong".

I've actually done an implementation of this for GCC at the tree level, 
based on an incremental interprocedural alias analysis algorithm.  This 
is one thing i needed tree serialization for.


> At the tree level there is enough information to be clear what is
> going on: the C expression "A.f[i]" becomes this tree:
>
>  <array_ref
>     arg 0 <component_ref
>         arg 0 <var_decl A>
>         arg 1 <field_decl f>
>     arg 1 <var_decl i>>
>
> (This is a brutally trimmed down version of what you'd get if you
> called debug_tree() on the expression node.)
>
> The tree expansion routines eventually call get_inner_reference()
> which transforms that into a (decl, offset) pair:
>
>  <var_decl A>
>
>  <mult_expr
>     arg 0 <var_decl i>
>     arg 1 <integer_cst 4>>
>
> If we'd asked it for A.p[i] instead, the offset would be something
> like <plus <mult <var i> <constant 4>> <constant 8192>> instead.
>
> The "variable" slot of [4 A S4 A32] is, in fact, <var_decl A> as
> returned by get_inner_reference.  Here's the rub: you might think that
> it would work to put <field_decl f> there instead, but FIELD_DECLs are
> unique to the type; all instances of a structure of that type use the
> same <field_decl f>.
>
> It might conceivably work to use <component_ref <var A> <field f>> in
> that slot.  However, I do not believe that COMPONENT_REFs are unique;
> if you refer to A.f twice you'll probably get two trees in memory, and
> that would defeat the simple address comparison currently being done
> by alias.c.
>   They could be _made_ unique, or alias.c could look more
> deeply, but that would be More Work Than I Have Time For (tm).
>
This wouldn't solve the problem of unions, etc.  You need an alias 
analysis algorithm that uses access paths or something (There are other 
ways than access paths, however most recent alias analysis algorithms 
i've seen use them, or some variant of them) that can differentiate 
between pieces of fields, etc.
These can get expensive, depending on how precise they are (and whether 
they are interprocedural or not).



> I do think that we should be able to do this optimization; perhaps
> I'll stick these notes onto the projects page for someone who wants to
> pick up the ball.
>
This optimization is known as scalar replacement of aggregates, BTW.
You need to also take care to pin down variables over function calls, 
etc, unless you use an interprocedural algorithm that can take these 
into account when computing the alias sets.

If you do in the alias analysis algorithm, it makes later elimination 
much simpler, but your alias sets bigger.


> zw