[RS4GC] New pass to remove gc.relocates added by RS4GC

[anna]

Summary

Utility pass to remove gc.relocates created by rewrite statepoints for GC.
With respect to safepoint verification, the IR generated would be incorrect, and cannot run on VMs
as such. However, the IR verifier would verify the IR to be correct.

This would be a single transformation on the final optimized IR. LLVM used with most VMs would have the RewriteStatepointsForGC (RS4GC) enabled in the opt pipeline, or some form of garbage collection support. See: http://llvm.org/docs/Statepoints.html

The benefit of this pass is for easy analysis of the IR, when the final optimized IR is 'polluted' by too
many gc.relocates of the original pointers. For example, in manual performance analysis of the optimized IR, we can walk back through the use-def chain without having to deal with all the gc.relocates.

test run: All RS4GC tests with -verify option. Local downstream tests on large
IR files. This also works when the pointer being gc.relocated is another
gc.relocate.

TODO: There are 2 specific parts that need some more thought. Right now most
GC.relocates are removed.

[anna]

lib/Transforms/Utils/RemoveGCRelocates.cpp

78–79

These are cases where lets say original pointer is i32*, while the gc.relocate are of type i8*.

All uses of the gc.relocates are phi or other non-store operations, which use the i8* relocated pointer. In such a case, there is no bitcast from i8* to i32* (since there are no uses of the i32* version of relocated pointer). I think this can be transformed to:

original_ptr.casted = bitcast i32* original_ptr to i8*
replace all uses of relocated pointer with original_ptr.casted

[anna]

lib/Transforms/Utils/RemoveGCRelocates.cpp

61–62

The first line (A gc.relocate is bound to a single statepoint token) is not relevant here.

Comment should be:
The order of removing the gc.relocate does not matter, since we first make sure that *all* uses of the relocate are replaced with original pointer. After completion of this transformation for all gc.relocates, we would have the original pointer in all relocates (including nested gc.relocate).

[sanjoy]

I have some minor comments inline, but overall I'm not sure if a pass like this (solely useful for generating "debugging output") is okay to go upstream.

Do you mind starting a thread on llvm-dev discussing if this sort of thing is okay with the community?

lib/Transforms/Utils/RemoveGCRelocates.cpp

2

Fix the comment here.

42

Not sure if you need private: here.

70

Didn't you just check that GCRel->getOperand(0) is a statepoint? I think this can be a cast<>

73

Why not just use the GCRelocateInst::getBasePtr instruction?

[anna]

In D25096#557526, @sanjoy wrote:

I have some minor comments inline, but overall I'm not sure if a pass like this (solely useful for generating "debugging output") is okay to go upstream.

Do you mind starting a thread on llvm-dev discussing if this sort of thing is okay with the community?

Actually, thats a good point. Especially since RS4GC is not in the pipeline of optimization passes (in PassManagerBuilder.cpp). So, the only usage would be for downstream folks incorporating RS4GC in their optimization pipeline.

lib/Transforms/Utils/RemoveGCRelocates.cpp

70

yes, I forgot to change that to cast. I had the order of checks other way around initially :)

73

Ah yes. Although, I'll be using the getDerivedPtr.

[anna]

addressed above comments.

[mehdi_amini]

lib/Transforms/Utils/RemoveGCRelocates.cpp

100

/Bike-shed
What about "strip-gc-relocates" (we already use "strip" for debug info for example and this seems comparable).
/Bike-shed off

[reames]

(stale comment I never hit submit on)

lib/Transforms/Utils/RemoveGCRelocates.cpp

100

I like the strip-gc-relocates name as well.

[anna]

[StripGCRelocates] Added test cases. Changed pass name to strip-gc-relocates
Please take a look at test5, this is somewhat of a grey area. Do we want to remove the relocates
and add a bit cast? This is the second TODO in the list:
gc.relocate of different type than the original pointer, but all uses are of the same type
as gc.relocate.

[anna]

Forgot to mention the motivation in continuing the review upstream itself: looks like llvm-dev community is generally in favour, or rather, no objections to adding debugging/diagnostic passes.

http://lists.llvm.org/pipermail/llvm-dev/2016-October/105773.html

[sanjoy]

lib/Transforms/Utils/RemoveGCRelocates.cpp

36

Not sure if this is correct, since you're changing IR. I'd suggest starting with "clobbers all" for now.

41

Why not have this just be a local that lives on stack in runOnFunction?

49

I didn't know we could have empty non-declarations.

53

I don't think you need this double staged casting -- you should be able to do:

if (auto *GCR = dyn_cast<GCRelocateInst>(&I))
  GCRelocates.push_back(GCR);

57

Empty line?

70

I wouldn't bother with this. I'd just insert a bitcast of the original to i8 addrspace(1)*, RAUW with that. We can always run -instcombine later to clean up the IR quickly.

At the very least, I'd do this ^ in place of the continue down below:

if (GCRel->hasOneUse() && isa<BitCastInst>(GCRel->user_back()))
  ToBeReplaced = GCRel->user_back();
else
  // Create new bitcast and RAUW with that.

[anna]

Addressed comments above. Renamed pass name, and handled bit casts.
Tests run with -strip-gc-relocates followed by an instcombine pass to clean up
unnecessary bitcasts.

[anna]

lib/Transforms/Utils/RemoveGCRelocates.cpp

49

Actually, I think there cannot be empty non-declarations after all optimizations are done.
Either way the pass will not do anything for empty functions. Removed that check.

70

Yes, the second idea was what I was thinking of originally, and mentioned in comment below.

I like your first idea better, the code is cleaner, and instcombine would get rid of unnecessary bitcasts (if any).

[sanjoy]

lgtm with comments

include/llvm/Transforms/Scalar.h

477

End with period.

Also I'd say "useful for manual inspection". Analysis can also mean "llvm analysis".

lib/Transforms/Utils/StripGCRelocates.cpp

11 ↗

(On Diff #75439)

s/would be incorrect,/is incorrect,/ sounds better

44 ↗

(On Diff #75439)

I'd remove the blank line.

57 ↗

(On Diff #75439)

Same here: I'd drop the blank line.

60 ↗

(On Diff #75439)

Hm -- why is it okay for _instcombine_ to remove the relocates hanging off of landingpads? In @test3, I suspect _instcombine_ is removing these because they aren't used, if they had real uses the landingpad relocates would still be around.

Also, if you avoid adding these landingpad gc relocates to the GCRelocates vector then instead of tracking Changed, you could just return !GCRelocates.empty();.

[anna]

lib/Transforms/Utils/StripGCRelocates.cpp

60 ↗

(On Diff #75439)

That's right. I've updated the comment as well, and avoid tracking Changed.

include/llvm/InitializePasses.h

 void initializeRegBankSelectPass(PassRegistry &);
 void initializeRegToMemPass(PassRegistry&);
 void initializeRegionInfoPassPass(PassRegistry&);
 void initializeRegionOnlyPrinterPass(PassRegistry&);
 void initializeRegionOnlyViewerPass(PassRegistry&);
 void initializeRegionPrinterPass(PassRegistry&);
 void initializeRegionViewerPass(PassRegistry&);
 void initializeRegisterCoalescerPass(PassRegistry&);
+void initializeRemoveGCRelocatesPass(PassRegistry&);
 void initializeRenameIndependentSubregsPass(PassRegistry&);
 void initializeResetMachineFunctionPass(PassRegistry &);
 void initializeReversePostOrderFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeRewriteStatepointsForGCPass(PassRegistry&);
 void initializeRewriteSymbolsLegacyPassPass(PassRegistry&);
 void initializeSCCPLegacyPassPass(PassRegistry &);
 void initializeSCEVAAWrapperPassPass(PassRegistry&);
 void initializeSLPVectorizerPass(PassRegistry&);

include/llvm/Transforms/Scalar.h

 //
 // RewriteStatepointsForGC - Rewrite any gc.statepoints which do not yet have
 // explicit relocations to include explicit relocations.
 //
 ModulePass *createRewriteStatepointsForGCPass();
 
 //===----------------------------------------------------------------------===//
 //
+// RemoveGCRelocates - Remove GC relocates that have been inserted by
+// RewriteStatepointsForGC. The resulting IR is incorrect, but this is useful
+// for analysis
+FunctionPass *createRemoveGCRelocatesPass();
+
+//===----------------------------------------------------------------------===//
+//
 // Float2Int - Demote floats to ints where possible.
 //
 FunctionPass *createFloat2IntPass();
 
 //===----------------------------------------------------------------------===//
 //
 // NaryReassociate - Simplify n-ary operations by reassociation.
 //

lib/Transforms/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   LowerInvoke.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
   MemorySSA.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   NameAnonGlobals.cpp
   PromoteMemoryToRegister.cpp
+  RemoveGCRelocates.cpp
   SSAUpdater.cpp
   SanitizerStats.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp
   SimplifyLibCalls.cpp
   SplitModule.cpp
   SymbolRewriter.cpp

lib/Transforms/Utils/RemoveGCRelocates.cpp

+//===- RemoveGCRelocates.cpp - Remove gc.relocates inserted by RewriteStatePoints===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This is a little utility pass that removes the gc.relocates inserted by
+// RewriteStatepointsForGC. Note that the generated IR would be incorrect,
+// but this is useful as a single pass in itself, for analysis of IR, without
+// the GC.relocates. The statepoint and gc.result instrinsics would still be
+// present.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Statepoint.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/Scalar.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+namespace {
+struct RemoveGCRelocates : public FunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+  RemoveGCRelocates() : FunctionPass(ID) {
+    initializeRemoveGCRelocatesPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &Info) const override {
+    Info.setPreservesAll();
+  }
+
+  bool runOnFunction(Function &F) override;
+
+  SmallVector<GCRelocateInst *, 20> GCRelocates;
+};
+char RemoveGCRelocates::ID = 0;
+}
+
+bool RemoveGCRelocates::runOnFunction(Function &F) {
+
+  // Nothing to do for declarations.
+  if (F.isDeclaration() || F.empty())
+    return false;
+  GCRelocates.clear();
+  for (Instruction &I : instructions(F)) {
+    ImmutableCallSite GCRel = ImmutableCallSite(&I);
+    if (!isGCRelocate(GCRel))
+      continue;
+    GCRelocates.push_back(cast<GCRelocateInst>(&I));
+
+  }
+  bool Changed = false;
+  // All gc.relocates are bound to a single statepoint token. The order of
+  // visiting gc.relocates for deletion does not matter.
+  for (GCRelocateInst *GCRel : GCRelocates) {
+
+    // TODO: Handle gc.relocates in landing pads (these are not bound to the
+    // statepoint token).
+    if (!isStatepoint(GCRel->getOperand(0)))
+      continue;
+    Value *OrigPtr = GCRel->getDerivedPtr();
+
+    Instruction *ToBeReplaced = GCRel;
+    // All gc_relocates are i8 addrspace(1)* typed, and may be bitcasted to
+    // the correct type of the original pointer (if they are not the same).
+    // TODO: Handle gc.relocates that are of different type from original
+    // pointer, but all uses are the gc.relocate of i8 addrspace(1)* type.
+    if (GCRel->getType() != OrigPtr->getType()) {
+      if (GCRel->hasOneUse() && isa<BitCastInst>(GCRel->user_back()))
+        ToBeReplaced = GCRel->user_back();
+      else
+        continue;
+    }
+    assert(ToBeReplaced->getType() == OrigPtr->getType() &&
+           "Should have same types!");
+    // Replace all uses and delete the relocate (and bitcast'ed version, if
+    // necessary).
+    ToBeReplaced->replaceAllUsesWith(OrigPtr);
+    if (GCRel != ToBeReplaced) {
+      ToBeReplaced->eraseFromParent();
+      // Only the bitcast of the gc.relocate was deleted above, we also need
+      // to delete the gc.relocate itself.
+      GCRel->eraseFromParent();
+    } else
+      ToBeReplaced->eraseFromParent();
+    Changed = true;
+  }
+  return Changed;
+}
+
+INITIALIZE_PASS(RemoveGCRelocates, "strip-gc-relocates",
+                "Strip gc.relocates inserted through RewriteStatepointsForGC",
+                true, false)
+FunctionPass *llvm::createRemoveGCRelocatesPass() {
+  return new RemoveGCRelocates();
+}

lib/Transforms/Utils/Utils.cpp

void llvm::initializeTransformUtils(PassRegistry &Registry) {
   initializeLowerSwitchPass(Registry);
   initializeNameAnonGlobalLegacyPassPass(Registry);
   initializePromoteLegacyPassPass(Registry);
   initializeUnifyFunctionExitNodesPass(Registry);
   initializeInstSimplifierPass(Registry);
   initializeMetaRenamerPass(Registry);
   initializeMemorySSAWrapperPassPass(Registry);
   initializeMemorySSAPrinterLegacyPassPass(Registry);
+  initializeRemoveGCRelocatesPass(Registry);
 }
 
 /// LLVMInitializeTransformUtils - C binding for initializeTransformUtilsPasses.
 void LLVMInitializeTransformUtils(LLVMPassRegistryRef R) {
   initializeTransformUtils(*unwrap(R));
 }

test/Transforms/Util/strip-gc-relocates.ll

+; RUN: opt -S -strip-gc-relocates < %s | FileCheck %s
+; test utility/debugging pass which removes gc.relocates, inserted by -rewrite-statepoints-for-gc
+declare void @use_obj32(i32 addrspace(1)*) "gc-leaf-function"
+
+declare void @g()
+declare token @llvm.experimental.gc.statepoint.p0f_isVoidf(i64, i32, void ()*, i32, i32, ...)
+declare i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token, i32, i32) #0
+declare void @do_safepoint()
+
+declare i32 addrspace(1)* @new_instance() #1
+
+
+; Simple case: remove gc.relocate
+define i32 addrspace(1)* @test1(i32 addrspace(1)* %arg) gc "statepoint-example" {
+entry:
+; CHECK-LABEL: test1
+; CHECK: gc.statepoint
+; CHECK-NOT: gc.relocate
+; CHECK: ret i32 addrspace(1)* %arg
+  %statepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @g, i32 0, i32 0, i32 0, i32 1, i32 100, i32 addrspace(1)* %arg)
+  %arg.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 8, i32 8) ; (%arg, %arg)
+  %arg.relocated.casted = bitcast i8 addrspace(1)* %arg.relocated to i32 addrspace(1)*
+  ret i32 addrspace(1)* %arg.relocated.casted
+}
+
+; Remove gc.relocates in presence of nested relocates.
+define void @test2(i32 addrspace(1)* %base) gc "statepoint-example" {
+entry:
+; CHECK-LABEL: test2
+; CHECK: statepoint
+; CHECK-NOT: gc.relocate
+; CHECK: call void @use_obj32(i32 addrspace(1)* %ptr.gep1)
+; CHECK: call void @use_obj32(i32 addrspace(1)* %ptr.gep1)
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %base, i32 15
+  %ptr.gep1 = getelementptr i32, i32 addrspace(1)* %ptr.gep, i32 15
+  %statepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %ptr.gep1, i32 addrspace(1)* %base)
+  %ptr.gep1.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 8, i32 7) ; (%base, %ptr.gep1)
+  %ptr.gep1.relocated.casted = bitcast i8 addrspace(1)* %ptr.gep1.relocated to i32 addrspace(1)*
+  %base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 8, i32 8) ; (%base, %base)
+  %base.relocated.casted = bitcast i8 addrspace(1)* %base.relocated to i32 addrspace(1)*
+  call void @use_obj32(i32 addrspace(1)* %ptr.gep1.relocated.casted)
+  %statepoint_token1 = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %ptr.gep1.relocated.casted, i32 addrspace(1)* %base.relocated.casted)
+  %ptr.gep1.relocated2 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token1, i32 8, i32 7) ; (%base.relocated.casted, %ptr.gep1.relocated.casted)
+  %ptr.gep1.relocated2.casted = bitcast i8 addrspace(1)* %ptr.gep1.relocated2 to i32 addrspace(1)*
+  %base.relocated3 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token1, i32 8, i32 8) ; (%base.relocated.casted, %base.relocated.casted)
+  %base.relocated3.casted = bitcast i8 addrspace(1)* %base.relocated3 to i32 addrspace(1)*
+  call void @use_obj32(i32 addrspace(1)* %ptr.gep1.relocated2.casted)
+  ret void
+}
+
+; TODO: remove gc.relocates from landing pad
+define i32 addrspace(1)* @test3(i32 addrspace(1)* %arg) gc "statepoint-example" personality i32 8 {
+; CHECK-LABEL: test3(
+; CHECK: gc.statepoint
+; CHECK-LABEL: normal_dest:
+; CHECK-NOT: gc.relocate
+; CHECK: ret i32 addrspace(1)* %arg
+; CHECK-LABEL: unwind_dest:
+; CHECK: gc.relocate
+entry:
+  %statepoint_token = invoke token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @g, i32 0, i32 0, i32 0, i32 1, i32 100, i32 addrspace(1)* %arg)
+          to label %normal_dest unwind label %unwind_dest
+
+normal_dest:                                      ; preds = %entry
+  %arg.relocated1 = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 8, i32 8) ; (%arg, %arg)
+  %arg.relocated1.casted = bitcast i8 addrspace(1)* %arg.relocated1 to i32 addrspace(1)*
+  ret i32 addrspace(1)* %arg.relocated1.casted
+
+unwind_dest:                                      ; preds = %entry
+  %lpad = landingpad token
+          cleanup
+  %arg.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %lpad, i32 8, i32 8) ; (%arg, %arg)
+  %arg.relocated.casted = bitcast i8 addrspace(1)* %arg.relocated to i32 addrspace(1)*
+  resume token undef
+}
+
+; in presence of phi
+define void @test4(i1 %cond) gc "statepoint-example" {
+; CHECK-LABEL: test4
+entry:
+  %base1 = call i32 addrspace(1)* @new_instance()
+  %base2 = call i32 addrspace(1)* @new_instance()
+  br i1 %cond, label %here, label %there
+
+here:                                             ; preds = %entry
+  br label %merge
+
+there:                                            ; preds = %entry
+  br label %merge
+
+merge:                                            ; preds = %there, %here
+; CHECK-LABEL: merge:
+; CHECK-NOT: gc.relocate
+; CHECK: %ptr.gep.remat = getelementptr i32, i32 addrspace(1)* %basephi.base, i32 15
+  %basephi.base = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ], !is_base_value !0
+  %basephi = phi i32 addrspace(1)* [ %base1, %here ], [ %base2, %there ]
+  %ptr.gep = getelementptr i32, i32 addrspace(1)* %basephi, i32 15
+  %statepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @do_safepoint, i32 0, i32 0, i32 0, i32 0, i32 addrspace(1)* %basephi.base)
+  %basephi.base.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 7, i32 7) ; (%basephi.base, %basephi.base)
+  %basephi.base.relocated.casted = bitcast i8 addrspace(1)* %basephi.base.relocated to i32 addrspace(1)*
+  %ptr.gep.remat = getelementptr i32, i32 addrspace(1)* %basephi.base.relocated.casted, i32 15
+  call void @use_obj32(i32 addrspace(1)* %ptr.gep.remat)
+  ret void
+}
+
+; The gc.relocate type is different from %arg, but removing the gc.relocate,
+; will need a bitcast to be added from i32 addrspace(1)* to i8 addrspace(1)*
+define i8 addrspace(1)* @test5(i32 addrspace(1)* %arg) gc "statepoint-example" {
+entry:
+; CHECK-LABEL: test5
+; CHECK: gc.statepoint
+; CHECK: gc.relocate
+; CHECK: ret i8 addrspace(1)* %arg.relocated
+  %statepoint_token = call token (i64, i32, void ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void ()* @g, i32 0, i32 0, i32 0, i32 1, i32 100, i32 addrspace(1)* %arg)
+  %arg.relocated = call coldcc i8 addrspace(1)* @llvm.experimental.gc.relocate.p1i8(token %statepoint_token, i32 8, i32 8) ; (%arg, %arg)
+  ret i8 addrspace(1)* %arg.relocated
+}
+
+attributes #0 = { nounwind readonly }
+attributes #1 = { nounwind "gc-leaf-function" }
+!0 = !{}