[llvm-dev] [RFC] Memory region declaration intrinsic

[Roman Lebedev via llvm-dev]

Hi all.

Differential: https://reviews.llvm.org/D115274

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 / http://eel.is/c++draft/expr.add#4, 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
* https://lists.llvm.org/pipermail/llvm-dev/2016-July/102472.html

... but it's limited to constant expressions. There were previous attempts at
removing that restriction, namely that RFC and my patch:
https://reviews.llvm.org/D114988, 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.