Add CalledValuePropagation pass

[mssimpso]

Summary

This patch adds a new transformation for propagating values used for indirect calls. The idea for this pass came from the review of D36432. The pass performs an IPSCCP-like analysis, propagating functions to indirect call sites and then attaching metadata to the call sites indicating the set of functions they may potentially target at run-time.

This metadata may be consumed by later transformations. My initial plan is to use the metadata to perform indirect call promotion for call sites that are known to target only two functions. The metadata can also be used, for example, to allow call sites to intersect the function attributes of the functions they are known to target (i.e., in CallSiteBase::hasFnAttr).

Although I've implemented this as a separate pass, the functionality could be added to IPSCCP without too much effort. I chose a separate pass primarily as an opportunity to revive the unused generic sparse propagation solver, but this isn't strictly necessary.

If patch sounds reasonable, please take a look at the dependent patches as well. D37354 adds the new kind of metadata, and D37353 enables the generic sparse propagation solver to work interprocedurally similar to IPSCCP. I've added a simple demonstration test to this patch, but I will add more if the overall approach looks good.

[efriedma]

I'd like to see a better motivating example; the specific example here could be handled by something more targeted in arg-promotion or something.

What's the difference between overdefined and untracked?

[mssimpso]

In D37355#858332, @efriedma wrote:

I'd like to see a better motivating example; the specific example here could be handled by something more targeted in arg-promotion or something.

Sure, Eli. Thanks for taking a look. I can add another example or two as test cases, although I'd like to try to not make them too complicated for now. The specific example I included here was pulled from D36432, and may not be the best. I'm currently only propagating through calls/returns, loads/stores through global variables, and phis/selects, which may be all we would want to handle for this kind of task.

What's the difference between overdefined and untracked?

The untracked value is something the generic solver added, and there isn't a big conceptual difference between it and overdefined(at least in this patch). From the comments in the generic solver, it uses untracked to represent "something that is obviously uninteresting to the analysis" in order to "avoid pointless work." Practically, I think this just means that it doesn't maintain mappings for these values in its internal state maps. But yeah, initializing a value as overdefined instead of untracked should end up with the same result. And if this were implemented in IPSCCP, that is what we would do.

[davide]

As Eli, I'd like to see other examples (I'm confident you can find some). In the meanwhile, a first review.

lib/Transforms/IPO/CalledValuePropagation.cpp

36–38 ↗

(On Diff #113465)

Is there a way we can avoid somewhat arbitrary cutoffs? They've been us a lot in the past.

52 ↗

(On Diff #113465)

As there's an increasing interest in IPO in llvm (yay) we might consider taking this kind of generic function and move to a common helper (e.g. IPO/Utils). FWIW, GCC has something like that. Also, I'm pretty sure IPSCCP has the same exact function (at least as far as I remember) and in case we find a bug there we need to update a single copy.

58 ↗

(On Diff #113465)

I'm unsure about this one. I had a bug lying around as sparse conditional constant propagation has a similar problem (i.e. it ignores variables which address is taken, although I had hard time to understand the concept of address taken for GVs).

108 ↗

(On Diff #113465)

is this deterministic?

141 ↗

(On Diff #113465)

I'm not familiar with this style of comments, and I don't think it's actually common in LLVM (although I may be wrong).

338 ↗

(On Diff #113465)

DenseSet?

344 ↗

(On Diff #113465)

Maybe at some point we can get rid of this.

382 ↗

(On Diff #113465)

I expected this to preserve something? [probably the same set that IPSCCP preserves]

[mssimpso]

Hi Davide,

Thanks very much for the initial review! I'm working on adding a few more motivating test cases that demonstrate missed optimization opportunities. I'll upload those shortly.

lib/Transforms/IPO/CalledValuePropagation.cpp

36–38 ↗

(On Diff #113465)

The cut-off used here is to prevent the number of lattice values we have to maintain in a std::set from growing too large. As I mentioned in the comments, the number of possible values could technically grow quite large (set of all subsets). I don't think this is likely to occur in practice, though.

One thing we could do to relax any cut-off is to make the lattice values take up less space. We could do this by representing the set of target functions as a bit vector, for example, instead of a vector of function pointers. For this particular task, though, I'm not sure how useful it would be to leave the number of target functions unconstrained.

I envisioned two main uses for this work (although I'm sure we can come up with more): indirect call promotion, and intersecting function attributes at call sites. My thinking was that if we wanted to do indirect call promotion, we probably would want to give up if the call could target a lot of functions (i.e., if we end up having to do more than insert a simple if-else). Intersecting attributes is less clear to me, but I was thinking that the chance that all possible call targets would have interesting attributes (say, a norecurse or readnone) would be small if the set of targets gets very large.

52 ↗

(On Diff #113465)

This makes sense to me. Yes, the check for trackable functions and global variables is more-or-less taken from IPSCCP.

58 ↗

(On Diff #113465)

I agree. This was PR33143, for reference. I had originally thought we could add a hasAddressTaken to GlobalVariable similar to what we have in Function, but after hearing feedback from Eli, I'm not sure that would help. In this case and in IPSCCP, we're interested in whether we can track the values loaded/stored at a given global variable. This is why we also have to check that the memory operations are not volatile.

108 ↗

(On Diff #113465)

It is, but it doesn't look that way because I sort and unique the functions vector before constructing the lattice values (in MergeValues). The functions vector is essentially a sorted set that I tried to make more efficient by using a SmallVector. Also, the functions vector doesn't change after a lattice value object is constructed. Multiple LLVM values will map to the same lattice value object (see also the DenseSet comment below).

141 ↗

(On Diff #113465)

It's used in a few places, but I'm happy to document these functions separately. My aim was to not be overly repetitive.

338 ↗

(On Diff #113465)

As written, I don't think DenseSet will work, unfortunately. Internally, the generic solver represents lattice values as void pointers (it's old code I guess), so they either have to fit in that amount of space (like the PointerIntPair in SCCP) or they have to index some uniquing data structure. std::set doesn't invalidate iterators after insertion like DenseSet does. That let's us use the address of our custom lattice values as the void pointer in the generic solver. This means that LatticeVals holds the unique lattice value objects, and multiple LLVM values end up mapping to the address of same lattice value object. It's possible there is a better way to interface with the generic solver, though.

344 ↗

(On Diff #113465)

I agree. Eli mentioned this as well. Untracked and overdefined are more-or-less the same.

382 ↗

(On Diff #113465)

This is what IPSCCP does, actually. But in this case, since we're only adding metadata we could just preserve all. We could even make this an analysis, like TBAA, which also just attaches metadata.

[mssimpso]

Add some more interesting/motivating test cases. These are abstractions of some cases I've come across in benchmarks. They could be optimized if we knew something about the targets of the indirect calls.

[mssimpso]

Fixed a comment in one of the new test cases. Thanks again for taking a look!

[mssimpso]

Addressed comments from Davide and Hal

• Incorporated feedback from D37354 (changed metadata from !targets to !callees, etc.).
• Moved common IPO utility functions to shared location (D37638)
• Separated comment groups into individual comments
• Marked the pass "preserves all"

[mssimpso]

Renamed "!targets" to "!callees" in a few comments I missed from the previous revision

[mssimpso]

Made untracked values overdefined.

After looking at the generic solver more closely, I found that when a value is initialized to untracked, it's users aren't notified and added to the work list for processing. This is the intended behavior, but when using untracked, I think it's going to be very easy to make a mistake and not see the entire module. It's probably better for us to track all the values, and mark the uninteresting ones overdefined. This update changes the patch to do this.

[mssimpso]

Hi everyone,

Are there anymore comments on this patch, or any of its dependencies? Thanks!

[mssimpso]

Ping.

[• dberlin]

I see this review has been hanging around a while, so i'll take a stab at reviewing it.

(Random note: I know you didn't do this, but getOrInitValueState is very verbose for a thing that everything is probably going to use by default.
IMHO, the API should be getOrInitValueState is renamed to getValueState, getValueState is renamed to getExistingValueState.
Similarly with the other calls.

Since there are no other users, this may be a good time to change it in a followup)

Generally looks very very good. I don't think i have any algorithmic complaints here at all.
If you agree with the templating vs void ptrs, i'm happy to go commit that patch.

lib/Transforms/IPO/CalledValuePropagation.cpp

203 ↗

(On Diff #115443)

Again, not a thing you have to address here, but is there a reason it's not just templated?

IE define an interface lattice vals must meet, and template it relying on that interface to exist.

This is what we do with GraphTraits, for example.

Using void pointers and having to go through these machinations seems .... ugly

(Edit: I have a patch to template it, here: https://reviews.llvm.org/differential/diff/117397/)

206 ↗

(On Diff #115443)

DenseSet?

(Do you need the ordering?)

228 ↗

(On Diff #115443)

Nitpick: IndirectCalls.insert(I)

[davide]

Generally I feel like it's getting there. Some small comments, but I expect this to be ready to be committed soon'ish

lib/Transforms/IPO/CalledValuePropagation.cpp

181–190 ↗

(On Diff #115443)

you can simplify just doing
return OS <<

286 ↗

(On Diff #115443)

DenseSet maybe?

lib/Transforms/IPO/PassManagerBuilder.cpp

717 ↗

(On Diff #115443)

I'd make an RFC on llvm-dev as people might have custom pipelines.

[davide]

And sorry for letting this hanging for so long, but life is a little crazy these days :)

[mssimpso]

In D37355#886149, @dberlin wrote:

I see this review has been hanging around a while, so i'll take a stab at reviewing it.

(Random note: I know you didn't do this, but getOrInitValueState is very verbose for a thing that everything is probably going to use by default.
IMHO, the API should be getOrInitValueState is renamed to getValueState, getValueState is renamed to getExistingValueState.
Similarly with the other calls.

Since there are no other users, this may be a good time to change it in a followup)

Generally looks very very good. I don't think i have any algorithmic complaints here at all.
If you agree with the templating vs void ptrs, i'm happy to go commit that patch.

Thanks for the review! Yes, templating would be much nicer than void pointers. Feel free to go ahead with that, and I'll update this patch accordingly.

lib/Transforms/IPO/CalledValuePropagation.cpp

203 ↗

(On Diff #115443)

Yeah, that would be much nicer - the generic solver is old code. Thanks for working on the patch, and please feel free to go ahead and commit it. You should also update the comment at the top of AbstractLatticeFunction, since it talks about the void pointer. I can rebase my work on top of that.

206 ↗

(On Diff #115443)

Sounds good. If we template the lattice function, I don't think std::set will be needed anymore.

Because the values had to be void pointer's, I needed addresses of my custom values in order to interface with the generic solver. DenseSet couldn't be used because the values can move around in memory after they've been added to the set.

228 ↗

(On Diff #115443)

Thanks!

[mssimpso]

In D37355#886173, @davide wrote:

Generally I feel like it's getting there. Some small comments, but I expect this to be ready to be committed soon'ish

Thanks very much, Davide!

lib/Transforms/IPO/CalledValuePropagation.cpp

181–190 ↗

(On Diff #115443)

Thanks!

286 ↗

(On Diff #115443)

Yeah, we can use DenseSet if we template the lattice function and get rid of the void pointers.

lib/Transforms/IPO/PassManagerBuilder.cpp

717 ↗

(On Diff #115443)

Good idea.

[mssimpso]

Addressed comments from Danny and Davide.

• Regarding the DenseSet, I just removed the set all together. I was previously using the set to unique the lattice values in order to save space. But in the common case, the lattice values should be very small. So I don't think it's worth worrying about that.
• I also moved the uniquing and sorting of the functions vector from MergeValues to the lattice value constructor. I think this makes it more obvious that the container is set-like. Using a vector instead of set is handy for equality testing, which the lattice value is required to implement.

[• dberlin]

I'm a bit confused why you use a vector instead of std::set or DenseSet. It looks like either would be better in every way?

You say " Using a vector instead of set is handy for equality testing, which the lattice value is required to implement."

But i honestly don't get it :)

Other than that (and the associated changes to merge, etc. That could just use set_union), this looks reasonable to me.

[• dberlin]

Also, if you used sets, you could just use set.swap in the constructor (or move constructors) to avoid the extra copying.

[mssimpso]

Addressed Danny's comments.

• Changed the data structure for holding function pointers from SmallVector to std::set. I was probably over thinking this before, but you're right, a set makes more sense. I went with std::set over DenseSet for a few reasons. First, DenseSet doesn't work with std::inserter, which I used for std::set_union (see below). And second, std::set is ordered, so the functions will always appear in a deterministic order in the !callees metadata, which is useful for testing.
• Used std::set_union in MergeValues
• Changed CVPLatticeVal constructor to use the set move constructor to avoid unnecessary copying.

[davide]

This is good enough for me now (I was reviewing the version without std::set while you were updating it, but I think it's just a technical detail and I wouldn't hold off the review just for that).
LGTM but please to wait for Danny to sign off as well. Thank you for your work/patience!

[• dberlin]

thanks for working through this :)

[mssimpso]

Danny/Davide,

Thanks very much for all of the reviews! Just to clarify, are you also OK with the dependent patches (the changes in D37353 to make the generic solver interprocedural and the NFC in D37638 that pulls out the IPO utilities)?

[davide]

Yes, I'm fine with the dependent patches.
As this is a large-ish change (and involves a fair amount of refactoring), if I was you, I'd send a mail to llvm-dev to avoid surprises explaining what's your plan (so that if there are people relying on bits being in a particular position for their out-of-tree passes/analyses they at least have an heads-up of what's going on)

[mssimpso]

In D37355#892441, @davide wrote:

Yes, I'm fine with the dependent patches.
As this is a large-ish change (and involves a fair amount of refactoring), if I was you, I'd send a mail to llvm-dev to avoid surprises explaining what's your plan (so that if there are people relying on bits being in a particular position for their out-of-tree passes/analyses they at least have an heads-up of what's going on)

Yes, will do. Thanks, Davide. Danny has some remaining comments on the other patches that I'll take care of in the meantime.

[mssimpso]

I updated this patch following the most recent changes to the generic solver, which allow clients to define custom LatticeKeys. I'll email llvm-dev before committing.

llvm/trunk/include/llvm-c/Transforms/IPO.h

  */
 
 /** See llvm::createArgumentPromotionPass function. */
 void LLVMAddArgumentPromotionPass(LLVMPassManagerRef PM);
 
 /** See llvm::createConstantMergePass function. */
 void LLVMAddConstantMergePass(LLVMPassManagerRef PM);
 
+/** See llvm::createCalledValuePropagationPass function. */
+void LLVMAddCalledValuePropagationPass(LLVMPassManagerRef PM);
+
 /** See llvm::createDeadArgEliminationPass function. */
 void LLVMAddDeadArgEliminationPass(LLVMPassManagerRef PM);
 
 /** See llvm::createFunctionAttrsPass function. */
 void LLVMAddFunctionAttrsPass(LLVMPassManagerRef PM);
 
 /** See llvm::createFunctionInliningPass function. */
 void LLVMAddFunctionInliningPass(LLVMPassManagerRef PM);

llvm/trunk/include/llvm/InitializePasses.h

 void initializeCFLAndersAAWrapperPassPass(PassRegistry&);
 void initializeCFLSteensAAWrapperPassPass(PassRegistry&);
 void initializeCallGraphDOTPrinterPass(PassRegistry&);
 void initializeCallGraphPrinterLegacyPassPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry&);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantHoistingLegacyPassPass(PassRegistry&);
+void initializeCalledValuePropagationLegacyPassPass(PassRegistry &);
 void initializeConstantMergeLegacyPassPass(PassRegistry&);
 void initializeConstantPropagationPass(PassRegistry&);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCountingFunctionInserterPass(PassRegistry&);
 void initializeCrossDSOCFIPass(PassRegistry&);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);

llvm/trunk/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createCallGraphDOTPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
       (void) llvm::createLateCFGSimplificationPass();
       (void) llvm::createCFLAndersAAWrapperPass();
       (void) llvm::createCFLSteensAAWrapperPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createLibCallsShrinkWrapPass();
+      (void) llvm::createCalledValuePropagationPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
       (void) llvm::createCostModelAnalysisPass();
       (void) llvm::createDeadArgEliminationPass();
       (void) llvm::createDeadCodeEliminationPass();
       (void) llvm::createDeadInstEliminationPass();
       (void) llvm::createDeadStoreEliminationPass();
       (void) llvm::createDependenceAnalysisWrapperPass();

llvm/trunk/include/llvm/Transforms/IPO.h

 //
 ModulePass *createMetaRenamerPass();
 
 //===----------------------------------------------------------------------===//
 /// createBarrierNoopPass - This pass is purely a module pass barrier in a pass
 /// manager.
 ModulePass *createBarrierNoopPass();
 
+/// createCalledValuePropagationPass - Attach metadata to indirct call sites
+/// indicating the set of functions they may target at run-time.
+ModulePass *createCalledValuePropagationPass();
+
 /// What to do with the summary when running passes that operate on it.
 enum class PassSummaryAction {
   None,   ///< Do nothing.
   Import, ///< Import information from summary.
   Export, ///< Export information to summary.
 };
 
 /// \brief This pass lowers type metadata and the llvm.type.test intrinsic to

llvm/trunk/include/llvm/Transforms/IPO/CalledValuePropagation.h

+//===- CalledValuePropagation.h - Propagate called values -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a transformation that attaches !callees metadata to
+// indirect call sites. For a given call site, the metadata, if present,
+// indicates the set of functions the call site could possibly target at
+// run-time. This metadata is added to indirect call sites when the set of
+// possible targets can be determined by analysis and is known to be small. The
+// analysis driving the transformation is similar to constant propagation and
+// makes uses of the generic sparse propagation solver.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H
+#define LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H
+
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+class CalledValuePropagationPass
+    : public PassInfoMixin<CalledValuePropagationPass> {
+public:
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
+};
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_CALLEDVALUEPROPAGATION_H

llvm/trunk/lib/Passes/PassBuilder.cpp

 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/GCOVProfiler.h"
 #include "llvm/Transforms/IPO/AlwaysInliner.h"
 #include "llvm/Transforms/IPO/ArgumentPromotion.h"
+#include "llvm/Transforms/IPO/CalledValuePropagation.h"
 #include "llvm/Transforms/IPO/ConstantMerge.h"
 #include "llvm/Transforms/IPO/CrossDSOCFI.h"
 #include "llvm/Transforms/IPO/DeadArgumentElimination.h"
 #include "llvm/Transforms/IPO/ElimAvailExtern.h"
 #include "llvm/Transforms/IPO/ForceFunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 #include "llvm/Transforms/IPO/FunctionImport.h"
 #include "llvm/Transforms/IPO/GlobalDCE.h"
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
   }
 
   // Interprocedural constant propagation now that basic cleanup has occured
   // and prior to optimizing globals.
   // FIXME: This position in the pipeline hasn't been carefully considered in
   // years, it should be re-analyzed.
   MPM.addPass(IPSCCPPass());
 
+  // Attach metadata to indirect call sites indicating the set of functions
+  // they may target at run-time. This should follow IPSCCP.
+  MPM.addPass(CalledValuePropagationPass());
+
   // Optimize globals to try and fold them into constants.
   MPM.addPass(GlobalOptPass());
 
   // Promote any localized globals to SSA registers.
   // FIXME: Should this instead by a run of SROA?
   // FIXME: We should probably run instcombine and simplify-cfg afterward to
   // delete control flows that are dead once globals have been folded to
   // constants.
if (Level > 1) {
     // produce the same result as if we only do promotion here.
     MPM.addPass(PGOIndirectCallPromotion(
         true /* InLTO */, PGOOpt && !PGOOpt->SampleProfileFile.empty()));
 
     // Propagate constants at call sites into the functions they call.  This
     // opens opportunities for globalopt (and inlining) by substituting function
     // pointers passed as arguments to direct uses of functions.
    MPM.addPass(IPSCCPPass());
+
+   // Attach metadata to indirect call sites indicating the set of functions
+   // they may target at run-time. This should follow IPSCCP.
+   MPM.addPass(CalledValuePropagationPass());
   }
 
   // Now deduce any function attributes based in the current code.
   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(
               PostOrderFunctionAttrsPass()));
 
   // Do RPO function attribute inference across the module to forward-propagate
   // attributes where applicable.

llvm/trunk/lib/Passes/PassRegistry.def

 MODULE_ALIAS_ANALYSIS("globals-aa", GlobalsAA())
 #undef MODULE_ALIAS_ANALYSIS
 #undef MODULE_ANALYSIS
 
 #ifndef MODULE_PASS
 #define MODULE_PASS(NAME, CREATE_PASS)
 #endif
 MODULE_PASS("always-inline", AlwaysInlinerPass())
+MODULE_PASS("called-value-propagation", CalledValuePropagationPass())
 MODULE_PASS("constmerge", ConstantMergePass())
 MODULE_PASS("cross-dso-cfi", CrossDSOCFIPass())
 MODULE_PASS("deadargelim", DeadArgumentEliminationPass())
 MODULE_PASS("elim-avail-extern", EliminateAvailableExternallyPass())
 MODULE_PASS("forceattrs", ForceFunctionAttrsPass())
 MODULE_PASS("function-import", FunctionImportPass())
 MODULE_PASS("globaldce", GlobalDCEPass())
 MODULE_PASS("globalopt", GlobalOptPass())

llvm/trunk/lib/Transforms/IPO/CMakeLists.txt

 add_llvm_library(LLVMipo
   AlwaysInliner.cpp
   ArgumentPromotion.cpp
   BarrierNoopPass.cpp
+  CalledValuePropagation.cpp
   ConstantMerge.cpp
   CrossDSOCFI.cpp
   DeadArgumentElimination.cpp
   ElimAvailExtern.cpp
   ExtractGV.cpp
   ForceFunctionAttrs.cpp
   FunctionAttrs.cpp
   FunctionImport.cpp

llvm/trunk/lib/Transforms/IPO/CalledValuePropagation.cpp

+//===- CalledValuePropagation.cpp - Propagate called values -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a transformation that attaches !callees metadata to
+// indirect call sites. For a given call site, the metadata, if present,
+// indicates the set of functions the call site could possibly target at
+// run-time. This metadata is added to indirect call sites when the set of
+// possible targets can be determined by analysis and is known to be small. The
+// analysis driving the transformation is similar to constant propagation and
+// makes uses of the generic sparse propagation solver.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/CalledValuePropagation.h"
+#include "llvm/Analysis/SparsePropagation.h"
+#include "llvm/Analysis/ValueLatticeUtils.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/Transforms/IPO.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "called-value-propagation"
+
+/// The maximum number of functions to track per lattice value. Once the number
+/// of functions a call site can possibly target exceeds this threshold, it's
+/// lattice value becomes overdefined. The number of possible lattice values is
+/// bounded by Ch(F, M), where F is the number of functions in the module and M
+/// is MaxFunctionsPerValue. As such, this value should be kept very small. We
+/// likely can't do anything useful for call sites with a large number of
+/// possible targets, anyway.
+static cl::opt<unsigned> MaxFunctionsPerValue(
+    "cvp-max-functions-per-value", cl::Hidden, cl::init(4),
+    cl::desc("The maximum number of functions to track per lattice value"));
+
+namespace {
+/// To enable interprocedural analysis, we assign LLVM values to the following
+/// groups. The register group represents SSA registers, the return group
+/// represents the return values of functions, and the memory group represents
+/// in-memory values. An LLVM Value can technically be in more than one group.
+/// It's necessary to distinguish these groups so we can, for example, track a
+/// global variable separately from the value stored at its location.
+enum class IPOGrouping { Register, Return, Memory };
+
+/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
+using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
+
+/// The lattice value type used by our custom lattice function. It holds the
+/// lattice state, and a set of functions.
+class CVPLatticeVal {
+public:
+  /// The states of the lattice values. Only the FunctionSet state is
+  /// interesting. It indicates the set of functions to which an LLVM value may
+  /// refer.
+  enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };
+
+  /// Comparator for sorting the functions set. We want to keep the order
+  /// deterministic for testing, etc.
+  struct Compare {
+    bool operator()(const Function *LHS, const Function *RHS) const {
+      return LHS->getName() < RHS->getName();
+    }
+  };
+
+  CVPLatticeVal() : LatticeState(Undefined) {}
+  CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
+  CVPLatticeVal(std::set<Function *, Compare> &&Functions)
+      : LatticeState(FunctionSet), Functions(Functions) {}
+
+  /// Get a reference to the functions held by this lattice value. The number
+  /// of functions will be zero for states other than FunctionSet.
+  const std::set<Function *, Compare> &getFunctions() const {
+    return Functions;
+  }
+
+  /// Returns true if the lattice value is in the FunctionSet state.
+  bool isFunctionSet() const { return LatticeState == FunctionSet; }
+
+  bool operator==(const CVPLatticeVal &RHS) const {
+    return LatticeState == RHS.LatticeState && Functions == RHS.Functions;
+  }
+
+  bool operator!=(const CVPLatticeVal &RHS) const {
+    return LatticeState != RHS.LatticeState || Functions != RHS.Functions;
+  }
+
+private:
+  /// Holds the state this lattice value is in.
+  CVPLatticeStateTy LatticeState;
+
+  /// Holds functions indicating the possible targets of call sites. This set
+  /// is empty for lattice values in the undefined, overdefined, and untracked
+  /// states. The maximum size of the set is controlled by
+  /// MaxFunctionsPerValue. Since most LLVM values are expected to be in
+  /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be
+  /// small and efficiently copyable.
+  std::set<Function *, Compare> Functions;
+};
+
+/// The custom lattice function used by the generic sparse propagation solver.
+/// It handles merging lattice values and computing new lattice values for
+/// constants, arguments, values returned from trackable functions, and values
+/// located in trackable global variables. It also computes the lattice values
+/// that change as a result of executing instructions.
+class CVPLatticeFunc
+    : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {
+public:
+  CVPLatticeFunc()
+      : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined),
+                                CVPLatticeVal(CVPLatticeVal::Overdefined),
+                                CVPLatticeVal(CVPLatticeVal::Untracked)) {}
+
+  /// Compute and return a CVPLatticeVal for the given CVPLatticeKey.
+  CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {
+    switch (Key.getInt()) {
+    case IPOGrouping::Register:
+      if (isa<Instruction>(Key.getPointer())) {
+        return getUndefVal();
+      } else if (auto *A = dyn_cast<Argument>(Key.getPointer())) {
+        if (canTrackArgumentsInterprocedurally(A->getParent()))
+          return getUndefVal();
+      } else if (auto *C = dyn_cast<Constant>(Key.getPointer())) {
+        return computeConstant(C);
+      }
+      return getOverdefinedVal();
+    case IPOGrouping::Memory:
+    case IPOGrouping::Return:
+      if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) {
+        if (canTrackGlobalVariableInterprocedurally(GV))
+          return computeConstant(GV->getInitializer());
+      } else if (auto *F = cast<Function>(Key.getPointer()))
+        if (canTrackReturnsInterprocedurally(F))
+          return getUndefVal();
+    }
+    return getOverdefinedVal();
+  }
+
+  /// Merge the two given lattice values. The interesting cases are merging two
+  /// FunctionSet values and a FunctionSet value with an Undefined value. For
+  /// these cases, we simply union the function sets. If the size of the union
+  /// is greater than the maximum functions we track, the merged value is
+  /// overdefined.
+  CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {
+    if (X == getOverdefinedVal() || Y == getOverdefinedVal())
+      return getOverdefinedVal();
+    if (X == getUndefVal() && Y == getUndefVal())
+      return getUndefVal();
+    std::set<Function *, CVPLatticeVal::Compare> Union;
+    std::set_union(X.getFunctions().begin(), X.getFunctions().end(),
+                   Y.getFunctions().begin(), Y.getFunctions().end(),
+                   std::inserter(Union, Union.begin()));
+    if (Union.size() > MaxFunctionsPerValue)
+      return getOverdefinedVal();
+    return CVPLatticeVal(std::move(Union));
+  }
+
+  /// Compute the lattice values that change as a result of executing the given
+  /// instruction. The changed values are stored in \p ChangedValues. We handle
+  /// just a few kinds of instructions since we're only propagating values that
+  /// can be called.
+  void ComputeInstructionState(
+      Instruction &I, DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
+      SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) override {
+    switch (I.getOpcode()) {
+    case Instruction::Call:
+      return visitCallSite(cast<CallInst>(&I), ChangedValues, SS);
+    case Instruction::Invoke:
+      return visitCallSite(cast<InvokeInst>(&I), ChangedValues, SS);
+    case Instruction::Load:
+      return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);
+    case Instruction::Ret:
+      return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
+    case Instruction::Select:
+      return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);
+    case Instruction::Store:
+      return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
+    default:
+      return visitInst(I, ChangedValues, SS);
+    }
+  }
+
+  /// Print the given CVPLatticeVal to the specified stream.
+  void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override {
+    if (LV == getUndefVal())
+      OS << "Undefined  ";
+    else if (LV == getOverdefinedVal())
+      OS << "Overdefined";
+    else if (LV == getUntrackedVal())
+      OS << "Untracked  ";
+    else
+      OS << "FunctionSet";
+  }
+
+  /// Print the given CVPLatticeKey to the specified stream.
+  void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override {
+    if (Key.getInt() == IPOGrouping::Register)
+      OS << "<reg> ";
+    else if (Key.getInt() == IPOGrouping::Memory)
+      OS << "<mem> ";
+    else if (Key.getInt() == IPOGrouping::Return)
+      OS << "<ret> ";
+    if (isa<Function>(Key.getPointer()))
+      OS << Key.getPointer()->getName();
+    else
+      OS << *Key.getPointer();
+  }
+
+  /// We collect a set of indirect calls when visiting call sites. This method
+  /// returns a reference to that set.
+  SmallPtrSetImpl<Instruction *> &getIndirectCalls() { return IndirectCalls; }
+
+private:
+  /// Holds the indirect calls we encounter during the analysis. We will attach
+  /// metadata to these calls after the analysis indicating the functions the
+  /// calls can possibly target.
+  SmallPtrSet<Instruction *, 32> IndirectCalls;
+
+  /// Compute a new lattice value for the given constant. The constant, after
+  /// stripping any pointer casts, should be a Function. We ignore null
+  /// pointers as an optimization, since calling these values is undefined
+  /// behavior.
+  CVPLatticeVal computeConstant(Constant *C) {
+    if (isa<ConstantPointerNull>(C))
+      return CVPLatticeVal(CVPLatticeVal::FunctionSet);
+    if (auto *F = dyn_cast<Function>(C->stripPointerCasts()))
+      return CVPLatticeVal({F});
+    return getOverdefinedVal();
+  }
+
+  /// Handle return instructions. The function's return state is the merge of
+  /// the returned value state and the function's return state.
+  void visitReturn(ReturnInst &I,
+                   DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
+                   SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
+    Function *F = I.getParent()->getParent();
+    if (F->getReturnType()->isVoidTy())
+      return;
+    auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);
+    auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
+    ChangedValues[RetF] =
+        MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
+  }
+
+  /// Handle call sites. The state of a called function's formal arguments is
+  /// the merge of the argument state with the call sites corresponding actual
+  /// argument state. The call site state is the merge of the call site state
+  /// with the returned value state of the called function.
+  void visitCallSite(CallSite CS,
+                     DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
+                     SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
+    Function *F = CS.getCalledFunction();
+    Instruction *I = CS.getInstruction();
+    auto RegI = CVPLatticeKey(I, IPOGrouping::Register);
+
+    // If this is an indirect call, save it so we can quickly revisit it when
+    // attaching metadata.
+    if (!F)
+      IndirectCalls.insert(I);
+
+    // If we can't track the function's return values, there's nothing to do.
+    if (!F || !canTrackReturnsInterprocedurally(F)) {
+      ChangedValues[RegI] = getOverdefinedVal();
+      return;
+    }
+
+    // Inform the solver that the called function is executable, and perform
+    // the merges for the arguments and return value.
+    SS.MarkBlockExecutable(&F->front());
+    auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
+    for (Argument &A : F->args()) {
+      auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);
+      auto RegActual =
+          CVPLatticeKey(CS.getArgument(A.getArgNo()), IPOGrouping::Register);
+      ChangedValues[RegFormal] =
+          MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
+    }
+    ChangedValues[RegI] =
+        MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
+  }
+
+  /// Handle select instructions. The select instruction state is the merge the
+  /// true and false value states.
+  void visitSelect(SelectInst &I,
+                   DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
+                   SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
+    auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
+    auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);
+    auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);
+    ChangedValues[RegI] =
+        MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));
+  }
+
+  /// Handle load instructions. If the pointer operand of the load is a global
+  /// variable, we attempt to track the value. The loaded value state is the
+  /// merge of the loaded value state with the global variable state.
+  void visitLoad(LoadInst &I,
+                 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
+                 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
+    auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
+    if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) {
+      auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
+      ChangedValues[RegI] =
+          MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
+    } else {
+      ChangedValues[RegI] = getOverdefinedVal();
+    }
+  }
+
+  /// Handle store instructions. If the pointer operand of the store is a
+  /// global variable, we attempt to track the value. The global variable state
+  /// is the merge of the stored value state with the global variable state.
+  void visitStore(StoreInst &I,
+                  DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
+                  SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
+    auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
+    if (!GV)
+      return;
+    auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);
+    auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
+    ChangedValues[MemGV] =
+        MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
+  }
+
+  /// Handle all other instructions. All other instructions are marked
+  /// overdefined.
+  void visitInst(Instruction &I,
+                 DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
+                 SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
+    auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
+    ChangedValues[RegI] = getOverdefinedVal();
+  }
+};
+} // namespace
+
+namespace llvm {
+/// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver
+/// must translate between LatticeKeys and LLVM Values when adding Values to
+/// its work list and inspecting the state of control-flow related values.
+template <> struct LatticeKeyInfo<CVPLatticeKey> {
+  static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {
+    return Key.getPointer();
+  }
+  static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {
+    return CVPLatticeKey(V, IPOGrouping::Register);
+  }
+};
+} // namespace llvm
+
+static bool runCVP(Module &M) {
+  // Our custom lattice function and generic sparse propagation solver.
+  CVPLatticeFunc Lattice;
+  SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice);
+
+  // For each function in the module, if we can't track its arguments, let the
+  // generic solver assume it is executable.
+  for (Function &F : M)
+    if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F))
+      Solver.MarkBlockExecutable(&F.front());
+
+  // Solver our custom lattice. In doing so, we will also build a set of
+  // indirect call sites.
+  Solver.Solve();
+
+  // Attach metadata to the indirect call sites that were collected indicating
+  // the set of functions they can possibly target.
+  bool Changed = false;
+  MDBuilder MDB(M.getContext());
+  for (Instruction *C : Lattice.getIndirectCalls()) {
+    CallSite CS(C);
+    auto RegI = CVPLatticeKey(CS.getCalledValue(), IPOGrouping::Register);
+    CVPLatticeVal LV = Solver.getExistingValueState(RegI);
+    if (!LV.isFunctionSet() || LV.getFunctions().empty())
+      continue;
+    MDNode *Callees = MDB.createCallees(SmallVector<Function *, 4>(
+        LV.getFunctions().begin(), LV.getFunctions().end()));
+    C->setMetadata(LLVMContext::MD_callees, Callees);
+    Changed = true;
+  }
+
+  return Changed;
+}
+
+PreservedAnalyses CalledValuePropagationPass::run(Module &M,
+                                                  ModuleAnalysisManager &) {
+  runCVP(M);
+  return PreservedAnalyses::all();
+}
+
+namespace {
+class CalledValuePropagationLegacyPass : public ModulePass {
+public:
+  static char ID;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+
+  CalledValuePropagationLegacyPass() : ModulePass(ID) {
+    initializeCalledValuePropagationLegacyPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  bool runOnModule(Module &M) override {
+    if (skipModule(M))
+      return false;
+    return runCVP(M);
+  }
+};
+} // namespace
+
+char CalledValuePropagationLegacyPass::ID = 0;
+INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation",
+                "Called Value Propagation", false, false)
+
+ModulePass *llvm::createCalledValuePropagationPass() {
+  return new CalledValuePropagationLegacyPass();
+}

llvm/trunk/lib/Transforms/IPO/IPO.cpp

 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/AlwaysInliner.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 
 using namespace llvm;
 
 void llvm::initializeIPO(PassRegistry &Registry) {
   initializeArgPromotionPass(Registry);
+  initializeCalledValuePropagationLegacyPassPass(Registry);
   initializeConstantMergeLegacyPassPass(Registry);
   initializeCrossDSOCFIPass(Registry);
   initializeDAEPass(Registry);
   initializeDAHPass(Registry);
   initializeForceFunctionAttrsLegacyPassPass(Registry);
   initializeGlobalDCELegacyPassPass(Registry);
   initializeGlobalOptLegacyPassPass(Registry);
   initializeGlobalSplitPass(Registry);

 void LLVMInitializeIPO(LLVMPassRegistryRef R) {
   initializeIPO(*unwrap(R));
 }
 
 void LLVMAddArgumentPromotionPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createArgumentPromotionPass());
 }
 
+void LLVMAddCalledValuePropagationPass(LLVMPassManagerRef PM) {
+  unwrap(PM)->add(createCalledValuePropagationPass());
+}
+
 void LLVMAddConstantMergePass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createConstantMergePass());
 }
 
 void LLVMAddDeadArgEliminationPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createDeadArgEliminationPass());
 }
 

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

if (PrepareForThinLTOUsingPGOSampleProfile)
     DisableUnrollLoops = true;
 
   // Infer attributes about declarations if possible.
   MPM.add(createInferFunctionAttrsLegacyPass());
 
   addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
 
   MPM.add(createIPSCCPPass());          // IP SCCP
+  MPM.add(createCalledValuePropagationPass());
   MPM.add(createGlobalOptimizerPass()); // Optimize out global vars
   // Promote any localized global vars.
   MPM.add(createPromoteMemoryToRegisterPass());
 
   MPM.add(createDeadArgEliminationPass()); // Dead argument elimination
 
   addInstructionCombiningPass(MPM); // Clean up after IPCP & DAE
   addExtensionsToPM(EP_Peephole, MPM);
if (OptLevel > 1) {
     // produce the same result as if we only do promotion here.
     PM.add(
         createPGOIndirectCallPromotionLegacyPass(true, !PGOSampleUse.empty()));
 
     // Propagate constants at call sites into the functions they call.  This
     // opens opportunities for globalopt (and inlining) by substituting function
     // pointers passed as arguments to direct uses of functions.
     PM.add(createIPSCCPPass());
+
+    // Attach metadata to indirect call sites indicating the set of functions
+    // they may target at run-time. This should follow IPSCCP.
+    PM.add(createCalledValuePropagationPass());
   }
 
   // Infer attributes about definitions. The readnone attribute in particular is
   // required for virtual constant propagation.
   PM.add(createPostOrderFunctionAttrsLegacyPass());
   PM.add(createReversePostOrderFunctionAttrsPass());
 
   // Split globals using inrange annotations on GEP indices. This can help

llvm/trunk/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
+; CHECK-O-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: GlobalOptPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O-NEXT: Running pass: DeadArgumentEliminationPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-O-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-EP-PEEPHOLE-NEXT: Running pass: NoOpFunctionPass

llvm/trunk/test/Other/new-pm-lto-defaults.ll

 ; CHECK-O-NEXT: Running pass: ForceFunctionAttrsPass
 ; CHECK-O-NEXT: Running pass: InferFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O2-NEXT: PGOIndirectCallPromotion
 ; CHECK-O2-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O2-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Function
 ; CHECK-O2-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-O2-NEXT: Running pass: IPSCCPPass
+; CHECK-O2-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}PostOrderFunctionAttrsPass>
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}SCC
 ; CHECK-O1-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}Function
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>
 ; CHECK-O-NEXT: Running analysis: AAManager
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis

llvm/trunk/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running analysis: DominatorTreeAnalysis
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-O-NEXT: Running pass: LowerExpectIntrinsicPass
 ; CHECK-O-NEXT: Finished llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: IPSCCPPass
+; CHECK-O-NEXT: Running pass: CalledValuePropagationPass
 ; CHECK-O-NEXT: Running pass: GlobalOptPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PromotePass>
 ; CHECK-O-NEXT: Running pass: DeadArgumentEliminationPass
 ; CHECK-O-NEXT: Running pass: ModuleToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: InstCombinePass
 ; CHECK-PRELINK-O-NEXT: Running analysis: OptimizationRemarkEmitterAnalysis
 ; CHECK-O-NEXT: Running pass: SimplifyCFGPass

llvm/trunk/test/Transforms/CalledValuePropagation/simple-arguments.ll

+; RUN: opt -called-value-propagation -S < %s | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnueabi"
+
+
+; This test checks that we propagate the functions through arguments and attach
+; !callees metadata to the call. Such metadata can enable optimizations of this
+; code sequence.
+;
+; For example, the code below a illustrates a contrived sort-like algorithm
+; that accepts a pointer to a comparison function. Since the indirect call to
+; the comparison function has only two targets, the call can be promoted to two
+; direct calls using an if-then-else. The loop can then be unswitched and the
+; called functions inlined. This essentially produces two loops, once
+; specialized for each comparison.
+;
+; CHECK:  %tmp3 = call i1 %cmp(i64* %tmp1, i64* %tmp2), !callees ![[MD:[0-9]+]]
+; CHECK: ![[MD]] = !{i1 (i64*, i64*)* @ugt, i1 (i64*, i64*)* @ule}
+;
+define void @test_argument(i64* %x, i64 %n, i1 %flag) {
+entry:
+  %tmp0 = sub i64 %n, 1
+  br i1 %flag, label %then, label %else
+
+then:
+  call void @arrange_data(i64* %x, i64 %tmp0, i1 (i64*, i64*)* @ugt)
+  br label %merge
+
+else:
+  call void @arrange_data(i64* %x, i64 %tmp0, i1 (i64*, i64*)* @ule)
+  br label %merge
+
+merge:
+  ret void
+}
+
+define internal void @arrange_data(i64* %x, i64 %n, i1 (i64*, i64*)* %cmp) {
+entry:
+  %tmp0 = icmp eq i64 %n, 1
+  br i1 %tmp0, label %merge, label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %cmp.false ]
+  %i.next = add nuw nsw i64 %i, 1
+  %tmp1 = getelementptr inbounds i64, i64* %x, i64 %i
+  %tmp2 = getelementptr inbounds i64, i64* %x, i64 %i.next
+  %tmp3 = call i1 %cmp(i64* %tmp1, i64* %tmp2)
+  br i1 %tmp3, label %cmp.true, label %cmp.false
+
+cmp.true:
+  call void @swap(i64* %tmp1, i64* %tmp2)
+  br label %cmp.false
+
+cmp.false:
+  %cond = icmp slt i64 %i.next, %n
+  br i1 %cond, label %for.body, label %for.end
+
+for.end:
+  %tmp4 = sub i64 %n, 1
+  call void @arrange_data(i64* %x, i64 %tmp4, i1 (i64*, i64*)* %cmp)
+  br label %merge
+
+merge:
+  ret void
+}
+
+define internal i1 @ugt(i64* %a, i64* %b) {
+entry:
+  %tmp0 = load i64, i64* %a
+  %tmp1 = load i64, i64* %b
+  %tmp2 = icmp ugt i64 %tmp0, %tmp1
+  ret i1 %tmp2
+}
+
+define internal i1 @ule(i64* %a, i64* %b) {
+entry:
+  %tmp0 = load i64, i64* %a
+  %tmp1 = load i64, i64* %b
+  %tmp2 = icmp ule i64 %tmp0, %tmp1
+  ret i1 %tmp2
+}
+
+declare void @swap(i64*, i64*)

llvm/trunk/test/Transforms/CalledValuePropagation/simple-memory.ll

+; RUN: opt -called-value-propagation -S < %s | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnueabi"
+
+@global_function = internal unnamed_addr global void ()* null, align 8
+@global_array = common unnamed_addr global i64* null, align 8
+
+; This test checks that we propagate the functions through an internal global
+; variable, and attach !callees metadata to the call. Such metadata can enable
+; optimizations of this code sequence.
+;
+; For example, since both of the targeted functions have the "nounwind" and
+; "readnone" function attributes, LICM can be made to move the call and the
+; function pointer load outside the loop. This would then enable the loop
+; vectorizer to vectorize the sum reduction.
+;
+; CHECK: call void %tmp0(), !callees ![[MD:[0-9]+]]
+; CHECK: ![[MD]] = !{void ()* @invariant_1, void ()* @invariant_2}
+;
+define i64 @test_memory_entry(i64 %n, i1 %flag) {
+entry:
+  br i1 %flag, label %then, label %else
+
+then:
+  store void ()* @invariant_1, void ()** @global_function
+  br label %merge
+
+else:
+  store void ()* @invariant_2, void ()** @global_function
+  br label %merge
+
+merge:
+  %tmp1 = call i64 @test_memory(i64 %n)
+  ret i64 %tmp1
+}
+
+define internal i64 @test_memory(i64 %n) {
+entry:
+  %array = load i64*, i64** @global_array
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+  %r = phi i64 [ 0, %entry ], [ %tmp3, %for.body ]
+  %tmp0 = load void ()*, void ()** @global_function
+  call void %tmp0()
+  %tmp1 = getelementptr inbounds i64, i64* %array, i64 %i
+  %tmp2 = load i64, i64* %tmp1
+  %tmp3 = add i64 %tmp2, %r
+  %i.next = add nuw nsw i64 %i, 1
+  %cond = icmp slt i64 %i.next, %n
+  br i1 %cond, label %for.body, label %for.end
+
+for.end:
+  %tmp4 = phi i64 [ %tmp3, %for.body ]
+  ret i64 %tmp4
+}
+
+declare void @invariant_1() #0
+declare void @invariant_2() #0
+
+attributes #0 = { nounwind readnone }

llvm/trunk/test/Transforms/CalledValuePropagation/simple-select.ll

+; RUN: opt -called-value-propagation -S < %s | FileCheck %s
+
+target triple = "aarch64-unknown-linux-gnueabi"
+
+@global_function = internal unnamed_addr global void ()* null, align 8
+@global_scalar = internal unnamed_addr global i64 zeroinitializer
+
+; This test checks that we propagate the functions through a select
+; instruction, and attach !callees metadata to the call. Such metadata can
+; enable optimizations of this code sequence.
+;
+; For example, since both of the targeted functions have the "norecurse"
+; attribute, the function attributes pass can be made to infer that
+; "@test_select" is also norecurse. This would allow the globals optimizer to
+; localize "@global_scalar". The function could then be further simplified to
+; always return the constant "1", eliminating the load and store instructions.
+;
+; CHECK: call void %tmp0(), !callees ![[MD:[0-9]+]]
+; CHECK: ![[MD]] = !{void ()* @norecurse_1, void ()* @norecurse_2}
+;
+define i64 @test_select_entry(i1 %flag) {
+entry:
+  %tmp0 = call i64 @test_select(i1 %flag)
+  ret i64 %tmp0
+}
+
+define internal i64 @test_select(i1 %flag) {
+entry:
+  %tmp0 = select i1 %flag, void ()* @norecurse_1, void ()* @norecurse_2
+  store i64 1, i64* @global_scalar
+  call void %tmp0()
+  %tmp1 = load i64, i64* @global_scalar
+  ret i64 %tmp1
+}
+
+declare void @norecurse_1() #0
+declare void @norecurse_2() #0
+
+attributes #0 = { norecurse }