llvm dev - Jul 2016 - RFC: inbounds on getelementptr indices for global splitting

Hi all,

I'd like to propose an IR extension that allows the inbounds keyword to be
attached to indices in a getelementptr constantexpr.

By placing the inbounds keyword on an index, any pointer derived from the
getelementptr outside of the bounds of the element referred to by that
index, other than the pointer one past the end of the element, shall be
treated as a poison value.

The main motivation is to allow the optimizer to split vtable groups along
vtable boundaries thus reducing code size when certain compiler features
[1] are enabled, in a way that avoids breaking ABI. The idea is that it
would be safe to split only if the vtable has local linkage and each
reference to the global has an inbounds keyword on the correct index. If
both of these conditions are satisfied, the address of the entire global is
known to not be taken, and therefore a split would not break semantics. The
new attribute could also potentially be used with other features such as
alias analysis.

This proposal arises from some concerns raised by Eli at
http://reviews.llvm.org/D22295 regarding an earlier implementation of
global splitting, which was based on metadata. I'm posting this new
proposal as an RFC as the increased intrusiveness in the IR warrants
greater visibility.

Example

i8** getelementptr inbounds ({[4 x i8*], [4 x i8*]}, {[4 x i8*], [4 x
i8*]}* @_ZTVfoo, i32 0, inbounds i32 1, i32 2)

This is a reference to the address point of the second element of _ZTVfoo,
a virtual table group with two virtual tables, such that any pointer
extending beyond the bounds of the second virtual table is a poison value.

Alternatives

We could consider attaching metadata to globals as proposed and implemented
in D22295, which would avoid extending the constant expression IR. However
as pointed out by Eli this is problematic because optimization passes may
plausibly rebuild globals in non-permitted ways, for example by deriving a
pointer to one past the end of a partition (which may cause it to point to
another global).

We could consider using intrinsics instead of constant expressions to
represent references to partitions. However this is not enough at least for
vtables because other globals (e.g. VTTs) may need to contain pointers to
vtables.

Thanks,
-- 
Peter

[1] Specifically, if either of the whole-program devirtualization or
control flow integrity features are being used. In the former case, under
virtual constant propagation we are able to place propagated constants
directly in front of virtual tables of classes with multiple bases. In the
latter case, we can arrange virtual tables with multiple bases in a more
hierarchical order, which reduces the required amount of runtime data and
simplifies the required checks.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160718/69c3c84a/attachment.html>

On Mon, Jul 18, 2016 at 6:02 PM, Peter Collingbourne via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hi all,
>
> I'd like to propose an IR extension that allows the inbounds keyword to
be
> attached to indices in a getelementptr constantexpr.
>
> By placing the inbounds keyword on an index, any pointer derived from the
> getelementptr outside of the bounds of the element referred to by that
> index, other than the pointer one past the end of the element, shall be
> treated as a poison value.
>

I have read this sentence several times and I am still not quite sure what
it means.
Can you please provide more examples of exactly what you are trying to
represent?

I know what it means for inbounds to be on the GEP but none of the indices:
that's the GEP of today.
What does it mean for the GEP to be marked inbound while only some of the
indices are inbounds?  What if the GEP isn't marked inbounds?
What does it mean if all the GEP indices are marked inbounds but the GEP
isn't marked inbounds?

GEPs are folded and optimized, two GEPs can compute the same numeric
position with differing indices.  What happens when we are giving out new
indices for a GEP with one (or more) inbounds index?

I'm also a little confused when you talk about pointers derived from the
GEP being outside of the bounds... The inbounds of present day GEP refers
to the base pointer and offsets, it does not directly have semantics on
pointers derived from such a GEP.  This means it is perfectly OK to have an
out of bounds GEP of an inbounds GEP.  My reading of your extension says
that this is not possible...

> The main motivation is to allow the optimizer to split vtable groups along
> vtable boundaries thus reducing code size when certain compiler features
> [1] are enabled, in a way that avoids breaking ABI. The idea is that it
> would be safe to split only if the vtable has local linkage and each
> reference to the global has an inbounds keyword on the correct index. If
> both of these conditions are satisfied, the address of the entire global is
> known to not be taken, and therefore a split would not break semantics. The
> new attribute could also potentially be used with other features such as
> alias analysis.
>
> This proposal arises from some concerns raised by Eli at
> http://reviews.llvm.org/D22295 regarding an earlier implementation of
> global splitting, which was based on metadata. I'm posting this new
> proposal as an RFC as the increased intrusiveness in the IR warrants
> greater visibility.
>
> Example
>
> i8** getelementptr inbounds ({[4 x i8*], [4 x i8*]}, {[4 x i8*], [4 x
> i8*]}* @_ZTVfoo, i32 0, inbounds i32 1, i32 2)
>
> This is a reference to the address point of the second element of _ZTVfoo,
> a virtual table group with two virtual tables, such that any pointer
> extending beyond the bounds of the second virtual table is a poison value.
>
> Alternatives
>
> We could consider attaching metadata to globals as proposed and
> implemented in D22295, which would avoid extending the constant expression
> IR. However as pointed out by Eli this is problematic because optimization
> passes may plausibly rebuild globals in non-permitted ways, for example by
> deriving a pointer to one past the end of a partition (which may cause it
> to point to another global).
>
> We could consider using intrinsics instead of constant expressions to
> represent references to partitions. However this is not enough at least for
> vtables because other globals (e.g. VTTs) may need to contain pointers to
> vtables.
>
> Thanks,
> --
> Peter
>
> [1] Specifically, if either of the whole-program devirtualization or
> control flow integrity features are being used. In the former case, under
> virtual constant propagation we are able to place propagated constants
> directly in front of virtual tables of classes with multiple bases. In the
> latter case, we can arrange virtual tables with multiple bases in a more
> hierarchical order, which reduces the required amount of runtime data and
> simplifies the required checks.
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160718/692372d1/attachment.html>

On Mon, Jul 18, 2016 at 8:29 PM, David Majnemer <david.majnemer at
gmail.com>
wrote:
>
>
> On Mon, Jul 18, 2016 at 6:02 PM, Peter Collingbourne via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi all,
>>
>> I'd like to propose an IR extension that allows the inbounds
keyword to
>> be attached to indices in a getelementptr constantexpr.
>>
>> By placing the inbounds keyword on an index, any pointer derived from
the
>> getelementptr outside of the bounds of the element referred to by that
>> index, other than the pointer one past the end of the element, shall be
>> treated as a poison value.
>>
>
>
> I have read this sentence several times and I am still not quite sure what
> it means.
> Can you please provide more examples of exactly what you are trying to
> represent?
>
Thank you for asking me to provide another example because thinking about
it revealed a flaw in my original specification. Here's the example, which
involves nested arrays.

@x = internal global [2 x [2 x [2 x i32]]] [[2 x [2 x i32]] [[2 x i32] [i32
1, i32 2], [2 x i32] [i32 3, i32 4]], [2 x [2 x i32]] [[2 x i32] [i32 5,
i32 6], [2 x i32] [i32 7, i32 8]]]
@x0 = constant i32* getelementptr inbounds ([2 x [2 x [2 x i32]]], [2 x [2
x [2 x i32]]]* @x, i32 0, inbounds i32 0, i32 0, i32 0)
@x1 = constant i32* getelementptr inbounds ([2 x [2 x [2 x i32]]], [2 x [2
x [2 x i32]]]* @x, i32 0, inbounds i32 1, i32 0, i32 0)

The intention is that the pointer that x0 is initialized to may only be
used to access the subelement {{1,2},{3,4}} of x (that being the element
selected by the second index), and the pointer that x1 is initialized to
may only be used to access subelement {{5,6},{7,8}} of x.

Semantically, we would want this function's behavior to be undefined:

define void @foo() {
  %p = load i32** @x0
  %q = getelementptr i32*, i32** %p, i32 4
  %r = load i32* %q ; UB here
  ret void
}

while this one would be fine:

define void @foo() {
  %p = load i32** @x0
  %q = getelementptr i32*, i32** %p, i32 2
  %r = load i32* %q ; loads 3
  ret void
}

As a consequence, if there are no other references to x, the optimizer may
split x into two globals:

@x.0 = internal global [2 x [2 x i32]] [[2 x i32] [i32 1, i32 2], [2 x i32]
[i32 3, i32 4]]
@x.1 = internal global [2 x [2 x i32]] [[2 x i32] [i32 5, i32 6], [2 x i32]
[i32 7, i32 8]]

replace x0's initializer with a reference to x.0 and replace x1's
initializer with a reference to x1. This is possible because the program
contains no pointer to x that may be adjusted to access the entire global.

However, it occurred to me that the semantics I previously gave are
insufficient for splitting, because this instruction:

  %q = getelementptr i32*, i32** %p, i32 4

would satisfy the "one-past-the-end" rule, and as such would not be a
poison value, and the program would be able to load from it to produce the
value 5.

I think the solution is to specify index inbounds in terms of loads and
stores, by replacing the sentence you referred to with the following:

"Loading from or storing to any pointer derived from a getelementptr has
undefined behavior if any of the indices of the getelementptr are marked as
inbounds and the load or store would access memory outside of the bounds of
the element selected by the index marked as inbounds."

To conclude this example, let's look at strengthening or weakening the
guarantee by placing the keyword on different indices. Suppose we introduce
this constant:

@x00 = constant i32* getelementptr inbounds ([2 x [2 x [2 x i32]]], [2 x [2
x [2 x i32]]]* @x, i32 0, i32 0, inbounds i32 0, i32 0)

Now the pointer that x00 is initialized to refers to the subelement {1,2}
of x (being the element referred to by the third index), although that
doesn't really help us split the constant because the existence of the
initializer in x0 requires that we keep {1,2} and {3,4} together.
Similarly, if we introduce this constant:

@x_all = constant i32* getelementptr inbounds ([2 x [2 x [2 x i32]]], [2 x
[2 x [2 x i32]]]* @x, inbounds i32 0, i32 0, i32 0, i32 0)

this reference to x does not make any guarantees about which subelements a
derived pointer may access. As such, the elements {{1,2},{3,4}} and
{{5,6},{7,8}} must be kept together as in the original global if this
constant appears in the program.

> I know what it means for inbounds to be on the GEP but none of the
> indices: that's the GEP of today.
> What does it mean for the GEP to be marked inbound while only some of the
> indices are inbounds?  What if the GEP isn't marked inbounds?
> What does it mean if all the GEP indices are marked inbounds but the GEP
> isn't marked inbounds?
>
Interesting points. Having thought about this further, it seems that we do
not need to allow multiple inbounds annotations on indices, as each
inbounds annotation will be at least as restrictive as an earlier one. For
example, in:

i32* getelementptr inbounds ([2 x [2 x [2 x i32]]], [2 x [2 x [2 x i32]]]*
@x, i32 0, inbounds i32 0, inbounds i32 0, i32 0)

the two inbounds markers would respectively guarantee that the pointer will
only access {{1,2},{3,4}} and {1,2}, and the latter implies the former.

Regarding the relationship with GEP inbounds: it does seem that the two
properties are somewhat orthogonal, as GEP inbounds guarantees that while
being calculated a pointer is within a dynamic address range (dependent on
object size), while index inbounds guarantees that once calculated a
pointer (and its derivatives) are within a static address range.

A possible semantic simplification could be to specify that index inbounds
also implies the dynamic address range guarantee, but I don't think we
should do that, because a program (or opt pass) may wish to adjust an index
inbounds pointer outside of the static range, which would potentially
invalidate GEP inbounds without invalidating index inbounds.

Given that the two properties are orthogonal, perhaps we should use a
different keyword for index inbounds...

> GEPs are folded and optimized, two GEPs can compute the same numeric
> position with differing indices.  What happens when we are giving out new
> indices for a GEP with one (or more) inbounds index?
>
> I'm also a little confused when you talk about pointers derived from
the
> GEP being outside of the bounds... The inbounds of present day GEP refers
> to the base pointer and offsets, it does not directly have semantics on
> pointers derived from such a GEP.  This means it is perfectly OK to have an
> out of bounds GEP of an inbounds GEP.  My reading of your extension says
> that this is not possible...
>
Right, this is not possible with index inbounds in that the derived pointer
cannot be loaded from or stored to.

Peter

>
>> The main motivation is to allow the optimizer to split vtable groups
>> along vtable boundaries thus reducing code size when certain compiler
>> features [1] are enabled, in a way that avoids breaking ABI. The idea
is
>> that it would be safe to split only if the vtable has local linkage and
>> each reference to the global has an inbounds keyword on the correct
index.
>> If both of these conditions are satisfied, the address of the entire
global
>> is known to not be taken, and therefore a split would not break
semantics.
>> The new attribute could also potentially be used with other features
such
>> as alias analysis.
>>
>> This proposal arises from some concerns raised by Eli at
>> http://reviews.llvm.org/D22295 regarding an earlier implementation of
>> global splitting, which was based on metadata. I'm posting this new
>> proposal as an RFC as the increased intrusiveness in the IR warrants
>> greater visibility.
>>
>> Example
>>
>> i8** getelementptr inbounds ({[4 x i8*], [4 x i8*]}, {[4 x i8*], [4 x
>> i8*]}* @_ZTVfoo, i32 0, inbounds i32 1, i32 2)
>>
>> This is a reference to the address point of the second element of
>> _ZTVfoo, a virtual table group with two virtual tables, such that any
>> pointer extending beyond the bounds of the second virtual table is a
poison
>> value.
>>
>> Alternatives
>>
>> We could consider attaching metadata to globals as proposed and
>> implemented in D22295, which would avoid extending the constant
expression
>> IR. However as pointed out by Eli this is problematic because
optimization
>> passes may plausibly rebuild globals in non-permitted ways, for example
by
>> deriving a pointer to one past the end of a partition (which may cause
it
>> to point to another global).
>>
>> We could consider using intrinsics instead of constant expressions to
>> represent references to partitions. However this is not enough at least
for
>> vtables because other globals (e.g. VTTs) may need to contain pointers
to
>> vtables.
>>
>> Thanks,
>> --
>> Peter
>>
>> [1] Specifically, if either of the whole-program devirtualization or
>> control flow integrity features are being used. In the former case,
under
>> virtual constant propagation we are able to place propagated constants
>> directly in front of virtual tables of classes with multiple bases. In
the
>> latter case, we can arrange virtual tables with multiple bases in a
more
>> hierarchical order, which reduces the required amount of runtime data
and
>> simplifies the required checks.
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>

-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160719/92de68aa/attachment.html>

On Tue, Jul 19, 2016, at 03:02 AM, Peter Collingbourne via llvm-dev
wrote:
> Hi all,
> 
> I'd like to propose an IR extension that allows the inbounds keyword to
> be
> attached to indices in a getelementptr constantexpr.
Hi Peter,

this proposal (in its updated version with load/stores triggering the
undef) is a good idea. It will also help to propagate out-of-bounds
information from C to LLVM-IR, which we are currently lacking at IR
level. As a result, multi-dimensional data-dependence analysis must
either take possible out-of-bounds accesses into consideration or emit
run-time checks to be correct. In Polly we have already been considering
to pass the information provided by your inbounds keywords  using
llvm.assume [1], to avoid this additional complexity. However,  as this
is littering the IR with assumptions, the relevant patch  was never
proposed for integration. Your approach is well targeted and  due to the
additional use cases you mention especially appealing. 

Best,
Tobias

[1] https://llvm.org/bugs/show_bug.cgi?id=27067

Thanks Tobias. I've sent https://reviews.llvm.org/D22793 which implements
this IR extension, and updated D22295 to use the extension.

Peter

On Tue, Jul 19, 2016 at 10:55 PM, Tobias Grosser <tobias at grosser.es>
wrote:
> On Tue, Jul 19, 2016, at 03:02 AM, Peter Collingbourne via llvm-dev
> wrote:
> > Hi all,
> >
> > I'd like to propose an IR extension that allows the inbounds
keyword to
> > be
> > attached to indices in a getelementptr constantexpr.
>
> Hi Peter,
>
> this proposal (in its updated version with load/stores triggering the
> undef) is a good idea. It will also help to propagate out-of-bounds
> information from C to LLVM-IR, which we are currently lacking at IR
> level. As a result, multi-dimensional data-dependence analysis must
> either take possible out-of-bounds accesses into consideration or emit
> run-time checks to be correct. In Polly we have already been considering
> to pass the information provided by your inbounds keywords  using
> llvm.assume [1], to avoid this additional complexity. However,  as this
> is littering the IR with assumptions, the relevant patch  was never
> proposed for integration. Your approach is well targeted and  due to the
> additional use cases you mention especially appealing.
>
> Best,
> Tobias
>
> [1] https://llvm.org/bugs/show_bug.cgi?id=27067
>


-- 
-- 
Peter
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160725/b310f1d4/attachment.html>