llvm dev - Aug 2009 - [LLVMdev] A create-distinct-item function with no (other) side effects

On Fri, Aug 28, 2009 at 3:47 PM, Nick Lewycky<nlewycky at google.com>
wrote:
>
>
> 2009/8/28 Kenneth Uildriks <kennethuil at gmail.com>
>>
>> This is by design, of course, (CreateDistinctItem does not return the
>> same value given the same caller-visible global state) but I see no
>> way to declare a function that:
>>
>> 1. Returns a distinct item each time it's called,
>
> Attach a 'noalias' attribute to the return type in your function
> declaration. See http://llvm.org/docs/LangRef.html#paramattrs
>
>>
>> 2. Doesn't need to be called at all if its return value from that
call
>> isn't used, and
>> 3. Doesn't even need to be declared if its return value is *never*
used.
>
> Thus far these still need a custom pass. It shouldn't be too hard
though.
> See http://wiki.llvm.org/HowTo:_Find_all_call_sites_of_a_function
>
> You're the second user I know of to ask for this. We should probably
come up
> with a general solution of some sort.
Conceptually, it's the same as "readonly" except that the
requirement
that it return the same value each time is dropped.  It would also
help optimize away calls to "random" in some cases.  I understand that
adding a new function attribute to IR is not trivial, though.  Thanks
for the confirmation.

My front-end is writing LLVM calls into the output module, and JITting
it as part of the compile process so it can create runtime code, and
allowing compiled code to optionally call functions exposing those
same LLVM calls to do its own runtime JITting.  I'm finding lots of
uses for that setup, at both compiletime and runtime, but when the
compiled code doesn't actually JIT anything at runtime, optimizing
away all those LLVM calls along with the LLVM library extern function
declarations would make the resulting .s files have *much* lighter
linking requirements and be easier to package and distribute.  I guess
a custom pass that's part of my compiler project would be the way to
go.
>
> Nick
>
>>
>> If I happen to know about CreateDistinctItem at build time, I can
>> write a custom pass, of course, but I was wondering if there was an
>> easier way to get the standard optimizers to recognize it, or if
y'all
>> think it's worthwhile to add an easier way.
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

On Fri, Aug 28, 2009 at 5:56 PM, Kenneth Uildriks<kennethuil at gmail.com>
wrote:
> It would also
> help optimize away calls to "random" in some cases.
If you're talking about the Unix random(), it does has visible side
effects, specifically related to the guarantee that an srandom call
followed by N random() calls will always produce the same sequence of
N numbers.

-Eli

On Fri, Aug 28, 2009 at 8:49 PM, Eli Friedman<eli.friedman at gmail.com>
wrote:
> On Fri, Aug 28, 2009 at 5:56 PM, Kenneth Uildriks<kennethuil at
gmail.com> wrote:
>> It would also
>> help optimize away calls to "random" in some cases.
>
> If you're talking about the Unix random(), it does has visible side
> effects, specifically related to the guarantee that an srandom call
> followed by N random() calls will always produce the same sequence of
> N numbers.
>
> -Eli
>
I see... that would not be a candidate for this hypothetical function
attribute then.  Although, more secure (and expensive) versions that
guarantee the opposite, a non-repeating and
practically-impossible-to-predict sequence, could benefit from this.

Kenneth Uildriks wrote:
> On Fri, Aug 28, 2009 at 3:47 PM, Nick Lewycky<nlewycky at google.com>
wrote:
>>
>> 2009/8/28 Kenneth Uildriks <kennethuil at gmail.com>
>>> This is by design, of course, (CreateDistinctItem does not return
the
>>> same value given the same caller-visible global state) but I see no
>>> way to declare a function that:
>>>
>>> 1. Returns a distinct item each time it's called,
>> Attach a 'noalias' attribute to the return type in your
function
>> declaration. See http://llvm.org/docs/LangRef.html#paramattrs
>>
>>> 2. Doesn't need to be called at all if its return value from
that call
>>> isn't used, and
>>> 3. Doesn't even need to be declared if its return value is
*never* used.
>> Thus far these still need a custom pass. It shouldn't be too hard
though.
>> See http://wiki.llvm.org/HowTo:_Find_all_call_sites_of_a_function
>>
>> You're the second user I know of to ask for this. We should
probably come up
>> with a general solution of some sort.
> 
> Conceptually, it's the same as "readonly" except that the
requirement
> that it return the same value each time is dropped.  It would also
> help optimize away calls to "random" in some cases.  I understand
that
> adding a new function attribute to IR is not trivial, though.  Thanks
> for the confirmation.
Are you sure? What if you had a malloc which lets you view the number of 
bytes allocated thus far? Presumably, you don't even know the 
implementation of the allocator that CreateDistinctItem is calling and 
whether it might expose functions that other LLVM methods can see. What 
if the allocator was compiled to bitcode and LLVM sees the pointers it 
stores as just flat pointers?

What you've got is a case where the state appears to be entirely private 
to this function and you happen to know (or, you believe) that there 
isn't any way for your program to get at its private state.

At work, not only do we have a custom allocator, it supports pluggable 
extensions. And we've got programs that use them.

We want something a little more advanced than a simple function 
attribute. There's a set of functions which can directly see the same 
state (malloc's privates, or random's entropy pool) and nobody off of 
that whitelist can. At the moment, there's no way to write an 
AliasAnalysis which expresses that.
> My front-end is writing LLVM calls into the output module, and JITting
> it as part of the compile process so it can create runtime code, and
> allowing compiled code to optionally call functions exposing those
> same LLVM calls to do its own runtime JITting.  I'm finding lots of
> uses for that setup, at both compiletime and runtime, but when the
> compiled code doesn't actually JIT anything at runtime, optimizing
> away all those LLVM calls along with the LLVM library extern function
> declarations would make the resulting .s files have *much* lighter
> linking requirements and be easier to package and distribute.  I guess
> a custom pass that's part of my compiler project would be the way to
> go.
Unused extern function declarations can be optimized away with the 
-strip-dead-prototypes pass.

Nick
>> Nick
>>
>>> If I happen to know about CreateDistinctItem at build time, I can
>>> write a custom pass, of course, but I was wondering if there was an
>>> easier way to get the standard optimizers to recognize it, or if
y'all
>>> think it's worthwhile to add an easier way.
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

On Sat, Aug 29, 2009 at 2:34 AM, Nick Lewycky<nicholas at mxc.ca>
wrote:
> Kenneth Uildriks wrote:
>>
>> On Fri, Aug 28, 2009 at 3:47 PM, Nick Lewycky<nlewycky at
google.com> wrote:
>>>
>>> 2009/8/28 Kenneth Uildriks <kennethuil at gmail.com>
>>>>
>>>> This is by design, of course, (CreateDistinctItem does not
return the
>>>> same value given the same caller-visible global state) but I
see no
>>>> way to declare a function that:
>>>>
>>>> 1. Returns a distinct item each time it's called,
>>>
>>> Attach a 'noalias' attribute to the return type in your
function
>>> declaration. See http://llvm.org/docs/LangRef.html#paramattrs
>>>
>>>> 2. Doesn't need to be called at all if its return value
from that call
>>>> isn't used, and
>>>> 3. Doesn't even need to be declared if its return value is
*never* used.
>>>
>>> Thus far these still need a custom pass. It shouldn't be too
hard though.
>>> See http://wiki.llvm.org/HowTo:_Find_all_call_sites_of_a_function
>>>
>>> You're the second user I know of to ask for this. We should
probably come
>>> up
>>> with a general solution of some sort.
>>
>> Conceptually, it's the same as "readonly" except that the
requirement
>> that it return the same value each time is dropped.  It would also
>> help optimize away calls to "random" in some cases.  I
understand that
>> adding a new function attribute to IR is not trivial, though.  Thanks
>> for the confirmation.
>
> Are you sure? What if you had a malloc which lets you view the number of
> bytes allocated thus far? Presumably, you don't even know the
implementation
> of the allocator that CreateDistinctItem is calling and whether it might
> expose functions that other LLVM methods can see. What if the allocator was
> compiled to bitcode and LLVM sees the pointers it stores as just flat
> pointers?
>
> What you've got is a case where the state appears to be entirely
private to
> this function and you happen to know (or, you believe) that there isn't
any
> way for your program to get at its private state.
Or you know up front that you don't *want* your program accessing its
private state.

(In the particular case I'm thinking of, my program calls
LLVMOpaqueType().  Every time it does, it's supposed to get a distinct
opaque type instance.  But it never dereferences the pointer it gets
back, or does anything to it other than compare it for equality with
other typerefs or pass it back to other LLVM functions.)

When you declare an external function, you can adjust its attributes
according to how that particular Module interacts with the function,
right?  (What happens if you link together two Modules that import the
same function and give it different attributes?)
>
> At work, not only do we have a custom allocator, it supports pluggable
> extensions. And we've got programs that use them.
>
> We want something a little more advanced than a simple function attribute.
> There's a set of functions which can directly see the same state
(malloc's
> privates, or random's entropy pool) and nobody off of that whitelist
can. At
> the moment, there's no way to write an AliasAnalysis which expresses
that.
Hmmm.... what if you put all the whitelist functions into one Module,
and other functions outside that Module?
>
>> My front-end is writing LLVM calls into the output module, and JITting
>> it as part of the compile process so it can create runtime code, and
>> allowing compiled code to optionally call functions exposing those
>> same LLVM calls to do its own runtime JITting.  I'm finding lots of
>> uses for that setup, at both compiletime and runtime, but when the
>> compiled code doesn't actually JIT anything at runtime, optimizing
>> away all those LLVM calls along with the LLVM library extern function
>> declarations would make the resulting .s files have *much* lighter
>> linking requirements and be easier to package and distribute.  I guess
>> a custom pass that's part of my compiler project would be the way
to
>> go.
>
> Unused extern function declarations can be optimized away with the
> -strip-dead-prototypes pass.
Yes, as long as initialization code that calls them also gets
optimized away when the globals they populate never get read at
runtime.  If the functions are assumed to have side-effects, those
calls remain and so do the extern function declarations.