[RewriteStatepointsForGC] Preprocess the IR to remove unreachable blocks and single entry phis

[reames]

Summary

Two related small changes:

• Various dominance based queries about liveness can get confused if we're talking about unreachable blocks. To avoid reasoning about such cases, just remove them before rewriting statepoints.
• Remove single entry phis (likely left behind by LCSSA) to reduce the number of live values.

Both of these are motivated by http://reviews.llvm.org/D8674, but are not actually dependent on that.

[swaroop.sridhar]

Change looks good to me, thanks.

[mjacob]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

1912

This variable should just record whether there is an unreachable statepoint.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

bool RewriteStatepointsForGC::runOnFunction(Function &F) {
   if (F.isDeclaration() || F.empty())
     return false;
 
   // Policy choice says not to rewrite - the most common reason is that we're
   // compiling code without a GCStrategy.
   if (!shouldRewriteStatepointsIn(F))
     return false;
 
-  // Gather all the statepoints which need rewritten.
+  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  
+  // Gather all the statepoints which need rewritten.  Be careful to only
+  // consider those in reachable code since we need to ask dominance queries
+  // when rewriting.  We'll delete the unreachable ones in a moment.
   SmallVector<CallSite, 64> ParsePointNeeded;
+  SmallVector<CallSite, 16> UnreachableStatepoints;
   for (Instruction &I : inst_range(F)) {
     // TODO: only the ones with the flag set!
-    if (isStatepoint(I))
+    if (isStatepoint(I)) {
+      if (DT.isReachableFromEntry(I.getParent()))
         ParsePointNeeded.push_back(CallSite(&I));
+      else
+        UnreachableStatepoints.push_back(CallSite(&I));
     }
+  }
+
+  bool MadeChange = false;
+  
+  // Delete any unreachable statepoints so that we don't have unrewritten
+  // statepoints surviving this pass.  This makes testing easier and the
+  // resulting IR less confusing to human readers.  Rather than be fancy, we
+  // just reuse a utility function which removes the unreachable blocks.
+  if (!UnreachableStatepoints.empty())
+    MadeChange |= removeUnreachableBlocks(F);
 
   // Return early if no work to do.
   if (ParsePointNeeded.empty())
-    return false;
+    return MadeChange;
 
-  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  return insertParsePoints(F, DT, this, ParsePointNeeded);
+  // As a prepass, go ahead and aggressively destroy single entry phi nodes.
+  // These are created by LCSSA.  They have the effect of increasing the size
+  // of liveness sets for no good reason.  It may be harder to do this post
+  // insertion since relocations and base phis can confuse things.
+  for (BasicBlock &BB : F)
+    if (BB.getUniquePredecessor()) {
+      MadeChange = true;
+      FoldSingleEntryPHINodes(&BB);
+    }
+
+  MadeChange |= insertParsePoints(F, DT, this, ParsePointNeeded);
+  return MadeChange;
 }
 
 
 // liveness computation via standard dataflow
 // -------------------------------------------------------------------
 
 // TODO: Consider using bitvectors for liveness, the set of potentially
 // interesting values should be small and easy to pre-compute.

test/Transforms/RewriteStatepointsForGC/preprocess.ll

+; RUN: opt -rewrite-statepoints-for-gc -S < %s | FileCheck %s
+
+declare void @consume(...)
+
+; Test to make sure we destroy LCSSA's single entry phi nodes before
+; running liveness
+define void @test6(i64 addrspace(1)* %obj) gc "statepoint-example" {
+; CHECK-LABEL: @test6
+entry:
+  br label %next
+
+next:
+; CHECK-LABEL: next:
+; CHECK-NEXT: gc.statepoint
+; CHECK-NEXT: gc.relocate
+; CHECK-NEXT: @consume(i64 addrspace(1)* %obj.relocated)
+; CHECK-NEXT: @consume(i64 addrspace(1)* %obj.relocated)
+  %obj2 = phi i64 addrspace(1)* [ %obj, %entry ]
+  call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  call void (...)* @consume(i64 addrspace(1)* %obj2)
+  call void (...)* @consume(i64 addrspace(1)* %obj)
+  ret void
+}
+
+declare void @some_call(i64 addrspace(1)*)
+
+; Need to delete unreachable gc.statepoint call
+define void @test7() gc "statepoint-example" {
+; CHECK-LABEL: test7
+; CHECK-NOT: gc.statepoint
+  ret void
+
+unreached:
+  %obj = phi i64 addrspace(1)* [null, %unreached]
+  call i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 0, i32 0, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+  call void (...)* @consume(i64 addrspace(1)* %obj)
+  br label %unreached
+}
+
+; Need to delete unreachable gc.statepoint invoke - tested seperately given
+; a correct implementation could only remove the instructions, not the block
+define void @test8() gc "statepoint-example" {
+; CHECK-LABEL: test8
+; CHECK-NOT: gc.statepoint
+  ret void
+
+unreached:
+  invoke i32 (void ()*, i32, i32, ...)* @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()* @foo, i32 1, i32 0, i64 addrspace(1)* null, i32 5, i32 0, i32 -1, i32 0, i32 0, i32 0)
+          to label %normal_return unwind label %exceptional_return
+
+normal_return:                                    ; preds = %entry
+  ret void
+
+exceptional_return:                               ; preds = %entry
+  %landing_pad4 = landingpad { i8*, i32 } personality i32 ()* undef
+          cleanup
+  ret void
+}
+
+declare void @foo()
+; Bound the last check-not
+; CHECK-LABEL: @foo
+
+declare i32 @llvm.experimental.gc.statepoint.p0f_isVoidf(void ()*, i32, i32, ...)
+