[PM] Introduce a devirtualization iteration layer for the new PM.

This is an orthogonal and separated layer instead of being embedded
inside the pass manager. While it adds a small amount of complexity, it
is fairly minimal and the composability and control seems worth the
cost.

The logic for this ends up being nicely isolated and targeted. It should
be easy to experiment with different iteration strategies wrapped around
the CGSCC bottom-up walk using this kind of facility.

The mechanism used to track devirtualization is the simplest one I came
up with. I think it handles most of the cases the existing iteration
machinery handles, but I haven't done a *very* in depth analysis. It
does however match the basic intended semantics, and we can tweak or
tune its exact behavior incrementally as necessary. One thing that we
may want to revisit is freshly building the value handle set on each
iteration. While I don't think this will be a significant cost (it is
strictly fewer value handles but more churn of value handes than the old
call graph), it is conceivable that we'll want a somewhat more clever
tracking mechanism. My hope is to layer that on as a follow up patch
with data supporting any implementation complexity it adds.

This code also provides for a basic count heuristic: if the number of
indirect calls decreases and the number of direct calls increases for
a given function in the SCC, we assume devirtualization is responsible.
This matches the heuristics currently used in the legacy pass manager.

Differential Revision: https://reviews.llvm.org/D23114

llvm-svn: 290665

1 files changed, 46 insertions, 73 deletions

diff --git a/llvm/test/Other/cgscc-observe-devirt.ll b/llvm/test/Other/cgscc-observe-devirt.ll
index 2b1e7d8134ef..3b35f0edc120 100644
--- a/llvm/test/Other/cgscc-observe-devirt.ll
+++ b/llvm/test/Other/cgscc-observe-devirt.ll
@@ -1,130 +1,103 @@
+; Make sure that even without some external devirtualization iteration tool,
+; the CGSCC pass manager correctly observes and re-visits SCCs that change
+; structure due to devirtualization. We trigger devirtualization here with GVN
+; which forwards a store through a load and to an indirect call.
+;
 ; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs)' -S < %s | FileCheck %s --check-prefix=BEFORE
 ; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(gvn))' -S < %s | FileCheck %s --check-prefix=AFTER
 ;
 ; Also check that adding an extra CGSCC pass after the function update but
 ; without requiring the outer manager to iterate doesn't break any invariant.
-; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(gvn),function-attrs)' -S < %s | FileCheck %s --check-prefix=AFTER2
+; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(function-attrs,function(gvn),function-attrs)' -S < %s | FileCheck %s --check-prefix=AFTER
 
 declare void @readnone() readnone
 declare void @unknown()
 
-; The @test1_* functions check that when we refine an indirect call to a direct
-; call, even if it doesn't change the call graph structure, we revisit the SCC
-; passes to reflect the more precise information.
-; FIXME: Currently, this isn't implemented in the new pass manager and so we
-; only get this with AFTER2, not with AFTER.
-
-; BEFORE: define void @test1_a() {
-; AFTER: define void @test1_a() {
-; AFTER2: define void @test1_a() {
-define void @test1_a() {
-  %fptr = alloca void()*
-  store void()* @unknown, void()** %fptr
-  %f = load void()*, void()** %fptr
-  call void %f()
-  ret void
-}
-
-; BEFORE: define void @test1_b() {
-; AFTER: define void @test1_b() {
-; AFTER2: define void @test1_b() #0 {
-define void @test1_b() {
-  %fptr = alloca void()*
-  store void()* @readnone, void()** %fptr
-  %f = load void()*, void()** %fptr
-  call void %f()
-  ret void
-}
-
-; The @test2_* checks that if we refine an indirect call to a direct call and
+; The @test1_* checks that if we refine an indirect call to a direct call and
 ; in the process change the very structure of the call graph we also revisit
 ; that component of the graph and do so in an up-to-date fashion.
 
-; BEFORE: define void @test2_a1() {
-; AFTER: define void @test2_a1() {
-; AFTER2: define void @test2_a1() {
-define void @test2_a1() {
+; BEFORE: define void @test1_a1() {
+; AFTER: define void @test1_a1() {
+define void @test1_a1() {
   %fptr = alloca void()*
-  store void()* @test2_b2, void()** %fptr
-  store void()* @test2_b1, void()** %fptr
+  store void()* @test1_b2, void()** %fptr
+  store void()* @test1_b1, void()** %fptr
   %f = load void()*, void()** %fptr
   call void %f()
   ret void
 }
 
-; BEFORE: define void @test2_b1() {
-; AFTER: define void @test2_b1() {
-; AFTER2: define void @test2_b1() {
-define void @test2_b1() {
+; BEFORE: define void @test1_b1() {
+; AFTER: define void @test1_b1() {
+define void @test1_b1() {
   call void @unknown()
-  call void @test2_a1()
+  call void @test1_a1()
   ret void
 }
 
-; BEFORE: define void @test2_a2() {
-; AFTER: define void @test2_a2() #0 {
-; AFTER2: define void @test2_a2() #0 {
-define void @test2_a2() {
+; BEFORE: define void @test1_a2() {
+; AFTER: define void @test1_a2() #0 {
+define void @test1_a2() {
   %fptr = alloca void()*
-  store void()* @test2_b1, void()** %fptr
-  store void()* @test2_b2, void()** %fptr
+  store void()* @test1_b1, void()** %fptr
+  store void()* @test1_b2, void()** %fptr
   %f = load void()*, void()** %fptr
   call void %f()
   ret void
 }
 
-; BEFORE: define void @test2_b2() {
-; AFTER: define void @test2_b2() #0 {
-; AFTER2: define void @test2_b2() #0 {
-define void @test2_b2() {
+; BEFORE: define void @test1_b2() {
+; AFTER: define void @test1_b2() #0 {
+define void @test1_b2() {
   call void @readnone()
-  call void @test2_a2()
+  call void @test1_a2()
   ret void
 }
 
 
-; The @test3_* set of functions exercise a case where running function passes
+; The @test2_* set of functions exercise a case where running function passes
 ; introduces a new post-order relationship that was not present originally and
 ; makes sure we walk across the SCCs in that order.
 
-; CHECK: define void @test3_a() {
-define void @test3_a() {
-  call void @test3_b1()
-  call void @test3_b2()
-  call void @test3_b3()
+; CHECK: define void @test2_a() {
+define void @test2_a() {
+  call void @test2_b1()
+  call void @test2_b2()
+  call void @test2_b3()
   call void @unknown()
   ret void
 }
 
-; CHECK: define void @test3_b1() #0 {
-define void @test3_b1() {
+; CHECK: define void @test2_b1() #0 {
+define void @test2_b1() {
   %fptr = alloca void()*
-  store void()* @test3_a, void()** %fptr
+  store void()* @test2_a, void()** %fptr
   store void()* @readnone, void()** %fptr
   %f = load void()*, void()** %fptr
   call void %f()
   ret void
 }
 
-; CHECK: define void @test3_b2() #0 {
-define void @test3_b2() {
+; CHECK: define void @test2_b2() #0 {
+define void @test2_b2() {
   %fptr = alloca void()*
-  store void()* @test3_a, void()** %fptr
-  store void()* @test3_b2, void()** %fptr
-  store void()* @test3_b3, void()** %fptr
-  store void()* @test3_b1, void()** %fptr
+  store void()* @test2_a, void()** %fptr
+  store void()* @test2_b2, void()** %fptr
+  store void()* @test2_b3, void()** %fptr
+  store void()* @test2_b1, void()** %fptr
   %f = load void()*, void()** %fptr
   call void %f()
   ret void
 }
 
-; CHECK: define void @test3_b3() #0 {
-define void @test3_b3() {
+; CHECK: define void @test2_b3() #0 {
+define void @test2_b3() {
   %fptr = alloca void()*
-  store void()* @test3_a, void()** %fptr
-  store void()* @test3_b2, void()** %fptr
-  store void()* @test3_b3, void()** %fptr
-  store void()* @test3_b1, void()** %fptr
+  store void()* @test2_a, void()** %fptr
+  store void()* @test2_b2, void()** %fptr
+  store void()* @test2_b3, void()** %fptr
+  store void()* @test2_b1, void()** %fptr
   %f = load void()*, void()** %fptr
   call void %f()
   ret void