[RS4GC] Fix crash in the case that a live variable has a constant base.

[mjacob]

Summary

Previously, RS4GC crashed in CreateGCRelocates() because it assumed
that every base is also in the array of live variables, which isn't true if a
live variable has a constant base.

This change fixes the crash by making sure CreateGCRelocates() won't try to
relocate a live variable with a constant base. This would be unnecessary
anyway because anything with a constant base won't move.

[reames]

Comments inline.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1620

I think the general approach of filtering the liveset here can work, but this is the wrong place for it. In particular, it's after the vector splitting and re-materialization logic. The vector splitting probably isn't an issue - I'm about to revise/remove that anyways - but the remat logic definitely has coupling with the relocation logic.

I think you probably should pull this out as a separate step between the recomputation of liveness after base pointer rewriting and the first use of the new liveness in splitVectorValues.

I'll also require much better comments. :) For instance, why does simply rewriting the live value as a constant-expr fail? (i.e. why is the right approach?)

p.s. A possible alternate approach would be to stop filtering constants from the liveset. In that case, we would have the live constant base in the liveset. Have you considered this option?

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

11

instead of undef, use an i1 argument.

A valid canonicalizing transform (i.e. simplifyInstruction) would break this test in a non-obvious way.

14

Add a check for the load from select.

[mjacob]

Address review comments.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1620

Agreed, filterung the liveset earlier makes sense. I'll also add a comment.

I'm not sure what you mean by "rewriting the live value as a constant-expr". Please clarify if that's still relevant for my next diff.

Adding the constant base to the liveset would probably solve the issue, too. However that would make the liveset bigger and would still need filtering later, at least for my custom stack map format which doesn't support constants.

[reames]

LGTM w/minor comments addressed.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2390

Can you give a small example here? It would make it easier to understand. Possibly: "for instance, a variable offset into a constant global"

2392

and that the GC doesn't otherwise need to know about them.

p.s. Does your GC actually have constant references? Or are these just small offsets off of null? That's the only case we've seen to date.

2394

relies on this filtering for correctness as it expects...

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

17

Can you add one or two other examples? For instance, a variable offset GEP from a global or a variable offset from a null pointer down a dead path?

[mjacob]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2392

Yes, my GC has constant references. GC objects in constants are immortal (they can't be deallocated), so they don't have to be reported by the statepoint mechanism. There is a separate mechanism that tracks references from immortal objects to potentially non-immortal objects.

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

17

Should they go to another file?

Regarding "variable offset GEP from a global": the simple version of this with just the GEP live over the statepoint doesn't crash without the patch because of rematerialization. I can (a) add a more complex example which isn't handled by rematerialization or (b) check that it doesn't get rematerialized. I'm not sure which would be more useful.

Regarding "variable offset from a null pointer down a dead path": first, what exactly do you mean by "dead"? Statically dead paths are removed by RS4GC. Can you give an simple example of a dynamically, but not statically, dead path? I hope I use the correct terminology here. Also, a constant null pointer as a base will fire an assert assert(!isa<ConstantPointerNull>(base) ... in findBasePointers().

[mjacob]

Improve comment.

[mjacob]

Improve comment.

[mjacob]

Add another test.

[mjacob]

As this revision was already accepted, I committed it. Another test (Philip proposed a test "variable offset from a null pointer down a dead path") could be added in a follow-up commit after my open questions about this particular test case are answered.

[reames]

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

17

You can put them in the same file or a different one as convient. No strong preference.

Sounds like we might want to consider adding a diagnostic flag to disable rematerialization. Doing so would make it easier to write the simple test and is probably worthwhile. Adding both the simple and complicated tests might be worth it as well.

By "dead", I meant "dynamically dead, but not statically dead". You can end up with all kinds of garbage down such a path because the compiler may have proven conflicting facts, but not yet realized the block is dead. Don't worry about this case specifically, I was mostly just throwing out ideas. I do want at least a bit more test coverage here, but I'm not picky about the form it takes.

p.s. The constant base assert has been removed.

[mjacob]

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

17

OK, the commit includes another test case. I think testing that it won't rematerialize makes sense as well. So now we have one test with a non-materializable derived pointer and one with a materializable derived pointer.

I meant another assert which is still present. The comment says it's there because the verifier relies on it.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

makeStatepointExplicit(DominatorTree &DT, const CallSite &CS,
   const auto &LiveSet = Result.LiveSet;
   const auto &PointerToBase = Result.PointerToBase;
 
   // Convert to vector for efficient cross referencing.
   SmallVector<Value *, 64> BaseVec, LiveVec;
   LiveVec.reserve(LiveSet.size());
   BaseVec.reserve(LiveSet.size());
   for (Value *L : LiveSet) {
     LiveVec.push_back(L);
     assert(PointerToBase.count(L));
     Value *Base = PointerToBase.find(L)->second;
     BaseVec.push_back(Base);
   }
   assert(LiveVec.size() == BaseVec.size());
 
   // To make the output IR slightly more stable (for use in diffs), ensure a
   // fixed order of the values in the safepoint (by sorting the value name).
if (PrintBasePointers) {
     for (auto &Info : Records) {
       errs() << "Base Pairs: (w/Relocation)\n";
       for (auto Pair : Info.PointerToBase)
         errs() << " derived %" << Pair.first->getName() << " base %"
                << Pair.second->getName() << "\n";
     }
   }
 
+  // It is possible that non-constant live variables have a constant base.  For
+  // example, a GEP with a variable offset from a global.  In this case we can
+  // remove it from the liveset.  We already don't add constants to the liveset
+  // because we assume they won't move at runtime and the GC doesn't need to be
+  // informed about them.  The same reasoning applies if the base is constant.
+  // Note that the relocation placement code relies on this filtering for
+  // correctness as it expects the base to be in the liveset, which isn't true
+  // if the base is constant.
+  for (auto &Info : Records)
+    for (auto &BasePair : Info.PointerToBase)
+      if (isa<Constant>(BasePair.second))
+        Info.LiveSet.erase(BasePair.first);
+
   for (CallInst *CI : Holders)
     CI->eraseFromParent();
 
   Holders.clear();
 
   // Do a limited scalarization of any live at safepoint vector values which
   // contain pointers.  This enables this pass to run after vectorization at
   // the cost of some possible performance loss.  TODO: it would be nice to

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
+
+@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
+  %safepoint_token = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @extern, i32 0, i32 0, i32 0, i32 0)
+; CHECK-NOT: relocate
+; CHECK: %load = load i8, i8 addrspace(1)* %select
+  %load = load i8, i8 addrspace(1)* %select
+  ret i8 %load
+}
+
+declare void @extern() gc "statepoint-example"
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)

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
+
+@global = external addrspace(1) global i8
+
+define i8 @test(i64 %offset) gc "statepoint-example" {
+  %derived = getelementptr i8, i8 addrspace(1)* @global, i64 %offset
+  %safepoint_token = call i32 (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @extern, i32 0, i32 0, i32 0, i32 0)
+; 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 i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)