[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