[RFC] Memory region declaration intrinsic

Hi all.

Differential: ⚙ D115274 [IR][RFC] Memory region declaration intrinsic

This is a follow-up to the "[llvm-dev] [RFC] Adding range metadata to
array subscripts.",
https://lists.llvm.org/pipermail/llvm-dev/2021-March/149390.html

Problem statement:

As per C 6.5.6p9 / [expr.add], given

struct S {
    int a[3];
    int b[3];
    int c[3];
};

void bar(int*);

void foo(S* s) {
  bar(&s.b[1]);
}

even though the pointer the bar receives has 4 ints to the left of it
and 4 to the right of it, the only ints it can access are
one to the left and one to the right. I.e. it can not go outside of the S::b.

But, there is currently no way to encode that knowledge into LLVM IR.
There's limited `inrange` thing for constant expression GEP's,. since:
* https://reviews.llvm.org/D22793
* [llvm-dev] RFC: inbounds on getelementptr indices for global splitting

... but it's limited to constant expressions. There were previous attempts at
removing that restriction, namely that RFC and my patch:
⚙ D114988 [IR] `GetElementPtrInst`: per-index `inrange` support, however implementation experience/review
pointed out a few design problems:
1. Poor opaque pointers interop, it requires the GEP to be into a structure,
    so if it's a pure pointer computation, we suddenly can't preserve
the knowledge.
2. While just adding a bit[s] to GEP instruction allows the
transformation to just ignore it
    if they aren't explicitly taught about it, which is fine from a
legality standpoint,
    it complicates it's preservation through transformation.
3. While i'm not sure how useful it would be, it limits us to
statically-sized arrays.

Instead of following through with that, let me propose a new design:

<begin langref>

.. _int_memory_region_decl:

'``llvm.memory.region.decl``' Intrinsic
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Syntax:
"""""""

::

      declare i8* @llvm.memory.region.decl.p0i8(i8* nocapture readnone
returned <ptr>, i64 <begin_offset>, i64 <end_offset>) nofree nosync
nounwind readnone speculatable willreturn

Overview:
"""""""""

The '``llvm.memory.region.decl``' intrinsic annotates memory region.

Arguments:
""""""""""

This is an overloaded intrinsic. The memory region can belong to any address
space. The first argument is a pointer into the memory region. The returned
pointer, which is the first argument, must belong to the same address space
as the argument. The second argument specifies the offset to the pointer (the
first argument) at which the memory region begins. The third argument specifies
the offset to the pointer (the first argument) at which the memory region ends.

Semantics:
""""""""""

The returned pointer, and, transitively, any pointer that is def-use based on
that pointer, points into the memory region ``[ptr+begin_offset,
ptr+end_offset)``,
or is a :ref:`poison value <poisonvalues>` otherwise.

This intrinsic is intended to be an optimization hint, there are no correctness
concerns with completely ignoring and/or dropping it. The main use-case is
to be able to annotate array bounds in C family of languages,
which may allow alloca splitting, and better alias analysis.

</end langref>

Example:

struct S {
  int a;
  int b[4];
};
int* get(S*s, int i) {
  return &s->b[i];
}

is currently lowered into

define dso_local nonnull i32* @_Z3getP1Si(%struct.S* readnone %s, i32
%i) local_unnamed_addr #0 {
 %idxprom = sext i32 %i to i64
%arrayidx = getelementptr inbounds %struct.S, %struct.S* %s, i64 0,
i32 1, i64 %idxprom
 ret i32* %arrayidx
}

would instead be lowered into

define dso_local nonnull i32* @_Z3getP1Si(%struct.S* readnone %s, i32
%i) local_unnamed_addr #0 {
 %arrayidx = getelementptr inbounds %struct.S, %struct.S* %s, i64 0,
i32 1, i64 0
 %arrayidx.bounded = call i32* @llvm.memory.region.decl.p0i32(i32*
%arrayidx, i64 0, i64 32)
 %idxprom = sext i32 %i to i64
 %arrayidx3 = getelementptr inbounds i32, i32* %arrayidx.bounded, i64 %idxprom
 ret i32* %arrayidx3
}

Concretely, this tells us that %i u<= 4, which should be useful for
Alias Analysis
in less contrived snippets.

The other motivational example, although still contrived:

struct S {
 int a;
 int b[4];
};
int stuff(int i, int array_val, int j, int scalar_val) {
 S s;
 s.a = scalar_val;
 s.b[i] = array_val;
 return s.a;
}

currently results in:

define dso_local i32 @_Z5stuffiiii(i32 %i, i32 %array_val, i32 %j, i32
%scalar_val) local_unnamed_addr #0 {
entry:
%s = alloca %struct.S, align 4
%0 = bitcast %struct.S* %s to i8*
call void @llvm.lifetime.start.p0i8(i64 20, i8* nonnull %0) #2
%a = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
store i32 %scalar_val, i32* %a, align 4, !tbaa !3
%idxprom = sext i32 %i to i64
%arrayidx = getelementptr inbounds %struct.S, %struct.S* %s, i64 0,
i32 1, i64 %idxprom
store i32 %array_val, i32* %arrayidx, align 4, !tbaa !8
%1 = load i32, i32* %a, align 4, !tbaa !3
call void @llvm.lifetime.end.p0i8(i64 20, i8* nonnull %0) #2
ret i32 %1
}

Notice the problem? `array_val` couldn't have been stored into `S::a`,
this particular example should optimize to just

define dso_local i32 @_Z5stuffiiii(i32 %i, i32 %array_val, i32 %j, i32
%scalar_val) local_unnamed_addr #0 {
 ret i32 %scalar_val
}

The even bigger picture here is that SROA simply gives up in presence
of variable GEP's,
but if we annotate the extents of such a variable GEP, then, given
right circumstances,
we may be able to conclude that the alloca could be split up, and
certain parts be promoted.
That is the main motivation for me behind this.

I think, this is sufficient information, but let me know if i should
address something else.

Roman.

How does this interact with "inbounds" markings on GEPs? Can the result of a non-inbounds GEP point outside the specified region?

I assume the input and result pointer alias? Given that, I don't think the "nocapture" is right. (There's a potential use-case for a similar intrinsic where the result doesn't alias the argument, but I guess that would be a different thing.)

The usual concern with this sort of intrinsic is the work involved in teaching a bunch of pointer optimizations the meaning of the new intrinsic. Encoding array bounds is probably important enough to be worth the extra work, though.

-Eli

How does this interact with "inbounds" markings on GEPs? Can the result of a non-inbounds GEP point outside the specified region?

Uh, it's a trick question, isn't it? :slight_smile:

Right now I would basically say that "inbounds" markings on GEPs is
orthogonal here, because this intrinsic simply "clamps" the underlying
"allocated object".
(and naturally, you can't unclamp it afterwards *in this def-use chain*)

I.e. if you go out of the specified bounds with `inbounds` you get
poison (and i think you can't go back from there?); but if you go
out of the specified bounds without `inbounds` it's not poison,
but dereferencing said pointer is still UB.

Let me know if this isn't a proper answer,
or if i have talked myself into a corner here :slight_smile:

I assume the input and result pointer alias?

The input pointer is directly returned, so they are the same,
so they are mustalias.

Given that, I don't think the "nocapture" is right.

Hmm. I guess: Compiler Explorer
Okay.

(There's a potential use-case for a similar intrinsic where the result doesn't alias the argument, but I guess that would be a different thing.)

Nothing immediately comes into mind.

The usual concern with this sort of intrinsic is the work involved in teaching a bunch of pointer optimizations the meaning of the new intrinsic.

Yes, ignoring the implementation cost of the improvements that will be
made possible, there's going to be //some// implementation cost incurred
to de-pessimize the existing transformations, or, perhaps more importantly,
avoiding losing this intrinsic during transformations.
I acknowledge this worry.

Encoding array bounds is probably important enough to be worth the extra work, though.

I think it'll solve a big knowledge propagation hole,
so i certainly hope so, yes.

-Eli

Roman

This seems fine, sure. Please update your proposed LangRef patch so this is clear.

-Eli

> From: Roman Lebedev <lebedev.ri@gmail.com>
> Sent: Tuesday, December 7, 2021 2:39 PM
> To: llvm-dev@lists.llvm.org
> Cc: Eli Friedman <efriedma@quicinc.com>; Johannes Doerfert
> <jdoerfert@anl.gov>; Clement Courbet <courbet@google.com>; Nuno Lopes
> <nunoplopes@sapo.pt>; Nikita Popov <nikita.ppv@gmail.com>; Peter
> Collingbourne <peter@pcc.me.uk>; Philip Reames <listmail@philipreames.com>
> Subject: Re: [RFC] Memory region declaration intrinsic
>
> >
> > How does this interact with "inbounds" markings on GEPs? Can the result of a
> non-inbounds GEP point outside the specified region?
> Uh, it's a trick question, isn't it? :slight_smile:
>
> Right now I would basically say that "inbounds" markings on GEPs is
> orthogonal here, because this intrinsic simply "clamps" the underlying
> "allocated object".
> (and naturally, you can't unclamp it afterwards *in this def-use chain*)
>
> I.e. if you go out of the specified bounds with `inbounds` you get
> poison (and i think you can't go back from there?); but if you go
> out of the specified bounds without `inbounds` it's not poison,
> but dereferencing said pointer is still UB.
>
> Let me know if this isn't a proper answer,
> or if i have talked myself into a corner here :slight_smile:

This seems fine, sure. Please update your proposed LangRef patch so this is clear.

Thank you!
Okay, tried to improve the langref, let me know if there's anything
obvious missing / can be improved.

-Eli

Roman

I think adding new intrinsics, especially on the def-use chain, is the wrong way.

We need to skip them in too many places where we do not use "stripPointerCast" which
is always causing extra work and missed optimizations once we add more information (in
the form of these intrinsics).

A generic solution would be to add one intrinsic to which we can attach information:

declare <ty> @llvm.assume.chained(<ty> nocapture readnone returned <val>) /* attribute */

Now we add information the same way we do it for `llvm.assume`, via operand bundles:

%p = call @llvm.assume.chained(i32* %base) ["objectsize"(0, 12), "align"(16)]

The definition from below wrt the semantics now apply to the "objectsize" operand bundle,
or whatever name we come up with.

I imagine we can simplify quite a few existing attributes if we adopt this scheme (which
also means we could try it out already and see if there is a problem).

~ Johannes

First of all, apologies for the delay. I was busy moving between countries & job.

The non-technical question is whether this matters at all. Do we expect any perf benefit from improving alias analysis for this case?

On the technical side, I do like this SSI-like approach, where you create a new pointer rather than add stuff to the BB/function context. SSI-based data is safer as it's on the def-use chain, which the compiler knows how to preserve and validate; you can't break it. When we have assumptions stated in the control-flow (like assume or lifetime intrinsics), optimizers can easily miscompile by moving or not moving those intrinsics where needed.
I guess we can formalize the intrinsic you propose as returning a sub-object, with it's own size and attributes, but aliased storage with the main object. It's a view, essentially.

For pointer comparisons, I don't see an issue, as ATM we see comparisons as if pointers were integers. So no worries.
But GVN is broken for pointers, and this change will make it even more broken. If you have 'if (p == region.decl(p, ..)) use(p)', we can't blindly replace p with the decl, as the dereferenceability may be different. Nothing new, but it adds pressure to fix GVN once and for all (Alina and I will hopefully find time to work on it in January).

Then we have the lifetime intrinsics. I assume we want to forbid pointers to sub-objects to be given to lifetime intrinsics. But we need to patch the optimizations that handle it to know that killing the main object also kills the sub-objects. Probably there's nothing to do as this is mainly used in codegen, but just thinking out loud.

I can't remember of other pointer stuff that could potentially interact badly with these new pointers.

For the design of the intrinsic itself, I think I prefer Johannes approach to allow the intrinsic to get multiple attributes. Rather than offsets, objectsize() seems to be sufficient for the use case below. We could also use it for alignment info as suggested by Johannes.

Thanks,
Nuno

The non-technical question is whether this matters at all. Do we expect any
perf benefit from improving alias analysis for this case?

I’ve seen a number of very hot functions in our code where alias analysis was at fault because of this.
The most impressive issue was in a compression algorithm, and the code was essentially:

struct Histogram {
Histogram();
int total;
int values[256];
};

Histogram DoIt(const int* image, int size) {
Histogram histogram;
for (int i = 0; i < size; ++i) {
++histogram.values[image[i]];
++histogram.total;
}
return histogram;
}

Because alias analysis is unable to tell that histogram.total and histogram.values[*] do not alias, the total has to be incremented one by one.

It was easy to fix by manually moving histogram.total outside of the loop. And this made compression 1% faster overall, so it does actually matter quite a lot.
Of course one might argue that this was not optimally written, but it was written like this, and I’ve seen other cases where it’s not as obvious.
This is the generated code right now:

0000000000000000 <_Z4DoItPKii>:
0: 48 89 f8 mov %rdi,%rax
3: 85 d2 test %edx,%edx
5: 7e 4d jle 54 <_Z4DoItPKii+0x54>
7: 41 89 d0 mov %edx,%r8d
d: 75 04 jne 13 <_Z4DoItPKii+0x13>
f: 31 d2 xor %edx,%edx
11: eb 2f jmp 42 <_Z4DoItPKii+0x42>
13: 44 89 c7 mov %r8d,%edi
16: 83 e7 fe and $0xfffffffe,%edi
19: 31 d2 xor %edx,%edx
1b: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1) ; loop (unrolled 2 times)
20: 48 63 0c 96 movslq (%rsi,%rdx,4),%rcx ; image[i]
24: 83 44 88 04 01 addl $0x1,0x4(%rax,%rcx,4) ; ++histogram.values[image[i]]
29: 83 00 01 addl $0x1,(%rax) ; ++histogram.total
2c: 48 63 4c 96 04 movslq 0x4(%rsi,%rdx,4),%rcx
31: 83 44 88 04 01 addl $0x1,0x4(%rax,%rcx,4)
36: 83 00 01 addl $0x1,(%rax)
39: 48 83 c2 02 add $0x2,%rdx
3d: 48 39 d7 cmp %rdx,%rdi
40: 75 de jne 20 <_Z4DoItPKii+0x20> ; end loop
42: 41 f6 c0 01 test $0x1,%r8b
46: 74 0c je 54 <_Z4DoItPKii+0x54>
48: 48 63 0c 96 movslq (%rsi,%rdx,4),%rcx
4c: 83 44 88 04 01 addl $0x1,0x4(%rax,%rcx,4)
51: 83 00 01 addl $0x1,(%rax)
54: c3 ret

When I let clang emit range information (note: this was with a previous iteration of this proposal, but the results are the same), LLVM can now hoist histogram.total out of the loop.

0000000000000000 <_Z4DoItPKii>:
0: 48 89 f8 mov %rdi,%rax
3: 85 d2 test %edx,%edx
5: 0f 8e 7d 00 00 00 jle 88 <_Z4DoItPKii+0x88>
b: 41 89 d1 mov %edx,%r9d
e: 49 8d 49 ff lea -0x1(%r9),%rcx
12: 45 89 c8 mov %r9d,%r8d
15: 41 83 e0 03 and $0x3,%r8d
19: 48 83 f9 03 cmp $0x3,%rcx
1d: 73 04 jae 23 <_Z4DoItPKii+0x23>
1f: 31 c9 xor %ecx,%ecx
21: eb 3d jmp 60 <_Z4DoItPKii+0x60>
23: 41 83 e1 fc and $0xfffffffc,%r9d
27: 31 c9 xor %ecx,%ecx
29: 0f 1f 80 00 00 00 00 nopl 0x0(%rax) ; loop (unrolled 4 times)
30: 48 63 3c 8e movslq (%rsi,%rcx,4),%rdi ; image[i]
34: 83 44 b8 04 01 addl $0x1,0x4(%rax,%rdi,4) ; ++histogram.values[image[i]]
39: 48 63 7c 8e 04 movslq 0x4(%rsi,%rcx,4),%rdi
3e: 83 44 b8 04 01 addl $0x1,0x4(%rax,%rdi,4)
43: 48 63 7c 8e 08 movslq 0x8(%rsi,%rcx,4),%rdi
48: 83 44 b8 04 01 addl $0x1,0x4(%rax,%rdi,4)
4d: 48 63 7c 8e 0c movslq 0xc(%rsi,%rcx,4),%rdi
52: 83 44 b8 04 01 addl $0x1,0x4(%rax,%rdi,4)
57: 48 83 c1 04 add $0x4,%rcx
5b: 49 39 c9 cmp %rcx,%r9
5e: 75 d0 jne 30 <_Z4DoItPKii+0x30>
60: 44 8b 08 mov (%rax),%r9d
63: 4d 85 c0 test %r8,%r8
66: 74 1a je 82 <_Z4DoItPKii+0x82>
68: 48 8d 0c 8e lea (%rsi,%rcx,4),%rcx
6c: 31 f6 xor %esi,%esi
6e: 66 90 xchg %ax,%ax
70: 48 63 3c b1 movslq (%rcx,%rsi,4),%rdi
74: 83 44 b8 04 01 addl $0x1,0x4(%rax,%rdi,4)
79: 48 83 c6 01 add $0x1,%rsi
7d: 49 39 f0 cmp %rsi,%r8
80: 75 ee jne 70 <_Z4DoItPKii+0x70>
82: 41 01 d1 add %edx,%r9d
85: 44 89 08 mov %r9d,(%rax) ; histogram.total = iter count
88: c3 ret