[RewriteStatepointsForGC] All constant should have null base pointer

[igor-laevsky]

Summary

Currently we consider that each constant has itself as a base value. I.e "base(const) = const". This introduces couple of problems when we are trying to avoid reporting constants in statepoint live sets:

1. When querying "base( phi(const1, const2) )" we will get "phi(const1, const2)" as a base pointer. Since it's not a constant we will record it in a stack map. However on practice we don't want this to happen (constant are never relocated).
2. base( phi(const, gc ptr) ) = phi( const, base(gc ptr) ). This particular case imposes challenge on our runtime - we don't expect to see constant base pointers other than null.

This problems can be avoided by treating all constant as if they were derived from null pointer base. I.e in a first case we will not include constant pointer in a stack map at all. In a second case we will get "phi(null, base(gc ptr))" as a base pointer which is a lot more convenient.

@Manuel, I understand that your use case of the RS4GC is sensitive to how we handle global variables. Could you please take a look so that this change doesn't bring you any problems?

[mjacob]

I don't think this will bring any problems. My collector just ignores constant bases. Note that also before this change findBaseDefiningValue() didn't necessarily actually return the right value. E.g. calling it with a GEP on a global will return the GEP instead of the global.

[igor-laevsky]

ping?

[sanjoy]

lgtm

We can potentially consider doing something friendlier for cases like base-pointers-12.ll (i.e. report @global as the base pointer for those cases in the future, but for now this is fine.

llvm/trunk/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

findBaseDefiningValueOfVector(Value *I) {
   // Each case parallels findBaseDefiningValue below, see that code for
   // detailed motivation.
 
   if (isa<Argument>(I))
     // An incoming argument to the function is a base pointer
     return BaseDefiningValueResult(I, true);
 
   if (isa<Constant>(I))
-    // Constant vectors consist only of constant pointers.
-    return BaseDefiningValueResult(I, true);
+    // Base of constant vector consists only of constant null pointers. 
+    // For reasoning see similar case inside 'findBaseDefiningValue' function.
+    return BaseDefiningValueResult(ConstantAggregateZero::get(I->getType()),
+                                   true);
 
   if (isa<LoadInst>(I))
     return BaseDefiningValueResult(I, true);
 
   if (isa<InsertElementInst>(I))
     // We don't know whether this vector contains entirely base pointers or
     // not.  To be conservatively correct, we treat it as a BDV and will
     // duplicate code as needed to construct a parallel vector of bases.
static BaseDefiningValueResult findBaseDefiningValue(Value *I) {
   if (I->getType()->isVectorTy())
     return findBaseDefiningValueOfVector(I);
 
   if (isa<Argument>(I))
     // An incoming argument to the function is a base pointer
     // We should have never reached here if this argument isn't an gc value
     return BaseDefiningValueResult(I, true);
 
-  if (isa<Constant>(I))
+  if (isa<Constant>(I)) {
     // We assume that objects with a constant base (e.g. a global) can't move
     // and don't need to be reported to the collector because they are always
-    // live.  All constants have constant bases.  Besides global references, all
-    // kinds of constants (e.g. undef, constant expressions, null pointers) can
-    // be introduced by the inliner or the optimizer, especially on dynamically
-    // dead paths.  See e.g. test4 in constants.ll.
-    return BaseDefiningValueResult(I, true);
+    // live. Besides global references, all kinds of constants (e.g. undef, 
+    // constant expressions, null pointers) can be introduced by the inliner or
+    // the optimizer, especially on dynamically dead paths.
+    // Here we treat all of them as having single null base. By doing this we
+    // trying to avoid problems reporting various conflicts in a form of 
+    // "phi (const1, const2)" or "phi (const, regular gc ptr)".
+    // See constant.ll file for relevant test cases.
+
+    return BaseDefiningValueResult(
+        ConstantPointerNull::get(cast<PointerType>(I->getType())), true);
+  }
 
   if (CastInst *CI = dyn_cast<CastInst>(I)) {
     Value *Def = CI->stripPointerCasts();
     // If stripping pointer casts changes the address space there is an
     // addrspacecast in between.
     assert(cast<PointerType>(Def->getType())->getAddressSpace() ==
                cast<PointerType>(CI->getType())->getAddressSpace() &&
            "unsupported addrspacecast");

llvm/trunk/test/Transforms/RewriteStatepointsForGC/base-pointers-12.ll

 ; RUN: opt < %s -rewrite-statepoints-for-gc -spp-print-base-pointers -S 2>&1 | FileCheck %s
 
-; CHECK: derived %select base @global
+; CHECK: derived %select base null
 
 @global = external addrspace(1) global i8
 
 define i8 @test(i1 %cond) gc "statepoint-example" {
   %derived1 = getelementptr i8, i8 addrspace(1)* @global, i64 1
   %derived2 = getelementptr i8, i8 addrspace(1)* @global, i64 2
   %select = select i1 %cond, i8 addrspace(1)* %derived1, i8 addrspace(1)* %derived2
   call void @extern()

llvm/trunk/test/Transforms/RewriteStatepointsForGC/base-pointers-13.ll

 ; RUN: opt < %s -rewrite-statepoints-for-gc -spp-print-base-pointers -S 2>&1 | FileCheck %s
 
-; CHECK: derived %derived base @global
+; CHECK: derived %derived base null
 
 @global = external addrspace(1) global i8
 
 define i8 @test(i64 %offset) gc "statepoint-example" {
   %derived = getelementptr i8, i8 addrspace(1)* @global, i64 %offset
   call void @extern()
 ; CHECK-NOT: relocate
 ; CHECK-NOT: remat
 ; CHECK: %load = load i8, i8 addrspace(1)* %derived
   %load = load i8, i8 addrspace(1)* %derived
   ret i8 %load
 }
 
 declare void @extern() gc "statepoint-example"
 
 declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)

llvm/trunk/test/Transforms/RewriteStatepointsForGC/base-vector.ll

entry:
   call void @do_safepoint() [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
   call void @use(i64 addrspace(1)* %bdv)
   ret void
 }
 
 define void @test6(i1 %cnd, i64 addrspace(1)* %obj, i64 %idx) gc "statepoint-example" {
 ; CHECK-LABEL: @test6
 ; CHECK: %gep = getelementptr i64, i64 addrspace(1)* %obj, i64 1
-; CHECK: %vec.base = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %obj, i32 0, !is_base_value !0
+; CHECK: %vec.base = insertelement <2 x i64 addrspace(1)*> zeroinitializer, i64 addrspace(1)* %obj, i32 0, !is_base_value !0
 ; CHECK: %vec = insertelement <2 x i64 addrspace(1)*> undef, i64 addrspace(1)* %gep, i32 0
 ; CHECK: %bdv.base = extractelement <2 x i64 addrspace(1)*> %vec.base, i64 %idx, !is_base_value !0
 ; CHECK:  %bdv = extractelement <2 x i64 addrspace(1)*> %vec, i64 %idx
 ; CHECK: gc.statepoint
 ; CHECK: gc.relocate
 ; CHECK-DAG: (%bdv.base, %bdv)
 ; A more complicated example involving vector and scalar bases.
 ; This is derived from a failing test case when we didn't have correct

llvm/trunk/test/Transforms/RewriteStatepointsForGC/constants.ll

entry:
   ; Same as test7 but use regular constant instead of a null
   ; CHECK-LABEL: test7
   ; CHECK: gc.statepoint
   ; CHECK-NOT: call {{.*}}gc.relocate
   %load_addr = getelementptr i8, i8 addrspace(1)* inttoptr (i64 15 to i8 addrspace(1)*), i64 %arg
   call void @foo() [ "deopt"() ]
   ret i8 addrspace(1)* %load_addr
 }
+
+define i8 @test8(i8 addrspace(1)* %p) gc "statepoint-example" {
+; Checks that base( phi(gep null, oop) ) = phi(null, base(oop)) and that we
+; correctly relocate this value
+; CHECK-LABEL: @test8
+entry:
+  %is_null = icmp eq i8 addrspace(1)* %p, null
+  br i1 %is_null, label %null.crit-edge, label %not-null
+
+not-null:
+  %load_addr = getelementptr inbounds i8, i8 addrspace(1)* %p, i64 8
+  br label %join
+
+null.crit-edge:
+  %load_addr.const = getelementptr inbounds i8, i8 addrspace(1)* null, i64 8
+  br label %join
+
+join:
+  %addr = phi i8 addrspace(1)* [ %load_addr, %not-null ], [%load_addr.const, %null.crit-edge]
+  ; CHECK: %addr.base = phi i8 addrspace(1)*
+  ; CHECK-DAG: [ %p, %not-null ]
+  ; CHECK-DAG: [ null, %null.crit-edge ]
+  ; CHECK: gc.statepoint
+  call void @foo() [ "deopt"() ]
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%addr.base, %addr.base)
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%addr.base, %addr)
+  br i1 %is_null, label %early-exit, label %use
+
+early-exit:
+  ret i8 0
+
+use:
+  %res = load i8, i8 addrspace(1)* %addr, align 1
+  ret i8 %res
+}
+
+define i8 @test9(i8 addrspace(1)* %p) gc "statepoint-example" {
+; Checks that base( phi(inttoptr, oop) ) = phi(null, base(oop)) and that we
+; correctly relocate this value
+; CHECK-LABEL: @test9
+entry:
+  %is_null = icmp eq i8 addrspace(1)* %p, null
+  br i1 %is_null, label %null.crit-edge, label %not-null
+
+not-null:
+  %load_addr = getelementptr inbounds i8, i8 addrspace(1)* %p, i64 8
+  br label %join
+
+null.crit-edge:
+  br label %join
+
+join:
+  %addr = phi i8 addrspace(1)* [ %load_addr, %not-null ], [inttoptr (i64 8 to i8 addrspace(1)*), %null.crit-edge]
+  ; CHECK: %addr.base = phi i8 addrspace(1)*
+  ; CHECK-DAG: [ %p, %not-null ]
+  ; CHECK-DAG: [ null, %null.crit-edge ]
+  ; CHECK: gc.statepoint
+  call void @foo() [ "deopt"() ]
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%addr.base, %addr.base)
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%addr.base, %addr)
+  br i1 %is_null, label %early-exit, label %use
+
+early-exit:
+  ret i8 0
+
+use:
+  %res = load i8, i8 addrspace(1)* %addr, align 1
+  ret i8 %res
+}
+
+define i8 @test10(i8 addrspace(1)* %p) gc "statepoint-example" {
+; Checks that base( phi(const gep, oop) ) = phi(null, base(oop)) and that we
+; correctly relocate this value
+; CHECK-LABEL: @test10
+entry:
+  %is_null = icmp eq i8 addrspace(1)* %p, null
+  br i1 %is_null, label %null.crit-edge, label %not-null
+
+not-null:
+  %load_addr = getelementptr inbounds i8, i8 addrspace(1)* %p, i64 8
+  br label %join
+
+null.crit-edge:
+  br label %join
+
+join:
+  %addr = phi i8 addrspace(1)* [ %load_addr, %not-null ], [getelementptr (i8, i8 addrspace(1)* null, i64 8), %null.crit-edge]
+  ; CHECK: %addr.base = phi i8 addrspace(1)*
+  ; CHECK-DAG: [ %p, %not-null ]
+  ; CHECK-DAG: [ null, %null.crit-edge ]
+  ; CHECK: gc.statepoint
+  call void @foo() [ "deopt"() ]
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%addr.base, %addr.base)
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%addr.base, %addr)
+  br i1 %is_null, label %early-exit, label %use
+
+early-exit:
+  ret i8 0
+
+use:
+  %res = load i8, i8 addrspace(1)* %addr, align 1
+  ret i8 %res
+}
+
+define i32 addrspace(1)* @test11(i1 %c) gc "statepoint-example" {
+; CHECK-LABEL: @test11
+; Checks that base( select(const1, const2) ) == null and that we don't record
+; such value in the oop map
+entry:
+  %val = select i1 %c, i32 addrspace(1)* inttoptr (i64 8 to i32 addrspace(1)*), i32 addrspace(1)* inttoptr (i64 15 to i32 addrspace(1)*)
+  ; CHECK: gc.statepoint
+  ; CHECK-NOT: call {{.*}}gc.relocate
+  call void @foo() [ "deopt"() ]
+  ret i32 addrspace(1)* %val
+}
+
+
+define <2 x i32 addrspace(1)*> @test12(i1 %c) gc "statepoint-example" {
+; CHECK-LABEL: @test12
+; Same as test11 but with vectors
+entry:
+  %val = select i1 %c, <2 x i32 addrspace(1)*> <i32 addrspace(1)* inttoptr (i64 5 to i32 addrspace(1)*), 
+                                                i32 addrspace(1)* inttoptr (i64 15 to i32 addrspace(1)*)>, 
+                       <2 x i32 addrspace(1)*> <i32 addrspace(1)* inttoptr (i64 30 to i32 addrspace(1)*), 
+                                                i32 addrspace(1)* inttoptr (i64 60 to i32 addrspace(1)*)>
+  ; CHECK: gc.statepoint
+  ; CHECK-NOT: call {{.*}}gc.relocate
+  call void @foo() [ "deopt"() ]
+  ret <2 x i32 addrspace(1)*> %val
+}
+
+define <2 x i32 addrspace(1)*> @test13(i1 %c, <2 x i32 addrspace(1)*> %ptr) gc "statepoint-example" {
+; CHECK-LABEL: @test13
+; Similar to test8, test9 and test10 but with vectors
+entry:
+  %val = select i1 %c, <2 x i32 addrspace(1)*> %ptr, 
+                       <2 x i32 addrspace(1)*> <i32 addrspace(1)* inttoptr (i64 30 to i32 addrspace(1)*), i32 addrspace(1)* inttoptr (i64 60 to i32 addrspace(1)*)>
+  ; CHECK: %val.base = select i1 %c, <2 x i32 addrspace(1)*> %ptr, <2 x i32 addrspace(1)*> zeroinitializer, !is_base_value !0
+  ; CHECK: gc.statepoint
+  call void @foo() [ "deopt"() ]
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%val.base, %val.base)
+  ; CHECK-DAG: call {{.*}}gc.relocate{{.*}}(%val.base, %val)
+  ret <2 x i32 addrspace(1)*> %val
+}