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

[chandlerc]

Summary

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.

Note, I haven't written a lot of tests for this yet, but it already fixes the
FIXME in the existing test that motivates it. I'll write more detailed tests
for it, but wanted to go ahead and post the core idea behind this.

Depends on D21462

[silvas]

include/llvm/Analysis/CGSCCPassManager.h

528 ↗

(On Diff #66639)

If you update C in this assignment, where do you call AM.invalidate(...) on the original C? (this is needed to downward invalidate any function analyses that might depend on SCC analyses on the original C). Is this something you expect the SCC transformation being run by DevirtIteratingWrapper itself to do? It would be nice to see a unittest exhibiting this.

[chandlerc]

include/llvm/Analysis/CGSCCPassManager.h

528 ↗

(On Diff #66639)

The pass is required to preserve the call graph (that's part of passing it by argument) and if it updates it to reflect that in the UpdateResult and invalidate the analysis manager.

But all of this should really be spelled out in the prior patch that switches to this API, I'll update that patch with better documentation of this fact.

I certainly want to add verification of these properties as well, but I'd like to do that in a follow-up patch rather than put more into the existing patches out for review. (There is some verification already, but with some API changes and work I think we can get more verification into place.)

[chandlerc]

Update to use a new name (stemming from a conversation with Mehdi on IRC) and
include a more interesting and thorough test case that exhausts the iteration
space.

Also simplify some naming and other bits of the code. Nothing substantive
changed here though.

Should be in a good state at this point.

[silvas]

include/llvm/Analysis/CGSCCPassManager.h

528 ↗

(On Diff #66639)

But all of this should really be spelled out in the prior patch that switches to this API, I'll update that patch with better documentation of this fact.

Please add a test case as well.

[silvas]

include/llvm/Analysis/CGSCCPassManager.h

475 ↗

(On Diff #67060)

Typo: MaxRepeatitions -> MaxRepetitions

557 ↗

(On Diff #67060)

Can you just avoid keeping WeakVH's to intrinsics? The langref says you can't take their address. Therefore, a devirtualized call will never be to an intrinsic.
http://llvm.org/docs/LangRef.html#intrinsic-functions

[chandlerc]

include/llvm/Analysis/CGSCCPassManager.h

528 ↗

(On Diff #67060)

I'm not sure what you mean...

I think there are already test cases for invalidation, but I can double check. But that shouldn't be in *this* patch, that should be in the big CG update patch. I haven't gone back to that one to update it substantially (this iteration utility was requested and I wanted to get it out for review) but I'm happy to add test cases there, or add more testing in subsequent patches for that stack as problems are discovered.

557 ↗

(On Diff #67060)

It's not that we could create a VH to a call to an instrinsic.

Above, we create a VH to an indirect call. That indirect call gets devirtualized into a direct call. At some point, some pass may turn that direct call into a call to an intrinsic, and if it does that this code needs to defensively prepare for it.

Sadly, there is no pass in tree that does this, but without this logic the pass would crash if anything ever conspired to trigger this.

[silvas]

include/llvm/Analysis/CGSCCPassManager.h

528 ↗

(On Diff #67060)

I think there are already test cases for invalidation, but I can double check. But that shouldn't be in *this* patch, that should be in the big CG update patch.

Totally agreed. Sorry if it wan't clear from context, but that's what I meant.

I haven't gone back to that one to update it substantially (this iteration utility was requested and I wanted to get it out for review) but I'm happy to add test cases there, or add more testing in subsequent patches for that stack as problems are discovered.

That sounds reasonable. I'll add any comments there once the discussion reopens there.

557 ↗

(On Diff #67060)

I'm not sure I understand. In the situation you described regarding the intrinsic, we did in fact devirtualize something. So why are we avoiding setting Devirt = true in that case?
Is it because that doesn't actually add extra call edges to the lazy call graph? If that's the case, you need the same treatment for calls to external function declarations and calls to inlineasm too, right?

You may want to add some more comments about this (and maybe a test case (unittest?) if it isn't too verbose).

[chandlerc]

include/llvm/Analysis/CGSCCPassManager.h

557 ↗

(On Diff #67060)

Sorry, I explained this really poorly.

The idea I had was that if we end up with a call to an intrinsic, there is no longer any call graph or IPO refinement to motivate iteration: scalar passes can already fully reason about the intrinsic.

I've added a bunch of comments and restructured the code to try to make this more clear.

I'm not sure I can craft a test case that does this, but I'll take a stab at it...

[chandlerc]

Rebase and address review comments.

[chandlerc]

include/llvm/Analysis/CGSCCPassManager.h

557 ↗

(On Diff #67060)

Actually, got a test for this and it convinced me we shouldn't be special casing intrinsics. We can actually do very useful function attrs work here even when "devirtualizing" to an intrinsic that won't be inlined.

Even better, that test pointed out that this was missing a heuristic from the legacy PM's version: we don't track the change of count and have that also trigger iteration.

I've added the heuristic, removed any special casing of intrinsics, and have a nice test case that covers this logic.

[chandlerc]

Add a test case that covers devirtualization that actually turns into an
intrinsic.

Also improved the testing to be more precise and robust.

Added support for iterating even if we turn an indirect call into a direct call
to an intrinsic and added support for the heuristic of changing the call count
that the old PM used.

[chandlerc]

Rebase and ping.

I've also now updated one of the devirtualization test cases for the old
inliner to run with this combined with the inliner in the new pass manager and
it passes now.

There is another devirt test case for the old pass manager that this can't
handle though, and I'm pondering the best way to handle that scenario.

[mehdi_amini]

LGTM.

include/llvm/Analysis/CGSCCPassManager.h

637 ↗

(On Diff #82529)

Wasn't it a limitation from MSVC2013 that is lifted now that we don't support it anymore?

703 ↗

(On Diff #82529)

What about something more explicit than i? IterationNum or something like that.
(Two reasons: 1) this is a long loop body and 2) i is used in the body (and also there is another nested loop also using an index i)

733 ↗

(On Diff #82529)

We could have some debug logging about "Found a devirtualized call from CS->getParent()->getParent()->getName() to F->getName()".

736 ↗

(On Diff #82529)

On the first iteration, it is weird to check all the value handles to find an impossible devirtualized call, but I don't have a better suggestion to reorganize the code that does not make it equally annoying somewhere else...

test/Other/cgscc-devirt-iteration.ll

36 ↗

(On Diff #82529)

s/repeatitions/repetitions/ (same in many other places in this patch)

43 ↗

(On Diff #82529)

readonce? Do you mean readnone?

60 ↗

(On Diff #82529)

If I follow correctly: this is the devirtualization that will trigger the first restart.

82 ↗

(On Diff #82529)

And this is devirtualized during the second iteration, enabling the third one to deduce the readnone.

100 ↗

(On Diff #82529)

Should you check that BEFORE contains the call to llvm.memcpy and not just devirtualize regularly to memcpy?

test/Other/cgscc-observe-devirt.ll

5 ↗

(On Diff #82529)

The comment here suggested that this RUN line was useful outside of the repetition?

[chandlerc]

Thanks! Submitting with fixes for essentially all of this. There is one question below that I'm happy to continue discussing and if any of the fixes didn't match what you were expecting just lemme know!

include/llvm/Analysis/CGSCCPassManager.h

736 ↗

(On Diff #82529)

It doesn't look impossible to me? We have run the pass once at this point, and had handles held across it. Let me know if I'm missing something here though, happy to look for a better way to structure the code.

test/Other/cgscc-devirt-iteration.ll

43 ↗

(On Diff #82529)

Er, readonly. I've added a sentence to clarify. We first deduce readonly, and then readnone.

No idea where 'readonce' came from. Fixed that.

60 ↗

(On Diff #82529)

Yes, and commented.

82 ↗

(On Diff #82529)

Correct, and again, comments added for a future reader.

100 ↗

(On Diff #82529)

Not just before, but all of them. Added.

test/Other/cgscc-observe-devirt.ll

5 ↗

(On Diff #82529)

Good point. I've restored it.

[mehdi_amini]

include/llvm/Analysis/CGSCCPassManager.h

736 ↗

(On Diff #82529)

Sorry, I figured after writing this comment but somehow didn't delete it (likely clicked the X instead, which just hide it).

It's all good :)

llvm/trunk/include/llvm/Analysis/CGSCCPassManager.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 
 #include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/InstIterator.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
 
 struct CGSCCUpdateResult;
 
 /// Extern template declaration for the analysis set for this IR unit.
 extern template class AllAnalysesOn<LazyCallGraph::SCC>;
 

 /// \brief A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
 CGSCCToFunctionPassAdaptor<FunctionPassT>
 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass, bool DebugLogging = false) {
   return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass),
                                                    DebugLogging);
 }
+
+/// A helper that repeats an SCC pass each time an indirect call is refined to
+/// a direct call by that pass.
+///
+/// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they
+/// change shape, we may also want to repeat an SCC pass if it simply refines
+/// an indirect call to a direct call, even if doing so does not alter the
+/// shape of the graph. Note that this only pertains to direct calls to
+/// functions where IPO across the SCC may be able to compute more precise
+/// results. For intrinsics, we assume scalar optimizations already can fully
+/// reason about them.
+///
+/// This repetition has the potential to be very large however, as each one
+/// might refine a single call site. As a consequence, in practice we use an
+/// upper bound on the number of repetitions to limit things.
+template <typename PassT>
+class DevirtSCCRepeatedPass
+    : public PassInfoMixin<DevirtSCCRepeatedPass<PassT>> {
+public:
+  explicit DevirtSCCRepeatedPass(PassT Pass, int MaxIterations,
+                                 bool DebugLogging = false)
+      : Pass(std::move(Pass)), MaxIterations(MaxIterations),
+        DebugLogging(DebugLogging) {}
+
+  /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating
+  /// whenever an indirect call is refined.
+  PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR) {
+    PreservedAnalyses PA = PreservedAnalyses::all();
+
+    // The SCC may be refined while we are running passes over it, so set up
+    // a pointer that we can update.
+    LazyCallGraph::SCC *C = &InitialC;
+
+    // Collect value handles for all of the indirect call sites.
+    SmallVector<WeakVH, 8> CallHandles;
+
+    // Struct to track the counts of direct and indirect calls in each function
+    // of the SCC.
+    struct CallCount {
+      int Direct;
+      int Indirect;
+    };
+
+    // Put value handles on all of the indirect calls and return the number of
+    // direct calls for each function in the SCC.
+    auto ScanSCC = [](LazyCallGraph::SCC &C,
+                      SmallVectorImpl<WeakVH> &CallHandles) {
+      assert(CallHandles.empty() && "Must start with a clear set of handles.");
+
+      SmallVector<CallCount, 4> CallCounts;
+      for (LazyCallGraph::Node &N : C) {
+        CallCounts.push_back({0, 0});
+        CallCount &Count = CallCounts.back();
+        for (Instruction &I : instructions(N.getFunction()))
+          if (auto CS = CallSite(&I)) {
+            if (CS.getCalledFunction()) {
+              ++Count.Direct;
+            } else {
+              ++Count.Indirect;
+              CallHandles.push_back(WeakVH(&I));
+            }
+          }
+      }
+
+      return CallCounts;
+    };
+
+    // Populate the initial call handles and get the initial call counts.
+    auto CallCounts = ScanSCC(*C, CallHandles);
+
+    for (int Iteration = 0;; ++Iteration) {
+      PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
+
+      // If the SCC structure has changed, bail immediately and let the outer
+      // CGSCC layer handle any iteration to reflect the refined structure.
+      if (UR.UpdatedC && UR.UpdatedC != C) {
+        PA.intersect(std::move(PassPA));
+        break;
+      }
+
+      // Check that we didn't miss any update scenario.
+      assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
+      assert(C->begin() != C->end() && "Cannot have an empty SCC!");
+      assert((int)CallCounts.size() == C->size() &&
+             "Cannot have changed the size of the SCC!");
+
+      // Check whether any of the handles were devirtualized.
+      auto IsDevirtualizedHandle = [&](WeakVH &CallH) {
+        if (!CallH)
+          return false;
+        auto CS = CallSite(CallH);
+        if (!CS)
+          return false;
+
+        // If the call is still indirect, leave it alone.
+        Function *F = CS.getCalledFunction();
+        if (!F)
+          return false;
+
+        if (DebugLogging)
+          dbgs() << "Found devirutalized call from "
+                 << CS.getParent()->getParent()->getName() << " to "
+                 << F->getName() << "\n";
+
+        // We now have a direct call where previously we had an indirect call,
+        // so iterate to process this devirtualization site.
+        return true;
+      };
+      bool Devirt = any_of(CallHandles, IsDevirtualizedHandle);
+
+      // Rescan to build up a new set of handles and count how many direct
+      // calls remain. If we decide to iterate, this also sets up the input to
+      // the next iteration.
+      CallHandles.clear();
+      auto NewCallCounts = ScanSCC(*C, CallHandles);
+
+      // If we haven't found an explicit devirtualization already see if we
+      // have decreased the number of indirect calls and increased the number
+      // of direct calls for any function in the SCC. This can be fooled by all
+      // manner of transformations such as DCE and other things, but seems to
+      // work well in practice.
+      if (!Devirt)
+        for (int i = 0, Size = C->size(); i < Size; ++i)
+          if (CallCounts[i].Indirect > NewCallCounts[i].Indirect &&
+              CallCounts[i].Direct < NewCallCounts[i].Direct) {
+            Devirt = true;
+            break;
+          }
+
+      if (!Devirt) {
+        PA.intersect(std::move(PassPA));
+        break;
+      }
+
+      // Otherwise, if we've already hit our max, we're done.
+      if (Iteration >= MaxIterations) {
+        if (DebugLogging)
+          dbgs() << "Found another devirtualization after hitting the max "
+                    "number of repetitions ("
+                 << MaxIterations << ") on SCC: " << *C << "\n";
+        PA.intersect(std::move(PassPA));
+        break;
+      }
+
+      if (DebugLogging)
+        dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
+               << *C << "\n";
+
+      // Move over the new call counts in preparation for iterating.
+      CallCounts = std::move(NewCallCounts);
+
+      // Update the analysis manager with each run and intersect the total set
+      // of preserved analyses so we're ready to iterate.
+      AM.invalidate(*C, PassPA);
+      PA.intersect(std::move(PassPA));
+    }
+
+    // Note that we don't add any preserved entries here unlike a more normal
+    // "pass manager" because we only handle invalidation *between* iterations,
+    // not after the last iteration.
+    return PA;
+  }
+
+private:
+  PassT Pass;
+  int MaxIterations;
+  bool DebugLogging;
+};
+
+/// \brief A function to deduce a function pass type and wrap it in the
+/// templated adaptor.
+template <typename PassT>
+DevirtSCCRepeatedPass<PassT>
+createDevirtSCCRepeatedPass(PassT Pass, int MaxIterations,
+                            bool DebugLogging = false) {
+  return DevirtSCCRepeatedPass<PassT>(std::move(Pass), MaxIterations,
+                                      DebugLogging);
+}
 }
 
 #endif

llvm/trunk/lib/Passes/PassBuilder.cpp

static Optional<int> parseRepeatPassName(StringRef Name) {
   if (!Name.consume_front("repeat<") || !Name.consume_back(">"))
     return None;
   int Count;
   if (Name.getAsInteger(0, Count) || Count <= 0)
     return None;
   return Count;
 }
 
+static Optional<int> parseDevirtPassName(StringRef Name) {
+  if (!Name.consume_front("devirt<") || !Name.consume_back(">"))
+    return None;
+  int Count;
+  if (Name.getAsInteger(0, Count) || Count <= 0)
+    return None;
+  return Count;
+}
+
 static bool isModulePassName(StringRef Name) {
   // Manually handle aliases for pre-configured pipeline fragments.
   if (Name.startswith("default") || Name.startswith("lto"))
     return DefaultAliasRegex.match(Name);
 
   // Explicitly handle pass manager names.
   if (Name == "module")
     return true;
static bool isCGSCCPassName(StringRef Name) {
   if (Name == "cgscc")
     return true;
   if (Name == "function")
     return true;
 
   // Explicitly handle custom-parsed pass names.
   if (parseRepeatPassName(Name))
     return true;
+  if (parseDevirtPassName(Name))
+    return true;
 
 #define CGSCC_PASS(NAME, CREATE_PASS)                                          \
   if (Name == NAME)                                                            \
     return true;
 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)                                      \
   if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">")           \
     return true;
 #include "PassRegistry.def"
if (!InnerPipeline.empty()) {
     if (auto Count = parseRepeatPassName(Name)) {
       CGSCCPassManager NestedCGPM(DebugLogging);
       if (!parseCGSCCPassPipeline(NestedCGPM, InnerPipeline, VerifyEachPass,
                                   DebugLogging))
         return false;
       CGPM.addPass(createRepeatedPass(*Count, std::move(NestedCGPM)));
       return true;
     }
+    if (auto MaxRepetitions = parseDevirtPassName(Name)) {
+      CGSCCPassManager NestedCGPM(DebugLogging);
+      if (!parseCGSCCPassPipeline(NestedCGPM, InnerPipeline, VerifyEachPass,
+                                  DebugLogging))
+        return false;
+      CGPM.addPass(createDevirtSCCRepeatedPass(std::move(NestedCGPM),
+                                               *MaxRepetitions, DebugLogging));
+      return true;
+    }
     // Normal passes can't have pipelines.
     return false;
   }
 
   // Now expand the basic registered passes from the .inc file.
 #define CGSCC_PASS(NAME, CREATE_PASS)                                          \
   if (Name == NAME) {                                                          \
     CGPM.addPass(CREATE_PASS);                                                 \

llvm/trunk/test/Other/cgscc-devirt-iteration.ll

+; The CGSCC pass manager includes an SCC iteration utility that tracks indirect
+; calls that are turned into direct calls (devirtualization) and re-visits the
+; SCC to expose those calls to the SCC-based IPO passes. 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,function(gvn,instcombine))' -S < %s | FileCheck %s --check-prefix=CHECK --check-prefix=BEFORE
+; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(devirt<1>(function-attrs,function(gvn,instcombine)))' -S < %s | FileCheck %s --check-prefix=CHECK --check-prefix=AFTER --check-prefix=AFTER1
+; RUN: opt -aa-pipeline=basic-aa -passes='cgscc(devirt<2>(function-attrs,function(gvn,instcombine)))' -S < %s | FileCheck %s --check-prefix=CHECK --check-prefix=AFTER --check-prefix=AFTER2
+
+declare void @readnone() readnone
+; CHECK: Function Attrs: readnone
+; CHECK: declare void @readnone()
+
+declare void @unknown()
+; CHECK-NOT: Function Attrs
+; CHECK: declare void @unknown()
+
+; The @test1 function checks that when we refine an indirect call to a direct
+; call we revisit the SCC passes to reflect the more precise information. This
+; is the basic functionality.
+
+define void @test1() {
+; BEFORE-NOT: Function Attrs
+; AFTER: Function Attrs: readnone
+; CHECK: define void @test1()
+entry:
+  %fptr = alloca void ()*
+  store void ()* @readnone, void ()** %fptr
+  %f = load void ()*, void ()** %fptr
+  call void %f()
+  ret void
+}
+
+; The @test2_* functions check that when we need multiple (in this case 2)
+; repetitions to compute some state that is incrementally exposed with each
+; one, the limit on repetitions is enforced. So we make progress with
+; one repetition but not as much as with three.
+;
+; This is somewhat awkward to test because we have to contrive to have a state
+; repetition triggered and observed with very few passes. The technique here
+; is to have one indirect call that can only be resolved when the entire SCC is
+; deduced as readonly, and mark that indirect call at the call site as readonly
+; to make that possible. This forces us to first deduce readonly, then
+; devirtualize again, and then deduce readnone.
+
+declare void @readnone_with_arg(void ()**) readnone
+; CHECK: Function Attrs: readnone
+; CHECK: declare void @readnone_with_arg(void ()**)
+
+define void @test2_a(void ()** %ignore) {
+; BEFORE-NOT: Function Attrs
+; AFTER1: Function Attrs: readonly
+; AFTER2: Function Attrs: readnone
+; BEFORE: define void @test2_a(void ()** %ignore)
+; AFTER: define void @test2_a(void ()** readnone %ignore)
+entry:
+  %f1ptr = alloca void (void ()**)*
+  store void (void ()**)* @readnone_with_arg, void (void ()**)** %f1ptr
+  %f1 = load void (void ()**)*, void (void ()**)** %f1ptr
+  ; This indirect call is the first to be resolved, allowing us to deduce
+  ; readonly but not (yet) readnone.
+  call void %f1(void ()** %ignore)
+; CHECK: call void @readnone_with_arg(void ()** %ignore)
+
+  ; Bogus call to test2_b to make this a cycle.
+  call void @test2_b()
+
+  ret void
+}
+
+define void @test2_b() {
+; BEFORE-NOT: Function Attrs
+; AFTER1: Function Attrs: readonly
+; AFTER2: Function Attrs: readnone
+; CHECK: define void @test2_b()
+entry:
+  %f2ptr = alloca void ()*
+  store void ()* @readnone, void ()** %f2ptr
+  ; Call the other function here to prevent forwarding until the SCC has had
+  ; function attrs deduced.
+  call void @test2_a(void ()** %f2ptr)
+
+  %f2 = load void ()*, void ()** %f2ptr
+  ; This is the second indirect call to be resolved, and can only be resolved
+  ; after we deduce 'readonly' for the rest of the SCC. Once it is
+  ; devirtualized, we can deduce readnone for the SCC.
+  call void %f2() readonly
+; BEFORE: call void %f2()
+; AFTER: call void @readnone()
+
+  ret void
+}
+
+declare i8* @memcpy(i8*, i8*, i64)
+; CHECK-NOT: Function Attrs
+; CHECK: declare i8* @memcpy(i8*, i8*, i64)
+
+; The @test3 function checks that when we refine an indirect call to an
+; intrinsic we still revisit the SCC pass. This also covers cases where the
+; value handle itself doesn't persist due to the nature of how instcombine
+; creates the memcpy intrinsic call, and we rely on the count of indirect calls
+; decreasing and the count of direct calls increasing.
+define void @test3(i8* %src, i8* %dest, i64 %size) {
+; CHECK-NOT: Function Attrs
+; BEFORE: define void @test3(i8* %src, i8* %dest, i64 %size)
+; AFTER: define void @test3(i8* nocapture readonly %src, i8* nocapture %dest, i64 %size)
+  %fptr = alloca i8* (i8*, i8*, i64)*
+  store i8* (i8*, i8*, i64)* @memcpy, i8* (i8*, i8*, i64)** %fptr
+  %f = load i8* (i8*, i8*, i64)*, i8* (i8*, i8*, i64)** %fptr
+  call i8* %f(i8* %dest, i8* %src, i64 %size)
+; CHECK: call void @llvm.memcpy
+  ret void
+}

llvm/trunk/test/Other/cgscc-observe-devirt.ll

+; 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
 }
 
 ; CHECK: attributes #0 = { readnone }

llvm/trunk/test/Transforms/Inline/devirtualize-2.ll

 ; RUN: opt < %s -inline -S | FileCheck %s
+; RUN: opt < %s -passes='cgscc(devirt<4>(inline))' -S | FileCheck %s
 ; PR4834
 
 define i32 @test1() {
   %funcall1_ = call fastcc i32 ()* () @f1()
   %executecommandptr1_ = call i32 %funcall1_()
   ret i32 %executecommandptr1_
 }