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