llvm dev - May 2008 - [LLVMdev] Iterator protocols

Am Freitag, den 16.05.2008, 06:54 -0700 schrieb Chris
Lattner:
> On May 13, 2008, at 4:09 PM, Gordon Henriksen wrote:
> 
> > On May 13, 2008, at 18:28, Dan Gohman wrote:
> >
> > I wonder if it would be worthwhile to have a flag on loads to mark
> > them as immutable. A flag from the source language stating "this
load
> > never aliases any subsequent store." A majority of loads in
functional
> > languages are of this nature. I could see a number of benefits:
> >
> > • Duplicate loads could be RAUW'd based solely on SSA properties.
> > • load / store alias analysis could be short-circuited for such loads.
> > • Codegen could remat such loads under register pressure.
> > • Vtable lookups through loop-invariant SSA vars could trivially be
> > shown to be themselves loop-invariant.
> 
> This is very interesting.  If there is a use-case that this sort of  
> thing would strongly benefit, then we could add it.
Any tight loop that uses a virtual function.
That's interesting for languages where functions are virtual by default.
(I think OO language designers tend to avoid nonvirtual functions in
general.)

Note that functional language tend to have the moral equivalent of
virtual functions, too, but I don't know how strong the effect would be.

Regards,
Jo

On May 16, 2008, at 7:50 AM, Joachim Durchholz wrote:
>
> Am Freitag, den 16.05.2008, 06:54 -0700 schrieb Chris Lattner:
>> On May 13, 2008, at 4:09 PM, Gordon Henriksen wrote:
>>
>>> On May 13, 2008, at 18:28, Dan Gohman wrote:
>>>
>>> I wonder if it would be worthwhile to have a flag on loads to mark
>>> them as immutable. A flag from the source language stating
"this
>>> load
>>> never aliases any subsequent store." A majority of loads in  
>>> functional
>>> languages are of this nature. I could see a number of benefits:
>>>
>>> • Duplicate loads could be RAUW'd based solely on SSA
properties.
>>> • load / store alias analysis could be short-circuited for such  
>>> loads.
>>> • Codegen could remat such loads under register pressure.
>>> • Vtable lookups through loop-invariant SSA vars could trivially be
>>> shown to be themselves loop-invariant.
>>
>> This is very interesting.  If there is a use-case that this sort of
>> thing would strongly benefit, then we could add it.
>
> Any tight loop that uses a virtual function.
> That's interesting for languages where functions are virtual by  
> default.
> (I think OO language designers tend to avoid nonvirtual functions in
> general.)
This isn't safe in C++ for example.

Also, the proposed definition wouldn't permit hoisting one of these  
loads out of a loop.

-Chris

On May 16, 2008, at 10:55, Chris Lattner wrote:
>
> On May 16, 2008, at 7:50 AM, Joachim Durchholz wrote:
>
>>
>> Am Freitag, den 16.05.2008, 06:54 -0700 schrieb Chris Lattner:
>>> On May 13, 2008, at 4:09 PM, Gordon Henriksen wrote:
>>>
>>>> On May 13, 2008, at 18:28, Dan Gohman wrote:
>>>>
>>>> I wonder if it would be worthwhile to have a flag on loads to
mark
>>>> them as immutable. A flag from the source language stating
"this
>>>> load
>>>> never aliases any subsequent store." A majority of loads
in
>>>> functional
>>>> languages are of this nature. I could see a number of benefits:
>>>>
>>>> • Duplicate loads could be RAUW'd based solely on SSA
properties.
>>>> • load / store alias analysis could be short-circuited for such
>>>> loads.
>>>> • Codegen could remat such loads under register pressure.
>>>> • Vtable lookups through loop-invariant SSA vars could
trivially be
>>>> shown to be themselves loop-invariant.
>>>
>>> This is very interesting.  If there is a use-case that this sort of
>>> thing would strongly benefit, then we could add it.
>>
>> Any tight loop that uses a virtual function.
>> That's interesting for languages where functions are virtual by
>> default.
>> (I think OO language designers tend to avoid nonvirtual functions in
>> general.)
>
> This isn't safe in C++ for example.
>
> Also, the proposed definition wouldn't permit hoisting one of these
> loads out of a loop.

Right, so that's not really ideal. The reason for the semantic I  
described is to avoid doing something obviously stupid like promoting  
the load above the store here:

     word *foo = gcalloc(1);
     foo[0] = f();
     // foo.bar is now initialized and will never be changed.
     word x = __immutable_load(foo[0]);

Which is approximately the obvious translation of x = { foo_bar = f  
() }.foo_bar in Ocaml, for instance. If instead foo got a new SSA name  
after it was initialized, then the ordering restriction could be  
eliminated:

     word *tmp = gcalloc(1);
     tmp[0] = f();
     word *foo = initialized(tmp);
     word x = __immutable_load(foo[0]);

A crude sledgehammer to accomplish that would be to provide a "Foo  
constructor" function (word *foo = make_block(f());) and not provide  
the body until link time in order to prevent inlining. Maybe if it  
proves useful an ‘SSA rename’ intrinsic (slotted in at 'initialized'  
above) could be added.

I expect this would generate recursive simplifications where the  
language permits such (as C++ doesn't). But Java/.NET string and array  
lengths are candidates, and it might also apply to final or readonly  
fields in Java or C#; I don't remember whether those suffer from the  
same problems as C++ initializers.

But I think I'd have to rearchitect my ocaml compiler to handle an  
earlier IR in order to take advantage of this property, and PR1917  
would have to be fixed as well, so I probably won't contribute here  
any time soon. :(

Now that I think about it, there's a related problem when the object  
is disposed:

     word x = __immutable_load(foo[0]);
     free(foo);

Can't sink the load below the free. So I think the semantics required  
would probably cripple this for any language without GC.

— Gordon