Carry facts about nullness and undef across GC relocation

[reames]

Summary

This change implements four basic optimizations:

• If a relocated value isn't used, it doesn't need to be relocated.
• If the value being relocated is null, relocation doesn't change that. (Technically, this might be collector specific. I don't know of one which it doesn't work for though.)
• If the value being relocated is undef, the relocation is meaningless.
• If the value being relocated was known nonnull, the relocated pointer also isn't null. (Since it points to the same source language object.)

I outlined other planned work in comments.

[sanjoy]

LGTM with comments addressed.

lib/Transforms/InstCombine/InstCombineCalls.cpp

1160 ↗

(On Diff #17136)

While I'm okay with keeping in this clause for now, I'm not comfortable with it.

What you're effectively saying here is that given any bit pattern P, there a source pattern Q such that P = relocate(Q). But there may be collectors that do not map to specific address patterns. For example, in x86-64, I think most collectors won't map any address to, say, ((void *) -1) because that is outside the 48 bit range.

1165 ↗

(On Diff #17136)

Nit: should this be "almost any collector"?

1167 ↗

(On Diff #17136)

Isn't this check the same as isa<ConstantPointerNull>(DerivedPtr)?

[reames]

Response to Sanjoy's comments.

lib/Transforms/InstCombine/InstCombineCalls.cpp

1160 ↗

(On Diff #17136)

I think this actually is legal. The bitpattern before relocation can be any bit pattern. We've got two cases:

• it's an address on which relocation is well defined (for a given collector), in which case some unknown value (with a possibly restricted value) would be the right result. Undef is not a valid result in this case.
• it's an address on which relocation is not well defined. i.e. we could pick it to be relocate(-1) Given this is not a well defined operation, we are free to pick any bit pattern as output. Undef is a valid result.

My argument that be that relocating undef can always be chosen to by the second case. I don't know of a collector with exactly specified relocations for any arbitrary address. Do you disagree?

1167 ↗

(On Diff #17136)

I *think* so, but am not entirely sure.

[sanjoy]

lib/Transforms/InstCombine/InstCombineCalls.cpp

1160 ↗

(On Diff #17136)

But then you're assuming that there is such a value as ((void *) -1) relocating which is undefined behavior. This is an assumption on relocation semantics which may not be true, for instance, on a 32 bit machine.

I think this property is very similar to stating gcrelocate(null) == null -- true for most practical GCs, but the "Right Thing" to do is to provide a hook in GCStrategy as you've mentioned later.

llvm/trunk/include/llvm/IR/Statepoint.h

public:
   int basePtrIndex() {
     return cast<ConstantInt>(RelocateCS.getArgument(1))->getZExtValue();
   }
   /// The index into the associate statepoint's argument list which
   /// contains the pointer whose relocation this gc.relocate describes.
   int derivedPtrIndex() {
     return cast<ConstantInt>(RelocateCS.getArgument(2))->getZExtValue();
   }
-  const Value *basePtr() {
+  Value *basePtr() {
     ImmutableCallSite CS(statepoint());
     return *(CS.arg_begin() + basePtrIndex());
   }
-  const Value *derivedPtr() {
+  Value *derivedPtr() {
     ImmutableCallSite CS(statepoint());
     return *(CS.arg_begin() + derivedPtrIndex());
   }
 };
 }
 #endif

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::assume: {
     // then this one is redundant, and should be removed.
     APInt KnownZero(1, 0), KnownOne(1, 0);
     computeKnownBits(IIOperand, KnownZero, KnownOne, 0, II);
     if (KnownOne.isAllOnesValue())
       return EraseInstFromFunction(*II);
 
     break;
   }
+  case Intrinsic::experimental_gc_relocate: {
+    // Translate facts known about a pointer before relocating into
+    // facts about the relocate value, while being careful to
+    // preserve relocation semantics.
+    GCRelocateOperands Operands(II);
+    Value *DerivedPtr = Operands.derivedPtr();
+
+    // Remove the relocation if unused, note that this check is required
+    // to prevent the cases below from looping forever.
+    if (II->use_empty())
+      return EraseInstFromFunction(*II);
+
+    // Undef is undef, even after relocation.
+    // TODO: provide a hook for this in GCStrategy.  This is clearly legal for
+    // most practical collectors, but there was discussion in the review thread
+    // about whether it was legal for all possible collectors.
+    if (isa<UndefValue>(DerivedPtr))
+      return ReplaceInstUsesWith(*II, DerivedPtr);
+
+    // The relocation of null will be null for most any collector.
+    // TODO: provide a hook for this in GCStrategy.  There might be some weird
+    // collector this property does not hold for.
+    if (isa<ConstantPointerNull>(DerivedPtr))
+      return ReplaceInstUsesWith(*II, DerivedPtr);
+
+    // isKnownNonNull -> nonnull attribute
+    if (isKnownNonNull(DerivedPtr))
+      II->addAttribute(AttributeSet::ReturnIndex, Attribute::NonNull);
+
+    // TODO: dereferenceable -> deref attribute
+
+    // TODO: bitcast(relocate(p)) -> relocate(bitcast(p))
+    // Canonicalize on the type from the uses to the defs
+    
+    // TODO: relocate((gep p, C, C2, ...)) -> gep(relocate(p), C, C2, ...)
+  }
   }
 
   return visitCallSite(II);
 }
 
 // InvokeInst simplification
 //
 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {

llvm/trunk/test/Transforms/InstCombine/statepoint.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+; These tests check the optimizations specific to
+; pointers being relocated at a statepoint.
+
+
+declare void @func()
+
+define i1 @test_negative(i32 addrspace(1)* %p) {
+entry:
+  %safepoint_token = tail call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0, i32 addrspace(1)* %p)
+  %pnew = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32 %safepoint_token, i32 4, i32 4)
+  %cmp = icmp eq i32 addrspace(1)* %pnew, null
+  ret i1 %cmp
+; CHECK-LABEL: test_negative
+; CHECK: %pnew = call i32 addrspace(1)*
+; CHECK: ret i1 %cmp
+}
+
+define i1 @test_nonnull(i32 addrspace(1)* nonnull %p) {
+entry:
+  %safepoint_token = tail call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0, i32 addrspace(1)* %p)
+  %pnew = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32 %safepoint_token, i32 4, i32 4)
+  %cmp = icmp eq i32 addrspace(1)* %pnew, null
+  ret i1 %cmp
+; CHECK-LABEL: test_nonnull
+; CHECK: ret i1 false
+}
+
+define i1 @test_null() {
+entry:
+  %safepoint_token = tail call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0, i32 addrspace(1)* null)
+  %pnew = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32 %safepoint_token, i32 4, i32 4)
+  %cmp = icmp eq i32 addrspace(1)* %pnew, null
+  ret i1 %cmp
+; CHECK-LABEL: test_null
+; CHECK-NOT: %pnew
+; CHECK: ret i1 true
+}
+
+define i1 @test_undef() {
+entry:
+  %safepoint_token = tail call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @func, i32 0, i32 0, i32 0, i32 addrspace(1)* undef)
+  %pnew = call i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32 %safepoint_token, i32 4, i32 4)
+  %cmp = icmp eq i32 addrspace(1)* %pnew, null
+  ret i1 %cmp
+; CHECK-LABEL: test_undef
+; CHECK-NOT: %pnew
+; CHECK: ret i1 undef
+}
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()*, i32, i32, ...)
+declare i32 addrspace(1)* @llvm.experimental.gc.relocate.p1i32(i32, i32, i32) #3