[RewriteStatepoints] Fix stale parse points

[yrouban]

Summary

RewriteStatepointsForGC collects parse points for further processing. During the collection if a callsite is found in an unreachable block (DominatorTree::isReachableFromEntry()) then all unreachable blocks are removed by removeUnreachableBlocks(). Some of the removed blocks could have been reachable according to DominatorTree::isReachableFromEntry(). In this case the collected parse points became stale and resulted in a crash when accessed.

The fix does the following: if a parse point is detected in an unreachable block then the removeUnreachableBlocks() method is called, the DominatorTree is updated and all parse points are collected again.

The proposed test crashes with the old version and passes with the new.

[anna]

Good find Yevgeny!
So, removeUnreachableBlocks is much more aggressive than DT.isReachableFromEntry. Did you check if there's some function that just keeps exactly what isReachableFromEntry computes?

Other comments inline.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2534 ↗

(On Diff #136472)

I'm not a fan of double collection of statepoints :) How about making this clearer:

1. Unconditionally run canonicalizing step: removeUnreachableBlocks.
2. Compute statepoints using line 2561 - 2565. At this point, just an assert that DT.isReachableFromEntry is enough.

Also, pls add an explicit comment stating that removeUnreachableBlocks is stronger than isReachableFromEntry.

test/Transforms/RewriteStatepointsForGC/unreachable-regression.ll

7 ↗

(On Diff #136472)

This was very confusing "why would removeUnreachableBlocks remove reachable blocks :)".

Once the unconditional canonicalization step is done, pls modify this comment and state that "Parse points are calculated only for reachable blocks".

[yrouban]

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2534 ↗

(On Diff #136472)

Ok. Make sense.
I'm not sure if removeUnreachanbleBlocks() is easy. That is why I propose its lazy run. I will make it simple as you suggested.

[yrouban]

made the removeUnreachableBlocks() call unconditinal

[anna]

LGTM w/ comments.

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

2535 ↗

(On Diff #136699)

I don't think this last line is needed here. removeUnreachableBlocks seems to be rather fancy compared to isReachableFromEntry ;)

2538 ↗

(On Diff #136699)

Nit: extra semicolon.

2534 ↗

(On Diff #136472)

Note that apart from canonicalizing the IR, we also got rid of the isReachableFromEntry check on every parse point.

[yrouban]

done the minor corrections as Anna suggested.
Could anyone with appropriate rights merge the patch?

[inouehrs]

test/Transforms/RewriteStatepointsForGC/unreachable-regression.ll

6 ↗

(On Diff #136948)

Minor typo: unreachanble -> unreachable

[yrouban]

hold on. I see unexpected test failure.

[yrouban]

• fixed the typos
• fixed two tests to get rid of unreachability of tested statepoints

[anna]

In D43929#1026825, @yrouban wrote:

done the minor corrections as Anna suggested.
Could anyone with appropriate rights merge the patch?

I'll land this today.

[anna]

Yevgeny, Just for record - Dan will be trying to drop it. There's something wrong with my local repo and rebuilding it still doesn't allow me to git svn dcommit.

This is the patch details:

commit 854c9fce69c2593c1a74de4ff94914574f9e2356 (HEAD -> master)
Author: Anna Thomas <[e-mail]>
Date:   Mon Mar 5 11:58:18 2018 -0500

    [RewriteStatepoints] Fix stale parse points
    
    RewriteStatepointsForGC collects parse points for further processing.
    During the collection if a callsite is found in an unreachable block
    (DominatorTree::isReachableFromEntry()) then all unreachable blocks are
    removed by removeUnreachableBlocks(). Some of the removed blocks could
    have been reachable according to DominatorTree::isReachableFromEntry().
    In this case the collected parse points became stale and resulted in a
    crash when accessed.
    
    The fix is to unconditionally canonicalize the IR to
    removeUnreachableBlocks and then collect the parse points.
    
    The added test crashes with the old version and passes with this patch.
    
    Patch by Yevgeny Rouban!
    
    Reviewed by: Anna
    
    Differential Revision: https://reviews.llvm.org/D43929

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

bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT,
   assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");
 
   auto NeedsRewrite = [&TLI](Instruction &I) {
     if (ImmutableCallSite CS = ImmutableCallSite(&I))
       return !callsGCLeafFunction(CS, TLI) && !isStatepoint(CS);
     return 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.
+  DeferredDominance DD(DT);
+  bool MadeChange = removeUnreachableBlocks(F, nullptr, &DD);
+  DD.flush();
+
   // 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;
-  bool HasUnreachableStatepoint = false;
   for (Instruction &I : instructions(F)) {
     // TODO: only the ones with the flag set!
     if (NeedsRewrite(I)) {
-      if (DT.isReachableFromEntry(I.getParent()))
-        ParsePointNeeded.push_back(CallSite(&I));
-      else
-        HasUnreachableStatepoint = true;
+      // NOTE removeUnreachableBlocks() is stronger than
+      // DominatorTree::isReachableFromEntry(). In other words
+      // removeUnreachableBlocks can remove some blocks for which
+      // isReachableFromEntry() returns true.
+      assert(DT.isReachableFromEntry(I.getParent()) &&
+            "no unreachable blocks expected");
     }
   }
 
-  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 (HasUnreachableStatepoint)
-    MadeChange |= removeUnreachableBlocks(F);
-
   // Return early if no work to do.
   if (ParsePointNeeded.empty())
     return MadeChange;
 
   // 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.

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

 ; CHECK: phi i8 addrspace(1)*
 ; CHECK-DAG: [ %arg.relocated, %if_branch ]
 ; CHECK-DAG: [ %arg.relocated2, %else_branch ]
 ; CHECK-NOT: phi
   call void @some_call(i8 addrspace(1)* %arg)
   ret void
 }
 
+declare void @goo(i64)
+
+declare i32 @moo(i64 addrspace(1)*)
+
 ; Make sure a use in a statepoint gets properly relocated at a previous one.  
 ; This is basically just making sure that statepoints aren't accidentally 
 ; treated specially.
 define void @test3(i64 addrspace(1)* %obj) gc "statepoint-example" {
 ; CHECK-LABEL: @test3
 ; CHECK: gc.statepoint
 ; CHECK-NEXT: gc.relocate
 ; CHECK-NEXT: bitcast
 ; CHECK-NEXT: gc.statepoint
 entry:
-  call void undef(i64 undef) [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
-  %0 = call i32 undef(i64 addrspace(1)* %obj) [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  call void @goo(i64 undef) [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
+  %0 = call i32 @moo(i64 addrspace(1)* %obj) [ "deopt"(i32 0, i32 -1, i32 0, i32 0, i32 0) ]
   ret void
 }
 
+declare i8 addrspace(1)* @boo()
+
 ; Check specifically for the case where the result of a statepoint needs to 
 ; be relocated itself
 define void @test4() gc "statepoint-example" {
 ; CHECK-LABEL: @test4
 ; CHECK: gc.statepoint
 ; CHECK: gc.result
 ; CHECK: gc.statepoint
 ; CHECK: [[RELOCATED:%[^ ]+]] = call {{.*}}gc.relocate
 ; CHECK: @use(i8 addrspace(1)* [[RELOCATED]])
-  %1 = call i8 addrspace(1)* undef() [ "deopt"() ]
-  %2 = call i8 addrspace(1)* undef() [ "deopt"() ]
+  %1 = call i8 addrspace(1)* @boo() [ "deopt"() ]
+  %2 = call i8 addrspace(1)* @boo() [ "deopt"() ]
   call void (...) @use(i8 addrspace(1)* %1)
-  unreachable
+  ret void
 }
 
 ; Test updating a phi where not all inputs are live to begin with
 define void @test5(i8 addrspace(1)* %arg) gc "statepoint-example" {
 ; CHECK-LABEL: test5
 entry:
-  %0 = call i8 addrspace(1)* undef() [ "deopt"() ]
+  %0 = call i8 addrspace(1)* @boo() [ "deopt"() ]
   switch i32 undef, label %kill [
     i32 10, label %merge
     i32 13, label %merge
   ]
 
 kill:                                             ; preds = %entry
   br label %merge
 
 merge:                                            ; preds = %kill, %entry, %entry
 ; CHECK: merge:
 ; CHECK: %test = phi i8 addrspace(1)
 ; CHECK-DAG: [ null, %kill ]
 ; CHECK-DAG: [ %arg.relocated, %entry ]
 ; CHECK-DAG: [ %arg.relocated, %entry ]
   %test = phi i8 addrspace(1)* [ null, %kill ], [ %arg, %entry ], [ %arg, %entry ]
   call void (...) @use(i8 addrspace(1)* %test)
-  unreachable
+  ret void
 }
 
 ; Check to make sure we handle values live over an entry statepoint
 define void @test6(i8 addrspace(1)* %arg1, i8 addrspace(1)* %arg2, i8 addrspace(1)* %arg3) gc "statepoint-example" {
 ; CHECK-LABEL: @test6
 entry:
   br i1 undef, label %gc.safepoint_poll.exit2, label %do_safepoint
 

llvm/trunk/test/Transforms/RewriteStatepointsForGC/unreachable-regression.ll

+; RUN: opt -S -rewrite-statepoints-for-gc < %s | FileCheck %s
+; RUN: opt -S -passes=rewrite-statepoints-for-gc < %s | FileCheck %s
+;
+; Regression test:
+;   After the rewritable callsite collection if any callsite was found
+;   in a block that was reported unreachable by DominanceTree then
+;   removeUnreachableBlocks() was called. But it is stronger than
+;   DominatorTree::isReachableFromEntry(), i.e. removeUnreachableBlocks
+;   can remove some blocks for which isReachableFromEntry() returns true.
+;   This resulted in stale pointers to the collected but removed
+;   callsites. Such stale pointers caused crash when accessed.
+declare void @f(i8 addrspace(1)* %obj)
+
+define void @test(i8 addrspace(1)* %arg) gc "statepoint-example" {
+; CHECK-LABEL: test(
+; CHECK-NEXT: @f
+ call void @f(i8 addrspace(1)* %arg) #1
+ br i1 true, label %not_zero, label %zero
+
+not_zero:
+ ret void
+
+; This block is reachable but removed by removeUnreachableBlocks()
+zero:
+; CHECK-NOT: @f
+ call void @f(i8 addrspace(1)* %arg) #1
+ ret void
+
+unreach:
+ call void @f(i8 addrspace(1)* %arg) #1
+ ret void
+}
+
+attributes #1 = { norecurse noimplicitfloat }

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

 ; RUN: opt -S -rewrite-statepoints-for-gc < %s | FileCheck %s
 ; RUN: opt -S -passes=rewrite-statepoints-for-gc < %s | FileCheck %s
 ;
 ; A test to make sure that we can look through bitcasts of
 ; vector types when a base pointer is contained in a vector.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 target triple = "x86_64-unknown-linux-gnu"
 
+declare i8 addrspace(1)* @foo()
+
 ; Function Attrs: uwtable
-define void @test() gc "statepoint-example" {
+define i32 @test() gc "statepoint-example" {
 ; CHECK-LABEL: @test
 entry:
 ; CHECK-LABEL: entry
 ; CHECK: %bc = bitcast
 ; CHECK: %[[p1:[A-Za-z0-9_]+]] = extractelement
 ; CHECK: %[[p2:[A-Za-z0-9_]+]] = extractelement
 ; CHECK: llvm.experimental.gc.statepoint
 ; CHECK: %[[p2]].relocated = {{.+}} @llvm.experimental.gc.relocate
 ; CHECK: %[[p1]].relocated = {{.+}} @llvm.experimental.gc.relocate
 ; CHECK: load atomic
   %bc = bitcast <8 x i8 addrspace(1)*> undef to <8 x i32 addrspace(1)*>
   %ptr= extractelement <8 x i32 addrspace(1)*> %bc, i32 7
-  %0 = call i8 addrspace(1)* undef() [ "deopt"() ]
+  %0 = call i8 addrspace(1)* @foo() [ "deopt"() ]
   %1 = load atomic i32, i32 addrspace(1)* %ptr unordered, align 4
-  unreachable
+  ret i32 %1
 }