llvm dev - Mar 2021 - [RFC] Adding range metadata to array subscripts.

On 3/24/21 12:47 PM, Florian Hahn wrote:
>
>> On Mar 24, 2021, at 15:16, Johannes Doerfert via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
>>
>>
>> On 3/24/21 9:06 AM, Clement Courbet wrote:
>>> On Wed, Mar 24, 2021 at 2:20 PM Johannes Doerfert <
>>> johannesdoerfert at gmail.com> wrote:
>>>
>>>> I really like encoding more (range) information in the IR,
>>>> more thoughts inlined.
>>>>
>>>> On 3/24/21 4:14 AM, Clement Courbet via llvm-dev wrote:
>>>>> Hi everyone,
>>>>>
>>>>> tl;dr: I would like to teach clang to output range metadata
so that LLVM
>>>>> can do better alias analysis. I have a proposal as D99248
>>>>> <https://reviews.llvm.org/D99248> (clang part) and
D99247
>>>>> <https://reviews.llvm.org/D99247> (llvm part). But
there are other
>>>> possible
>>>>> options that I'm detailing below.
>>>>>
>>>>> Consider the following code, adapted from brotli
>>>>> <https://en.wikipedia.org/wiki/Brotli>:
>>>>>
>>>>> ```
>>>>>
>>>>> struct Histogram {
>>>>>
>>>>>     int values[256];
>>>>>
>>>>>     int total;
>>>>>
>>>>> };
>>>>>
>>>>> Histogram DoIt(const int* image, int size) {
>>>>>
>>>>>     Histogram histogram;
>>>>>
>>>>>     for (int i = 0; i < size; ++i) {
>>>>>
>>>>>       ++histogram.values[image[i]];  // (A)
>>>>>
>>>>>       ++histogram.total;             // (B)
>>>>>
>>>>>     }
>>>>>
>>>>>     return histogram;
>>>>>
>>>>> }
>>>>> ```
>>>>>
>>>>> In this code, the compiler does not know anything about the
values of
>>>>> images[i], so it assumes that 256 is a possible value for
it. In that
>>>> case,
>>>>> (A) would change the value of histogram.total, so (B) has
to load, add
>>>> one
>>>>> and store [godbolt <https://godbolt.org/z/KxE343>].
>>>>>
>>>>> Fortunately, C/C++ has a rule that it is invalid (actually,
UB) to use
>>>>> values to form a pointer to total and dereference it. What
valid C/C++
>>>> code
>>>>> is allowed to do with values is:
>>>>>    - Form any pointer in [values, values + 256].
>>>>>    - Form and dereference any pointer in [values, values +
256)
>>>>>
>>>>> Note that the LLVM memory model is much laxer than that of
C/C++. It has
>>>> no
>>>>> notion of types. In particular, given an LLVM aggregate
definition:
>>>>>
>>>>> ```
>>>>> %struct.S = type { [42 x i32], i32, i32 }
>>>>> ```
>>>>>
>>>>> It is perfectly valid to use an address derived from a
GEP(0,0,%i)  [gep
>>>>> reference] representing indexing into the [42 x i32] array
to load the
>>>> i32
>>>>> member at index 2. It is also valid for %i to be 43 (though
not 44 if an
>>>>> inbound GEP is used).
>>>>> So clang has to give LLVM more information about the C/C++
rules.
>>>>>
>>>>> *IR representation:*
>>>>> LLVM has several ways of representing ranges of values:
>>>>>    - *!range* metadata can be attached to integer call and
load
>>>> instructions
>>>>> to indicate the allowed range of values of the result.
LLVM's
>>>> ValueTracking
>>>>> provides a function for querying the range for any
llvm::Variable.
>>>>>    - The *llvm.assume* intrinsic takes a boolean condition
that can also
>>>> be
>>>>> used by ValueTracking to infer range of values.
>>>>>    - The *inrange* attribute of GEP can be used to indicate
C-like
>>>> semantics
>>>>> for the structure field marked with the inrange attribute.
It can only be
>>>>> used for GEP constantexprs (ie.e. GEPs defined inline), but
not for
>>>>> standalone GEPs defining instructions.  relevant discussion
>>>>>
<https://reviews.llvm.org/D22793?id=65626#inline-194653>.
>>>>>
>>>>> Alternatives:
>>>>> *(1) *Annotate each array subscript index value with a
range, e.g.:
>>>>> ```
>>>>> %i = i64 …
>>>>> %ri =  call i64 @llvm.annotation.i64(%index), !range !0
>>>>> %gep1 = getelementptr inbounds %struct.S, %struct.S* %s,
i64 0, i32 0,
>>>> i32
>>>>> %ri
>>>>> ...
>>>>> !0 = !{i64 0, i64 42}
>>>>> ```
>>>>> *(2) *(variant of 1) relax the constraint that !range
metadata can only
>>>> be
>>>>> set on call and load instructions, and set the !range
metadata on the
>>>> index
>>>>> expression. We still need annotations for function
parameters though:
>>>>> ```
>>>>> %i = i64 … , !range !0
>>>>> %gep1 = getelementptr inbounds %struct.S, %struct.S* %s,
i64 0, i32 0,
>>>> i32
>>>>> %i
>>>>> ...
>>>>> !0 = !{i64 0, i64 42}
>>>>> ```
>>>>> This is slightly more compact.
>>>>>
>>>>> *(3)* Same as (1), with llvm.assume. This feels inferior to
annotations.
>>>>> *(4)* Extend inrange to non-constantexprs GEPs. It is
unclear how this
>>>> will
>>>>> interfere with optimizations.
>>>> I would very much like not to introduce another way to encode
>>>> assumptions other than `llvm.assume`. If you want to avoid the
extra
>>>> instructions, use `llvm.assume(i1 true)
["range"(%val, %lb, %ub)]`,
>>>> which is in line with our move towards operand bundle use.
>>>>
>>> Thanks, I did not know about that. I've just tried it but it
appears that
>>> tags have to be attribute names, and `!range` is not a valid
attribute,
>>> it's a metadata node. Is there a way to encode this ?
>> We need to get rid of that assertion. There are other non-attributes
>> to be used in assume operand bundles in the (near) future, so the this
>> work has to be done anyway.
>
> +1 on trying to use assume, rather than adding another way.
>
> But are value ranges special for assumes, so that we need to handle them in
a bundle? Is that just so we can easier skip ‘artificial’ assume users?
It would make users explicit and we will have non-attribute bundles anyway.
I find it also "conceptually nicer", would you prefer explicit
instructions?

~ Johannes

> Cheers,
> Florian

To summarize here is how each proposal would look like, along with a list
of pros and cons for each.

%struct.S = type { i32, [2 x i32], i32 }

*inrange*
define void @with_inrange(%struct.S* %s, i32 %in_array) {
  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1,
inrange i32 %in_array
  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
  ret void
}

(Note that this is not currently valid IR, we need to make `inrange` work
on standalone GEP instructions)
pros:
 - compact, no extra instructions
cons:
 - The range information is local to the GEP instruction, and cannot be
easily used for other purposes, e.g. SCEV (the ValueTracker is not aware of
it)

*annotation with range metadata*
define void @with_annotation(%struct.S* %s, i32 %index) {
  %in_array = call i32 @llvm.annotation.i32(%index), !range !0
  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1,
i32 %in_array
  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
  ret void
}

pros:
 - a single added instruction
 - the ValueTracker already knows about range metadata
 - deriving the range in ValueTracker involves a single metadata lookup.
 - The range information will be available for other purposes (e.g. SCEV).
cons:
 - one extra instruction
 - llvm.annotation is not widely used


*assume*
define void @with_assume(%struct.S* %s, i32 %in_array) {
  %cmp1 = icmp sge i32 %in_array, 0
  %cmp2 = icmp slt i32 %in_array, 2
  %cmp = and i1 %cmp1, %cmp2
  call void @llvm.assume(i1 %cmp)
  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1,
i32 %in_array
  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
  ret void
}

pros:
 - The range information will be available for other purposes (e.g. SCEV).
cons:
 - several extra instructions
 - the ValueTracker cannot currently derive a range from this
 - Deriving the range can be costly
<https://github.com/llvm/llvm-project/blob/dd388ba3e0b0a5f06565d0bcb6e1aebb5daac065/llvm/lib/Analysis/ValueTracking.cpp#L638>

*assume with bundle*
define void @with_assume_bundle(%struct.S* %s, i32 %in_array) {
  call void @llvm.assume(i1 true) ["range"(i32 %in_array, i32 0, i32
2)]
  %gep1 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 1,
i32 %in_array
  %gep2 = getelementptr inbounds %struct.S, %struct.S* %s, i64 0, i32 0
  ret void
}

(Note that this is not currently valid IR, we need to make bundle tags work
for non-attributes)
pros:
 - The range information will be available for other purposes (e.g. SCEV).
 - ? (see below)
cons:
 - one extra instruction
 - ? (see below)

@johannes For the last option, I'm also not sure what becomes of the
"range" tag in the assume bundle once we remove the assertion ? Does
it
become attached to the value (%in_array), in which case we have the
advantages of range metadata (option 2), or is this still attached to the
assume, with the disadvantages of option 3 ?

On Wed, Mar 24, 2021 at 8:32 PM Johannes Doerfert <
johannesdoerfert at gmail.com> wrote:
>
> On 3/24/21 12:47 PM, Florian Hahn wrote:
> >
> >> On Mar 24, 2021, at 15:16, Johannes Doerfert via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >>
> >>
> >> On 3/24/21 9:06 AM, Clement Courbet wrote:
> >>> On Wed, Mar 24, 2021 at 2:20 PM Johannes Doerfert <
> >>> johannesdoerfert at gmail.com> wrote:
> >>>
> >>>> I really like encoding more (range) information in the IR,
> >>>> more thoughts inlined.
> >>>>
> >>>> On 3/24/21 4:14 AM, Clement Courbet via llvm-dev wrote:
> >>>>> Hi everyone,
> >>>>>
> >>>>> tl;dr: I would like to teach clang to output range
metadata so that
> LLVM
> >>>>> can do better alias analysis. I have a proposal as
D99248
> >>>>> <https://reviews.llvm.org/D99248> (clang part)
and D99247
> >>>>> <https://reviews.llvm.org/D99247> (llvm part).
But there are other
> >>>> possible
> >>>>> options that I'm detailing below.
> >>>>>
> >>>>> Consider the following code, adapted from brotli
> >>>>> <https://en.wikipedia.org/wiki/Brotli>:
> >>>>>
> >>>>> ```
> >>>>>
> >>>>> struct Histogram {
> >>>>>
> >>>>>     int values[256];
> >>>>>
> >>>>>     int total;
> >>>>>
> >>>>> };
> >>>>>
> >>>>> Histogram DoIt(const int* image, int size) {
> >>>>>
> >>>>>     Histogram histogram;
> >>>>>
> >>>>>     for (int i = 0; i < size; ++i) {
> >>>>>
> >>>>>       ++histogram.values[image[i]];  // (A)
> >>>>>
> >>>>>       ++histogram.total;             // (B)
> >>>>>
> >>>>>     }
> >>>>>
> >>>>>     return histogram;
> >>>>>
> >>>>> }
> >>>>> ```
> >>>>>
> >>>>> In this code, the compiler does not know anything
about the values of
> >>>>> images[i], so it assumes that 256 is a possible value
for it. In that
> >>>> case,
> >>>>> (A) would change the value of histogram.total, so (B)
has to load,
> add
> >>>> one
> >>>>> and store [godbolt
<https://godbolt.org/z/KxE343>].
> >>>>>
> >>>>> Fortunately, C/C++ has a rule that it is invalid
(actually, UB) to
> use
> >>>>> values to form a pointer to total and dereference it.
What valid
> C/C++
> >>>> code
> >>>>> is allowed to do with values is:
> >>>>>    - Form any pointer in [values, values + 256].
> >>>>>    - Form and dereference any pointer in [values,
values + 256)
> >>>>>
> >>>>> Note that the LLVM memory model is much laxer than
that of C/C++. It
> has
> >>>> no
> >>>>> notion of types. In particular, given an LLVM
aggregate definition:
> >>>>>
> >>>>> ```
> >>>>> %struct.S = type { [42 x i32], i32, i32 }
> >>>>> ```
> >>>>>
> >>>>> It is perfectly valid to use an address derived from a
GEP(0,0,%i)
> [gep
> >>>>> reference] representing indexing into the [42 x i32]
array to load
> the
> >>>> i32
> >>>>> member at index 2. It is also valid for %i to be 43
(though not 44
> if an
> >>>>> inbound GEP is used).
> >>>>> So clang has to give LLVM more information about the
C/C++ rules.
> >>>>>
> >>>>> *IR representation:*
> >>>>> LLVM has several ways of representing ranges of
values:
> >>>>>    - *!range* metadata can be attached to integer call
and load
> >>>> instructions
> >>>>> to indicate the allowed range of values of the result.
LLVM's
> >>>> ValueTracking
> >>>>> provides a function for querying the range for any
llvm::Variable.
> >>>>>    - The *llvm.assume* intrinsic takes a boolean
condition that can
> also
> >>>> be
> >>>>> used by ValueTracking to infer range of values.
> >>>>>    - The *inrange* attribute of GEP can be used to
indicate C-like
> >>>> semantics
> >>>>> for the structure field marked with the inrange
attribute. It can
> only be
> >>>>> used for GEP constantexprs (ie.e. GEPs defined
inline), but not for
> >>>>> standalone GEPs defining instructions.  relevant
discussion
> >>>>>
<https://reviews.llvm.org/D22793?id=65626#inline-194653>.
> >>>>>
> >>>>> Alternatives:
> >>>>> *(1) *Annotate each array subscript index value with a
range, e.g.:
> >>>>> ```
> >>>>> %i = i64 …
> >>>>> %ri =  call i64 @llvm.annotation.i64(%index), !range
!0
> >>>>> %gep1 = getelementptr inbounds %struct.S, %struct.S*
%s, i64 0, i32
> 0,
> >>>> i32
> >>>>> %ri
> >>>>> ...
> >>>>> !0 = !{i64 0, i64 42}
> >>>>> ```
> >>>>> *(2) *(variant of 1) relax the constraint that !range
metadata can
> only
> >>>> be
> >>>>> set on call and load instructions, and set the !range
metadata on the
> >>>> index
> >>>>> expression. We still need annotations for function
parameters though:
> >>>>> ```
> >>>>> %i = i64 … , !range !0
> >>>>> %gep1 = getelementptr inbounds %struct.S, %struct.S*
%s, i64 0, i32
> 0,
> >>>> i32
> >>>>> %i
> >>>>> ...
> >>>>> !0 = !{i64 0, i64 42}
> >>>>> ```
> >>>>> This is slightly more compact.
> >>>>>
> >>>>> *(3)* Same as (1), with llvm.assume. This feels
inferior to
> annotations.
> >>>>> *(4)* Extend inrange to non-constantexprs GEPs. It is
unclear how
> this
> >>>> will
> >>>>> interfere with optimizations.
> >>>> I would very much like not to introduce another way to
encode
> >>>> assumptions other than `llvm.assume`. If you want to avoid
the extra
> >>>> instructions, use `llvm.assume(i1 true)
["range"(%val, %lb, %ub)]`,
> >>>> which is in line with our move towards operand bundle use.
> >>>>
> >>> Thanks, I did not know about that. I've just tried it but
it appears
> that
> >>> tags have to be attribute names, and `!range` is not a valid
attribute,
> >>> it's a metadata node. Is there a way to encode this ?
> >> We need to get rid of that assertion. There are other
non-attributes
> >> to be used in assume operand bundles in the (near) future, so the
this
> >> work has to be done anyway.
> >
> > +1 on trying to use assume, rather than adding another way.
> >
> > But are value ranges special for assumes, so that we need to handle
them
> in a bundle? Is that just so we can easier skip ‘artificial’ assume users?
>
> It would make users explicit and we will have non-attribute bundles anyway.
> I find it also "conceptually nicer", would you prefer explicit
> instructions?
>
> ~ Johannes
>
>
> > Cheers,
> > Florian
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210325/1c4b5aaa/attachment.html>

> On Mar 24, 2021, at 19:32, Johannes Doerfert <johannesdoerfert at
gmail.com> wrote:
> 
> 
> On 3/24/21 12:47 PM, Florian Hahn wrote:
>> 
>>> On Mar 24, 2021, at 15:16, Johannes Doerfert via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
>>> 
>>> 
>>> On 3/24/21 9:06 AM, Clement Courbet wrote:
>>>> On Wed, Mar 24, 2021 at 2:20 PM Johannes Doerfert <
>>>> johannesdoerfert at gmail.com> wrote:
>>>> 
>>>>> I really like encoding more (range) information in the IR,
>>>>> more thoughts inlined.
>>>>> 
>>>>> On 3/24/21 4:14 AM, Clement Courbet via llvm-dev wrote:
>>>>>> Hi everyone,
>>>>>> 
>>>>>> tl;dr: I would like to teach clang to output range
metadata so that LLVM
>>>>>> can do better alias analysis. I have a proposal as
D99248
>>>>>> <https://reviews.llvm.org/D99248> (clang part)
and D99247
>>>>>> <https://reviews.llvm.org/D99247> (llvm part).
But there are other
>>>>> possible
>>>>>> options that I'm detailing below.
>>>>>> 
>>>>>> Consider the following code, adapted from brotli
>>>>>> <https://en.wikipedia.org/wiki/Brotli>:
>>>>>> 
>>>>>> ```
>>>>>> 
>>>>>> struct Histogram {
>>>>>> 
>>>>>>    int values[256];
>>>>>> 
>>>>>>    int total;
>>>>>> 
>>>>>> };
>>>>>> 
>>>>>> Histogram DoIt(const int* image, int size) {
>>>>>> 
>>>>>>    Histogram histogram;
>>>>>> 
>>>>>>    for (int i = 0; i < size; ++i) {
>>>>>> 
>>>>>>      ++histogram.values[image[i]];  // (A)
>>>>>> 
>>>>>>      ++histogram.total;             // (B)
>>>>>> 
>>>>>>    }
>>>>>> 
>>>>>>    return histogram;
>>>>>> 
>>>>>> }
>>>>>> ```
>>>>>> 
>>>>>> In this code, the compiler does not know anything about
the values of
>>>>>> images[i], so it assumes that 256 is a possible value
for it. In that
>>>>> case,
>>>>>> (A) would change the value of histogram.total, so (B)
has to load, add
>>>>> one
>>>>>> and store [godbolt
<https://godbolt.org/z/KxE343>].
>>>>>> 
>>>>>> Fortunately, C/C++ has a rule that it is invalid
(actually, UB) to use
>>>>>> values to form a pointer to total and dereference it.
What valid C/C++
>>>>> code
>>>>>> is allowed to do with values is:
>>>>>>   - Form any pointer in [values, values + 256].
>>>>>>   - Form and dereference any pointer in [values, values
+ 256)
>>>>>> 
>>>>>> Note that the LLVM memory model is much laxer than that
of C/C++. It has
>>>>> no
>>>>>> notion of types. In particular, given an LLVM aggregate
definition:
>>>>>> 
>>>>>> ```
>>>>>> %struct.S = type { [42 x i32], i32, i32 }
>>>>>> ```
>>>>>> 
>>>>>> It is perfectly valid to use an address derived from a
GEP(0,0,%i)  [gep
>>>>>> reference] representing indexing into the [42 x i32]
array to load the
>>>>> i32
>>>>>> member at index 2. It is also valid for %i to be 43
(though not 44 if an
>>>>>> inbound GEP is used).
>>>>>> So clang has to give LLVM more information about the
C/C++ rules.
>>>>>> 
>>>>>> *IR representation:*
>>>>>> LLVM has several ways of representing ranges of values:
>>>>>>   - *!range* metadata can be attached to integer call
and load
>>>>> instructions
>>>>>> to indicate the allowed range of values of the result.
LLVM's
>>>>> ValueTracking
>>>>>> provides a function for querying the range for any
llvm::Variable.
>>>>>>   - The *llvm.assume* intrinsic takes a boolean
condition that can also
>>>>> be
>>>>>> used by ValueTracking to infer range of values.
>>>>>>   - The *inrange* attribute of GEP can be used to
indicate C-like
>>>>> semantics
>>>>>> for the structure field marked with the inrange
attribute. It can only be
>>>>>> used for GEP constantexprs (ie.e. GEPs defined inline),
but not for
>>>>>> standalone GEPs defining instructions.  relevant
discussion
>>>>>>
<https://reviews.llvm.org/D22793?id=65626#inline-194653>.
>>>>>> 
>>>>>> Alternatives:
>>>>>> *(1) *Annotate each array subscript index value with a
range, e.g.:
>>>>>> ```
>>>>>> %i = i64 …
>>>>>> %ri =  call i64 @llvm.annotation.i64(%index), !range !0
>>>>>> %gep1 = getelementptr inbounds %struct.S, %struct.S*
%s, i64 0, i32 0,
>>>>> i32
>>>>>> %ri
>>>>>> ...
>>>>>> !0 = !{i64 0, i64 42}
>>>>>> ```
>>>>>> *(2) *(variant of 1) relax the constraint that !range
metadata can only
>>>>> be
>>>>>> set on call and load instructions, and set the !range
metadata on the
>>>>> index
>>>>>> expression. We still need annotations for function
parameters though:
>>>>>> ```
>>>>>> %i = i64 … , !range !0
>>>>>> %gep1 = getelementptr inbounds %struct.S, %struct.S*
%s, i64 0, i32 0,
>>>>> i32
>>>>>> %i
>>>>>> ...
>>>>>> !0 = !{i64 0, i64 42}
>>>>>> ```
>>>>>> This is slightly more compact.
>>>>>> 
>>>>>> *(3)* Same as (1), with llvm.assume. This feels
inferior to annotations.
>>>>>> *(4)* Extend inrange to non-constantexprs GEPs. It is
unclear how this
>>>>> will
>>>>>> interfere with optimizations.
>>>>> I would very much like not to introduce another way to
encode
>>>>> assumptions other than `llvm.assume`. If you want to avoid
the extra
>>>>> instructions, use `llvm.assume(i1 true)
["range"(%val, %lb, %ub)]`,
>>>>> which is in line with our move towards operand bundle use.
>>>>> 
>>>> Thanks, I did not know about that. I've just tried it but
it appears that
>>>> tags have to be attribute names, and `!range` is not a valid
attribute,
>>>> it's a metadata node. Is there a way to encode this ?
>>> We need to get rid of that assertion. There are other
non-attributes
>>> to be used in assume operand bundles in the (near) future, so the
this
>>> work has to be done anyway.
>> 
>> +1 on trying to use assume, rather than adding another way.
>> 
>> But are value ranges special for assumes, so that we need to handle
them in a bundle? Is that just so we can easier skip ‘artificial’ assume users?
> 
> It would make users explicit and we will have non-attribute bundles anyway.
> I find it also "conceptually nicer", would you prefer explicit
instructions?
One disadvantage of using a bundle (or !range metadata) is that we treat ranges
for certain values in a special way and differently to how we treat range
information expressed by the user e.g. via conditions (or builtin assume). This
means we have to handle multiple variants across the codebase, which can lead to
situations where only one or the other is handled, which in turn can lead to
surprising results (of the form: why does a transformation apply if information
provided in a certain way, but does not apply of the equivalent info is provided
in a different way).
Using instruction potentially also allows us to specify more complex ranges, in
relation to other values.

But I realize that there are some practical consideration that make the
instruction approach less appealing and I am all in favor of the more pragmatic
& practical solution to start with.

Cheers,
Florian
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210327/ec6db754/attachment.html>