[llvm-dev] Fwd: Deterministic function return attribute

[László Radnai via llvm-dev]

(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!

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...)

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)?

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'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...

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.

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
>
>