Page MenuHomePhabricator

IR: Introduce inbounds attribute on getelementptr indices.
ClosedPublic

Authored by pcc on Jul 25 2016, 5:41 PM.

Details

Summary

If the inbounds keyword is present before any index, loading from or
storing to any pointer derived from the getelementptr has undefined
behavior if the load or store would access memory outside of the bounds of
the element selected by the index marked as inbounds.

This can be used, e.g. for alias analysis or to split globals at element
boundaries where beneficial.

As previously proposed on llvm-dev:
http://lists.llvm.org/pipermail/llvm-dev/2016-July/102472.html

Event Timeline

pcc updated this revision to Diff 65454.Jul 25 2016, 5:41 PM
pcc retitled this revision from to IR: Introduce inbounds attribute on getelementptr indices..
pcc updated this object.
pcc added a subscriber: llvm-commits.
majnemer edited edge metadata.Jul 26 2016, 7:59 AM

Seeing as how this doesn't have to do with the original inbounds attribute, perhaps we should call it something else?
Maybe inrange or withinrange? Not sure...

Will this play well with GetUnderlyingObject? Aren't we using it in some places to rewrite the memory accesses? Will this feature be intrusive in all the code that deal with GEP and memory accesses to honor/preserve this "inbound"?

pcc added a comment.Jul 26 2016, 11:50 AM

I think my concern with a separate keyword was that it would essentially need to be a synonym of inbounds in order to be descriptive, and I generally prefer not to use synonyms to refer to different things, as that can be confusing. But maybe using the same keyword would be even more confusing, and perhaps the overriding concern here should be searchability in langref. With that considered, I think I'm ok with inrange.

pcc added a comment.Jul 26 2016, 12:07 PM

Will this play well with GetUnderlyingObject? Aren't we using it in some places to rewrite the memory accesses?

That should be fine. If we do end up splitting an object, the underlying object will change, but by the rules of this annotation, that change would be unobservable.

Will this feature be intrusive in all the code that deal with GEP and memory accesses to honor/preserve this "inbound"?

Passes are free to discard this annotation, it's similar to metadata in that way.

I think you need to update andIRFlags.

include/llvm/IR/Operator.h
384–387 ↗(On Diff #65454)

How will this play with intersectOptionalDataWith?

eli.friedman edited edge metadata.Jul 26 2016, 12:42 PM

(I'll refer to the new attribute as inrange to try to avoid confusion.)

Does the way you're using subclass data mean that GVN just works correctly without any additional changes? Or does it need to be modified to avoid unifying a non-inrange GEP with an inrange GEP?

inrange markings probably interact badly with certain existing optimizations; for example, a gep with all zero indexes plus a bitcast currently gets folded into just a bitcast, but that loses the inrange marking. Not a correctness problem, but it'll probably be difficult to fix the resulting missed optimizations.

We'll probably have to be extremely cautious in terms of how we actually use inrange in clang. Applying inrange to a computation like "&p->a" is theoretically allowed by the C standard, but likely to cause problems in practice. Specifically, we could end up breaking programs without any good way to find the problem. Existing tools like valgrind and asan can't detect this sort of issue at all. That's more of a question of what makes sense for clang rather than something which affects the attribute itself... but if clang can't really use inrange markings outside of vtables, that reduces the utility a lot.

pcc added a comment.Jul 26 2016, 1:57 PM

Does the way you're using subclass data mean that GVN just works correctly without any additional changes? Or does it need to be modified to avoid unifying a non-inrange GEP with an inrange GEP?

If we allow this attribute on instructions, we would need to modify andIRFlags to recognize the new attribute, as David mentioned. At the moment, we only allow it on constants (I will document this more clearly).

inrange markings probably interact badly with certain existing optimizations; for example, a gep with all zero indexes plus a bitcast currently gets folded into just a bitcast, but that loses the inrange marking.

That specific fold is one that I inhibited, see lib/IR/ConstantFold.cpp, line 551.

Not a correctness problem, but it'll probably be difficult to fix the resulting missed optimizations.

While working on this patch I did try to identify any missed optimizations specific to vtables by hacking in some code like this:

diff --git a/lib/IR/Constants.cpp b/lib/IR/Constants.cpp
index 1fbd75f..1d445ff 100644
--- a/lib/IR/Constants.cpp
+++ b/lib/IR/Constants.cpp
@@ -1940,6 +1940,13 @@ Constant *ConstantExpr::getGetElementPtr(Type *Ty, Constant *C,
     ArgVec.push_back(Idx);
   }
 
+#if 0
+  if (isa<GlobalVariable>(C) && C->getName().startswith("_ZTV") &&
+      C->getName().find("type_info") == StringRef::npos &&
+      (!InBoundsIndex || *InBoundsIndex != 1))
+    abort();
+#endif
+
   unsigned SubClassOptionalData = InBounds ? GEPOperator::IsInBounds : 0;
   if (InBoundsIndex && *InBoundsIndex < 63)
     SubClassOptionalData |= (*InBoundsIndex + 1) << 1;

The constant folding changes I made in this patch were sufficient to be able to compile Chromium on Linux without aborting (with the above code turned on) and without a regression in binary size.

I'm not sure if there's a better way in general to track missed optimizations.

That's more of a question of what makes sense for clang rather than something which affects the attribute itself... but if clang can't really use inrange markings outside of vtables, that reduces the utility a lot.

You have a point there, but I'd expect that frontends for more memory safe languages may be able to make more extensive use of this attribute than clang.

In D22793#496473, @pcc wrote:

Passes are free to discard this annotation, it's similar to metadata in that way.

Oh, that wasn't clear to me.

We'll probably have to be extremely cautious in terms of how we actually use inrange in clang. Applying inrange to a computation like "&p->a" is theoretically allowed by the C standard, but likely to cause problems in practice. Specifically, we could end up breaking programs without any good way to find the problem. Existing tools like valgrind and asan can't detect this sort of issue at all. That's more of a question of what makes sense for clang rather than something which affects the attribute itself... but if clang can't really use inrange markings outside of vtables, that reduces the utility a lot.

Isn't it similar to TBBA? What kind of extra problem do you anticipate?
You may be able to chime in on this related thread on llvm-dev currently: https://groups.google.com/forum/#!topic/llvm-dev/Lc8POEocCX8

It's similar to TBAA, I guess... TBAA tends to cause problems too; fno-strict-aliasing is popular for a reason. :)

pcc added a comment.Jul 26 2016, 3:08 PM

I think you need to update andIRFlags.

Because this attribute is not currently supported on instructions, we don't need to do that yet.

include/llvm/IR/Operator.h
384–387 ↗(On Diff #65454)

We discussed this on IRC and concluded that we can remove that function (D22830).

pcc updated this revision to Diff 65615.Jul 26 2016, 3:08 PM
pcc edited edge metadata.
  • Rename inbounds -> inrange
pcc updated this revision to Diff 65626.Jul 26 2016, 4:20 PM
  • Add language to langref forbidding certain pointer comparisons involving inrange GEPs
hfinkel edited edge metadata.Jul 26 2016, 4:28 PM

It's similar to TBAA, I guess... TBAA tends to cause problems too; fno-strict-aliasing is popular for a reason. :)

I think we should follow the same approach here. Just like with TBAA, and with nsw on integer operations, we produce the flag when possible, and add a command-line option to turn it off.

hfinkel added inline comments.Jul 26 2016, 4:37 PM
docs/LangRef.rst
7551 ↗(On Diff #65626)

I don't think we should limit this to constant expressions. We should be able to use this to model p.x[i] vs. p.y. Removing the restriction to constant expressions will also mean you need to generalize the text about pointer comparisons: instead of saying that all operands must be identical, you'll need to say that the same elements need to be selected (or something like that).

include/llvm/IR/Operator.h
382 ↗(On Diff #65626)

Can more than once index have inrange on it? It looks like no, but this is not clear from the LangRef, and I don't understand that restriction regardless.

majnemer added inline comments.Jul 26 2016, 4:58 PM
docs/LangRef.rst
7546–7549 ↗(On Diff #65626)

What if I do a ptrtoint and compare the ints?

pcc added inline comments.Jul 26 2016, 5:06 PM
docs/LangRef.rst
7546–7549 ↗(On Diff #65626)

Yes, good point. "pointer comparison" can just become "comparison" then, I think.

7551 ↗(On Diff #65626)

Seems reasonable enough, but I'm not sure if I'll have any time soon to implement this for non-constants. Perhaps the non-constant implementation can be a separate patch.

include/llvm/IR/Operator.h
382 ↗(On Diff #65626)

No more than one. The rationale is that inrange on a given index will be at least as restrictive as inrange on any earlier index, so there's no point in allowing more than one. I'll document this in the langref.

hfinkel added inline comments.Jul 26 2016, 5:21 PM
docs/LangRef.rst
7551 ↗(On Diff #65626)

Aside from the LangRef, what needs to change to allow non-constant indicies? I think they should be allowed, even if taking advantage of them is future work. I don't see anything in the parser changes that forbids them.

pcc added inline comments.Jul 26 2016, 5:29 PM
docs/LangRef.rst
7551 ↗(On Diff #65626)

We would need printing and parsing support, as well as a bitcode representation for getelementptr instructions (as opposed to only constants) with an inrange annotation. Should be straightforward, but a non-zero amount of work.

hfinkel added inline comments.Jul 26 2016, 5:36 PM
docs/LangRef.rst
7551 ↗(On Diff #65626)

Ah, so it only applies to constants right now, not to actual GEP instructions. I see what you mean now, but when I originally read the text, I thought that you meant that the index expression needed to be constant, not that the entire GEP needed to be a constant.

sanjoy added a subscriber: sanjoy.Jul 26 2016, 5:59 PM
sanjoy added inline comments.
docs/LangRef.rst
7550 ↗(On Diff #65626)

This is a little odd since (IIUC) it implies that replacing an inrange GEP with a not inrange version of the same GEP can introduce undefined behavior; that is:

x0 = gep_inrange(A, 42)
x1 = gep_normal(A, 42)
result = x0 == x0 ;; perhaps hidden behind a function

to

x0 = gep_inrange(A, 42)
x1 = gep_normal(A, 42)
result = x0 == y0 ;; perhaps hidden behind a function

via x1->replaceAllUsesWith(x0).

Why do you need this property / caveat?

7551 ↗(On Diff #65626)

Given that, it is probably better to say "allowed in constant getelementptr expressions"

eli.friedman added inline comments.Jul 26 2016, 6:01 PM
docs/LangRef.rst
7548 ↗(On Diff #65626)

Hmm... this sort of restricts the possible uses of the marking. For example, given:

struct X {
    int x, y[2];
};
int f(struct X *x, int i) { return x->y[i]; }
int *f2(struct X *x) { return x->y; }

We can mark the GEP in x->y[i] inrange, but we can't mark the GEP in x->y inrange because it could be used in a pointer comparison. I guess that's okay (the stated form is convenient for performing SROA). That said, inevitably someone is going to push for a version which doesn't make comparisons undefined so it can be used more aggressively in C code.

You should probably state explicitly that the result of converting an inrange pointer to an integer is undef; you can't actually do anything useful with the result anyway.

sanjoy added inline comments.Jul 26 2016, 6:05 PM
docs/LangRef.rst
7550 ↗(On Diff #65626)

There's a typo, in the transformed snippet we should have result = x0 == x1. Also pretend that there are other uses of x1 (so it isn't trivially DCE'ed away).

hfinkel added inline comments.Jul 26 2016, 6:09 PM
docs/LangRef.rst
7548 ↗(On Diff #65626)

What's the motivation for the current language? I don't think we can have anything that strict.

eli.friedman added inline comments.Jul 26 2016, 6:54 PM
docs/LangRef.rst
7547 ↗(On Diff #65626)

I think this is supposed to be "if both operands were derived from an inrange GEP"?

7548 ↗(On Diff #65626)

The motivation here is that we want to be able to say "if every use of a given global is an inrange GEP, SROA is legal (i.e. we can split the global)". That requires some sort of restriction on comparisons because we could change the result of a comparison in an unpredictable way.

pcc added inline comments.Jul 26 2016, 6:55 PM
docs/LangRef.rst
7548 ↗(On Diff #65626)

The intent was to allow optimization passes to re-arrange elements of an indexed object (i.e. what SplitGlobals does). Although at this point it does seem that trying to restrict pointer comparisons in general would be likely to make this too restrictive for use by C family frontends. Instead I think the best approach would be to change SplitGlobals to check for the unnamed_addr attribute, and remove the pointer comparison language here.

You should probably state explicitly that the result of converting an inrange pointer to an integer is undef;

Will do.

7550 ↗(On Diff #65626)

I think this is moot in light of my other comment.

7551 ↗(On Diff #65626)

Will do

hfinkel added inline comments.Jul 26 2016, 7:06 PM
docs/LangRef.rst
7548 ↗(On Diff #65626)

I'd think that we just need to check the use-def chains, starting with uses of the global, to see if the address was captured.

pcc added inline comments.Jul 26 2016, 7:10 PM
docs/LangRef.rst
7548 ↗(On Diff #65626)

The problem with that, at least for vtables, is that the vtable address will be captured in most normal cases (e.g. the constructor will store the vtable address in the object's vtable pointer). So for split globals I think we need to rely on unnamed_addr here.

hfinkel added inline comments.Jul 26 2016, 7:14 PM
docs/LangRef.rst
7548 ↗(On Diff #65626)

That makes sense.

pcc updated this revision to Diff 65650.Jul 26 2016, 7:21 PM
pcc edited edge metadata.
  • Remove pointer comparison language. Explicitly forbid ptrtoint. Clarify language related to constant expressions.
In D22793#497101, @pcc wrote:
  • Remove pointer comparison language. Explicitly forbid ptrtoint. Clarify language related to constant expressions.

If we're relying on unnamed_addr, why do you need to forbid ptrtoint?

pcc added a comment.Jul 26 2016, 7:28 PM

On second thoughts, that restriction doesn't seem necessary, so I've removed it.

pcc updated this revision to Diff 65651.Jul 26 2016, 7:28 PM
  • Remove ptrtoint restriction
delena added a subscriber: delena.Jul 27 2016, 1:37 PM

I think that "inrange" mark for non-constant indices will help to handle x.y[i] cases. Do you plan to cover non-constant indices?

pete added a subscriber: pete.Jul 27 2016, 6:29 PM
pete added inline comments.
include/llvm/IR/Operator.h
382 ↗(On Diff #65651)

Sorry to come late to this one...

My read on this implies that inrange on the start of a GEP would be equivalent to inbounds today. Is that the case?

Assuming it is, the inrange is strictly a more accurate version of inbounds, and we should only have inrange. Put another way, keep the name inbounds, but allow it to be applied to any single type in the GEP.

So that would make all of these equivalent in terms of AA, and all of these alias each other:

%arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, i32 2
%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 1, i32 2
%arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, inbounds i32 2

But these won't alias because the inbounds applies to an index with a different value:

%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 0, i32 2
%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 1, i32 2

And these will alias because one has inbounds and the other doesn't:

%arrayidx = getelementptr %struct.ST, %struct.ST* %s, i64 0, i32 2
%arrayidx = getelementptr %struct.ST, %struct.ST* %s, inbounds i64 1, i32 2
pcc added a comment.Sep 7 2016, 11:51 AM

Apologies for the delayed response, I just returned from a long vacation.

include/llvm/IR/Operator.h
382 ↗(On Diff #65651)

My read on this implies that inrange on the start of a GEP would be equivalent to inbounds today. Is that the case?

No. The inbounds keyword is a bounds restriction with regard to the allocated object, while inrange on the start of the GEP is a bounds restriction with regard to the GEP element type (or subelement type). The inrange restriction also applies to any pointers derived from the inrange GEP, while this isn't the case for inbounds. So, for example if you have an allocated object of type [2 x %struct.ST] and a pointer %s referring to its first element, and the instructions

%i1 = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 0
%i2 = getelementptr %struct.ST, %struct.ST* %s, inrange i64 0

the instruction

%i1a = getelementptr %struct.ST, %struct.ST* %i1, i64 1

would yield a pointer to the second element of the allocated object but the instruction

%i2a = getelementptr %struct.ST, %struct.ST* %i2, i64 1

would yield an undefined value.

pcc updated this revision to Diff 70625.Sep 7 2016, 4:57 PM
  • Forbid pointer comparison and ptrtoint as discussed
mehdi_amini added inline comments.Sep 7 2016, 5:06 PM
docs/LangRef.rst
7549 ↗(On Diff #70625)

Isn't it hard to guarantee in face of transformations?

Let say a pass would do outlining, passing the pointer derived from the GEP by argument, in this new function the inrange information would be lost and another transformation allowed to introduce a pointer comparison.

pcc added inline comments.Sep 7 2016, 5:30 PM
docs/LangRef.rst
7549 ↗(On Diff #70625)

Hrm, yes, I think you're right. It looks like we can't avoid specifying exactly which comparisons are allowable in practice.

Taking into account Sanjoy's point from earlier, I believe this would suffice:

The result of a pointer
comparison or ``ptrtoint`` involving a pointer derived from a ``getelementptr``
with the ``inrange`` keyword is undefined, with the exception of comparisons in the case
where both operands are in the range of the element selected by the ``inrange`` keyword,
inclusive of the address one past the end of that element.
pcc updated this revision to Diff 75491.Oct 21 2016, 2:51 PM

Refresh; incorporate my suggested wording change

I haven't reviewed the assembly and bitcode reading/writing changes.

The semantics here look right.

llvm/docs/LangRef.rst
7579

Might want to clarify that this includes ptrtoint-like operations involving memory.

llvm/include/llvm/IR/Operator.h
387

Please add a comment somewhere describing exactly how many bits are dedicated to InRangeIndex.

llvm/lib/Analysis/ConstantFolding.cpp
950

Should we preserve inbounds here? (Please add a FIXME if it's complicated somehow.)

970

Does this patch affect this TODO somehow?

llvm/lib/IR/ConstantFold.cpp
551

This is a little awkward... but I don't really see an alternative; it's okay, I guess.

pcc updated this revision to Diff 77305.Nov 8 2016, 7:34 PM
pcc marked 2 inline comments as done.
  • Address review comments
llvm/lib/Analysis/ConstantFolding.cpp
950

My first impression is that it would be sound to preserve inbounds if all GEPs are inbounds, which is what D26441 does. Let's deal with that orthogonally though.

970

I guess it would be covered by the "etc" :)

But added to be explicit.

llvm/lib/IR/ConstantFold.cpp
551

Right, this should be no longer needed in the typeless pointer world anyway.

Okay, that addresses my comments. (I haven't tried to review the bitcode/assembly reading/writing changes; I'm hoping you can find someone else to review that.)

pcc added a comment.Nov 10 2016, 1:52 PM

@eugenis may I ask you to review the rest of this patch?

The implementation looks good to me.

include/llvm/IR/Constants.h
1079 ↗(On Diff #70625)

Update the doxygen.

lib/Analysis/ConstantFolding.cpp
906 ↗(On Diff #70625)

s/inbounds/inrange/

This revision was automatically updated to reflect the committed changes.
pcc marked 2 inline comments as done.