[llvm-dev] Fwd: Deterministic function return attribute
Johannes Doerfert via llvm-dev
llvm-dev at lists.llvm.org
Fri Aug 14 06:47:34 PDT 2020
Oh right, errno! For that one (and similar situations) I was hoping to
eventually
introduce something like: `global_accs({@errno, @data})`.
The idea is to list the globals you access with the understanding
you do not access other data. Potentially we need `globals_and_argmemonly`
as well.
FWIW, AAMemoryLocation in the Attributor already tracks this information
such
that other AAs can use it, it just doesn't manifest it due to the lack of an
IR spelling ;)
On 8/14/20 8:23 AM, Sanjay Patel wrote:
> I haven't looked closely at the grid of attribute possibilities, but this
> reminds me of:
> http://bugs.llvm.org/PR46773
>
> So if we're looking for motivating cases for a "pure" or similar attribute,
> it's most of the C/C++ math library (when errno is in play)?
>
> On Thu, Aug 13, 2020 at 9:43 PM Johannes Doerfert via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi László,
>>
>> On 8/13/20 5:21 PM, László Radnai via llvm-dev wrote:
>> > (Sorry I clicked reply instead of reply to all)
>> > I'm fighting with my email client, I hope the quoted text contains
>> > what I want it to contain.
>> >
>> > ---------- Forwarded message ----------
>> > From: László Radnai <radlaci97 at gmail.com>
>> > Date: Fri, 14 Aug 2020 00:11:35 +0200
>> > Subject: Re: [llvm-dev] Deterministic function return attribute
>> > To: Johannes Doerfert <johannesdoerfert at gmail.com>
>> >
>> > Johannes,
>> >
>> > Thanks for clarifying. Your answer was really useful for me!
>>
>> Glad to help, let's try to figure this one out too ;)
>>
>>
>> > I think I've mixed these up (and that explains why I haven't been able
>> > to find some things on the docs I've remembered...)
>>
>> Yeah, the docs,.. feel free to propose patches to improve them and put
>> me as a reviewer ;)
>>
>>
>> > Though one question interests me: what attributes can be given to a
>> > lazy-init singleton or memoized function (which do access memory, but
>> > does not change output and has no visible side-effects)?
>>
>> Short answer: None (right now).
>>
>> Long answer:
>> There are optimizations that exploit such behavior (or at least similar
>> behavior) already. IPSCCP and there is an Attributor patch that I lost
>> track of a while ago. However, that does not mean we couldn't create an
>> attribute for this. I'm confident there is a reasonable way to define
>> it, the question is how we would use it. I guess we can teach
>> inst combine and such passes about it, but then the question is: is it
>> worth it? There are two cases two consider, and so far I'm unsure if
>> either justifies this:
>> 1) The function is a definition, so we analyze it, deduce the
>> attribute, and passes simplify calls to it. So far, so good.
>> Though, in this scenario it is likely that we inline the function.
>> The attribute would be gone, but we can still optimize subsequent
>> "bodies" as we basically see the assignment and the subsequent load
>> + compare.
>> 2) The function is a declaration, so no deduction is possible and we
>> require the attribute to be provided in the input. Usefulness is
>> given in this case but it is unclear to me if we can expect people
>> to annotate their code. That said, I'm still hoping this will soon
>> become a viable alternative to LTO:
>>
>> https://www.youtube.com/watch?v=elmio6AoyK0&list=PL_R5A0lGi1AAxLTNN21BA0w8CA_xDR0F8&index=14&t=6s
>>
>>
>>
>> > Examples:
>> >
>> > ```
>> > static Type* data;
>> >
>> > Type* getXInstance(){
>> > if (data==nullptr)
>> > data = new Type();
>> > return data;
>> > }
>> > ```
>> >
>> > or with `static Type* data` inside the function (I don't know whether
>> > LLVM makes a distinction, haven't had the time to check.)
>> >
>> > For the memoized function, an example:
>> >
>> > static int memo[100];
>> >
>> > int fib(int n){
>> > llvm.assume(0 <= n && n<=100);
>> > if (memo[n] != 0) {
>> > return memo[n];
>> > }
>> > if (n == 0) {
>> > return memo[n] = 1;
>> > }
>> > return memo[n] = fib(n-1) + fib(n-2);
>> > }
>> >
>> > My goal would be the same: instruction combining. There are memory
>> > accesses, but considering(assuming) only this function accessey the
>> > memory and the output is deterministic (for both cases).
>> >
>> > Whether the optimization kicks in (as I will check later), the
>> > question is either (i) what attributes can communicate this property,
>> > or (ii) how can I achieve such optimizations? Is there some previous
>> > work on this? Is this available in gcc?
>>
>> I don't know much about gcc, sorry ;)
>>
>>
>>
>> > I'm not even sure what would be needed for this property to hold, but
>> > memory access is too strong property.
>> >
>> > If it only accesses function-internal (does not alias with anything
>> > from any other function) memory...? Well, it could store state, not
>> > cache results... So it does not guarantee deterministic outputs...
>>
>> First thing is to define what uses cases should be addressed. The above
>> are two but we need to be precise about the surrounding code. Let's
>> assume no other uses of the memory exist, then we derive nice properties
>> for the functions. Though, it might be worth to consider defining
>> properties for such kind of memory instead ;)
>>
>> I have ideas but I'll think about this first and let you know. Feel free
>> to brainstorm ideas (on the list or just via email to me if you prefer).
>>
>>
>> > My motive (maybe clarifying this helps a bit): I'm interested in the
>> > internal workings of a compiler and how smart can a compiler can be,
>> > for fun. Secondarily, tocommunicate with the optimizer when writing in
>> > C.
>>
>> I would also like to improve the communication/interface, believe me...
>> In addition to talk above, I'd also recommend to look at
>> http://lists.llvm.org/pipermail/llvm-dev/2019-December/137632.html
>> and the `assume` directive we added to OpenMP 5.1:
>> https://www.openmp.org/wp-content/uploads/openmp-TR8.pdf
>>
>>
>>
>> ~ Johannes
>>
>>
>> > Thanks, László
>> >
>> > On 8/13/20, Johannes Doerfert <johannesdoerfert at gmail.com> wrote:
>> >>
>> >> Hi László,
>> >>
>> >> On 8/13/20 6:23 AM, László Radnai via llvm-dev wrote:
>> >> > Hi!
>> >> >
>> >> > I'm interested in what attributes in LLVM mean, specifically how to
>> >> > say that the result is always the same for the given input
>> parameters.
>> >> >
>> >> > The main thing would be to merge two calls with the same parameters
>> >> > when the function is declared but not defined. (just like two
>> stores).
>> >> > I'll call this property mergability.
>> >> >
>> >> > %1 := call @test(%0)
>> >> > %2 := call @test(%0)
>> >> >
>> >> > and the optimization would be something like
>> (%2).replaceUsesWith((%1)).
>> >> >
>> >> > I think it's related to speculatable & readnone in LLVM, (if I
>> >> > understood well, it's the same as GCC's __attribute__((pure)),
>> but I'm
>> >> > not sure whether there are edgecases where the mergability is not
>> >> > equivalent.
>> >> >
>> >> > I've seen somewhere that maybe malloc has these attributes, but it
>> >> > surely cannot be merged. This is because there is memory
>> read/written
>> >> > that cannot be seen by LLVM (which is accepted by readnone). This
>> >> > would be a counter-example.
>> >> >
>> >> > So my question is:
>> >> > Is mergability equivalent to the readnone+speculatable attribute?
>> >> > If not, is there some attribute that should help?
>> >> >
>> >> > And also, does malloc have (or rather, could malloc have) these
>> >> attributes?
>> >>
>> >> Some thoughts, you let me know if this is helpful:
>> >>
>> >> same input -> same output; this is basically an implication of
>> >> `readnone`, or `readonly` without intermediate modifications.
>> >> It is already happening as you would expect it to, I think in inst
>> >> combine but I didn't check: https://godbolt.org/z/hnY71v
>> >>
>> >> `speculatable` means it is `readnone` and doesn't cause UB. As a
>> >> consequence it is allowed to eagerly execute the function. `readnone`
>> >> (aka `__attribute__((const))`) is not sufficient because of things like
>> >> this: `int pure_div(int a, int b) { return a / b; }`
>> >> While there is certainly no memory access or anything else that would
>> >> make it not only depend on the arguments, you cannot hoist a call to
>> >> `pure_div` out of a conditional like `if (b != 0) r = pure_div(a, b);`.
>> >>
>> >> `readnone` does *not* allow accesses to memory that "cannot be seen by
>> >> LLVM". We have `inaccessiblememonly` for that.
>> >>
>> >> Please follow up with questions :)
>> >>
>> >> ~ Johannes
>> >>
>> >>
>> >> > Thanks, László
>> >> > _______________________________________________
>> >> > LLVM Developers mailing list
>> >> > llvm-dev at lists.llvm.org
>> >> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> >>
>> >>
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > llvm-dev at lists.llvm.org
>> > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
More information about the llvm-dev
mailing list