[llvm-dev] Fwd: Deterministic function return attribute

Sanjay Patel via llvm-dev llvm-dev at lists.llvm.org
Fri Aug 14 06:23:51 PDT 2020


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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200814/4f78d7a9/attachment.html>


More information about the llvm-dev mailing list