Index: llvm/trunk/bindings/python/llvm/core.py
===================================================================
--- llvm/trunk/bindings/python/llvm/core.py
+++ llvm/trunk/bindings/python/llvm/core.py
@@ -465,9 +465,6 @@
     library.LLVMInitializeAnalysis.argtypes = [PassRegistry]
     library.LLVMInitializeAnalysis.restype = None
 
-    library.LLVMInitializeIPA.argtypes = [PassRegistry]
-    library.LLVMInitializeIPA.restype = None
-
     library.LLVMInitializeCodeGen.argtypes = [PassRegistry]
     library.LLVMInitializeCodeGen.restype = None
 
@@ -621,7 +618,6 @@
     lib.LLVMInitializeIPO(p)
     lib.LLVMInitializeInstrumentation(p)
     lib.LLVMInitializeAnalysis(p)
-    lib.LLVMInitializeIPA(p)
     lib.LLVMInitializeCodeGen(p)
     lib.LLVMInitializeTarget(p)
 
Index: llvm/trunk/include/llvm/InitializePasses.h
===================================================================
--- llvm/trunk/include/llvm/InitializePasses.h
+++ llvm/trunk/include/llvm/InitializePasses.h
@@ -53,9 +53,6 @@
 /// initializeAnalysis - Initialize all passes linked into the Analysis library.
 void initializeAnalysis(PassRegistry&);
 
-/// initializeIPA - Initialize all passes linked into the IPA library.
-void initializeIPA(PassRegistry&);
-
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void initializeCodeGen(PassRegistry&);
 
Index: llvm/trunk/lib/Analysis/Analysis.cpp
===================================================================
--- llvm/trunk/lib/Analysis/Analysis.cpp
+++ llvm/trunk/lib/Analysis/Analysis.cpp
@@ -28,6 +28,9 @@
   initializeBasicAliasAnalysisPass(Registry);
   initializeBlockFrequencyInfoWrapperPassPass(Registry);
   initializeBranchProbabilityInfoWrapperPassPass(Registry);
+  initializeCallGraphWrapperPassPass(Registry);
+  initializeCallGraphPrinterPass(Registry);
+  initializeCallGraphViewerPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerPass(Registry);
   initializeCFGPrinterPass(Registry);
@@ -47,6 +50,7 @@
   initializePostDomPrinterPass(Registry);
   initializePostDomOnlyViewerPass(Registry);
   initializePostDomOnlyPrinterPass(Registry);
+  initializeGlobalsModRefPass(Registry);
   initializeIVUsersPass(Registry);
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
@@ -74,6 +78,10 @@
   initializeAnalysis(*unwrap(R));
 }
 
+void LLVMInitializeIPA(LLVMPassRegistryRef R) {
+  initializeAnalysis(*unwrap(R));
+}
+
 LLVMBool LLVMVerifyModule(LLVMModuleRef M, LLVMVerifierFailureAction Action,
                           char **OutMessages) {
   raw_ostream *DebugOS = Action != LLVMReturnStatusAction ? &errs() : nullptr;
Index: llvm/trunk/lib/Analysis/CMakeLists.txt
===================================================================
--- llvm/trunk/lib/Analysis/CMakeLists.txt
+++ llvm/trunk/lib/Analysis/CMakeLists.txt
@@ -13,6 +13,9 @@
   CFGPrinter.cpp
   CFLAliasAnalysis.cpp
   CGSCCPassManager.cpp
+  CallGraph.cpp
+  CallGraphSCCPass.cpp
+  CallPrinter.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
@@ -23,7 +26,9 @@
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
+  GlobalsModRef.cpp
   IVUsers.cpp
+  InlineCost.cpp
   InstCount.cpp
   InstructionSimplify.cpp
   Interval.cpp
@@ -69,5 +74,3 @@
   )
 
 add_dependencies(LLVMAnalysis intrinsics_gen)
-
-add_subdirectory(IPA)
Index: llvm/trunk/lib/Analysis/CallGraph.cpp
===================================================================
--- llvm/trunk/lib/Analysis/CallGraph.cpp
+++ llvm/trunk/lib/Analysis/CallGraph.cpp
@@ -0,0 +1,309 @@
+//===- CallGraph.cpp - Build a Module's call graph ------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraph class methods.
+//
+
+CallGraph::CallGraph(Module &M)
+    : M(M), Root(nullptr), ExternalCallingNode(getOrInsertFunction(nullptr)),
+      CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
+  // Add every function to the call graph.
+  for (Function &F : M)
+    addToCallGraph(&F);
+
+  // If we didn't find a main function, use the external call graph node
+  if (!Root)
+    Root = ExternalCallingNode;
+}
+
+CallGraph::CallGraph(CallGraph &&Arg)
+    : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)), Root(Arg.Root),
+      ExternalCallingNode(Arg.ExternalCallingNode),
+      CallsExternalNode(std::move(Arg.CallsExternalNode)) {
+  Arg.FunctionMap.clear();
+  Arg.Root = nullptr;
+  Arg.ExternalCallingNode = nullptr;
+}
+
+CallGraph::~CallGraph() {
+  // CallsExternalNode is not in the function map, delete it explicitly.
+  if (CallsExternalNode)
+    CallsExternalNode->allReferencesDropped();
+
+// Reset all node's use counts to zero before deleting them to prevent an
+// assertion from firing.
+#ifndef NDEBUG
+  for (auto &I : FunctionMap)
+    I.second->allReferencesDropped();
+#endif
+}
+
+void CallGraph::addToCallGraph(Function *F) {
+  CallGraphNode *Node = getOrInsertFunction(F);
+
+  // If this function has external linkage, anything could call it.
+  if (!F->hasLocalLinkage()) {
+    ExternalCallingNode->addCalledFunction(CallSite(), Node);
+
+    // Found the entry point?
+    if (F->getName() == "main") {
+      if (Root) // Found multiple external mains?  Don't pick one.
+        Root = ExternalCallingNode;
+      else
+        Root = Node; // Found a main, keep track of it!
+    }
+  }
+
+  // If this function has its address taken, anything could call it.
+  if (F->hasAddressTaken())
+    ExternalCallingNode->addCalledFunction(CallSite(), Node);
+
+  // If this function is not defined in this translation unit, it could call
+  // anything.
+  if (F->isDeclaration() && !F->isIntrinsic())
+    Node->addCalledFunction(CallSite(), CallsExternalNode.get());
+
+  // Look for calls by this function.
+  for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
+    for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;
+         ++II) {
+      CallSite CS(cast<Value>(II));
+      if (CS) {
+        const Function *Callee = CS.getCalledFunction();
+        if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
+          // Indirect calls of intrinsics are not allowed so no need to check.
+          // We can be more precise here by using TargetArg returned by
+          // Intrinsic::isLeaf.
+          Node->addCalledFunction(CS, CallsExternalNode.get());
+        else if (!Callee->isIntrinsic())
+          Node->addCalledFunction(CS, getOrInsertFunction(Callee));
+      }
+    }
+}
+
+void CallGraph::print(raw_ostream &OS) const {
+  OS << "CallGraph Root is: ";
+  if (Function *F = Root->getFunction())
+    OS << F->getName() << "\n";
+  else {
+    OS << "<<null function: 0x" << Root << ">>\n";
+  }
+
+  // Print in a deterministic order by sorting CallGraphNodes by name.  We do
+  // this here to avoid slowing down the non-printing fast path.
+
+  SmallVector<CallGraphNode *, 16> Nodes;
+  Nodes.reserve(FunctionMap.size());
+
+  for (auto I = begin(), E = end(); I != E; ++I)
+    Nodes.push_back(I->second.get());
+
+  std::sort(Nodes.begin(), Nodes.end(),
+            [](CallGraphNode *LHS, CallGraphNode *RHS) {
+    if (Function *LF = LHS->getFunction())
+      if (Function *RF = RHS->getFunction())
+        return LF->getName() < RF->getName();
+
+    return RHS->getFunction() != nullptr;
+  });
+
+  for (CallGraphNode *CN : Nodes)
+    CN->print(OS);
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void CallGraph::dump() const { print(dbgs()); }
+#endif
+
+// removeFunctionFromModule - Unlink the function from this module, returning
+// it.  Because this removes the function from the module, the call graph node
+// is destroyed.  This is only valid if the function does not call any other
+// functions (ie, there are no edges in it's CGN).  The easiest way to do this
+// is to dropAllReferences before calling this.
+//
+Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
+  assert(CGN->empty() && "Cannot remove function from call "
+         "graph if it references other functions!");
+  Function *F = CGN->getFunction(); // Get the function for the call graph node
+  FunctionMap.erase(F);             // Remove the call graph node from the map
+
+  M.getFunctionList().remove(F);
+  return F;
+}
+
+/// spliceFunction - Replace the function represented by this node by another.
+/// This does not rescan the body of the function, so it is suitable when
+/// splicing the body of the old function to the new while also updating all
+/// callers from old to new.
+///
+void CallGraph::spliceFunction(const Function *From, const Function *To) {
+  assert(FunctionMap.count(From) && "No CallGraphNode for function!");
+  assert(!FunctionMap.count(To) &&
+         "Pointing CallGraphNode at a function that already exists");
+  FunctionMapTy::iterator I = FunctionMap.find(From);
+  I->second->F = const_cast<Function*>(To);
+  FunctionMap[To] = std::move(I->second);
+  FunctionMap.erase(I);
+}
+
+// getOrInsertFunction - This method is identical to calling operator[], but
+// it will insert a new CallGraphNode for the specified function if one does
+// not already exist.
+CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
+  auto &CGN = FunctionMap[F];
+  if (CGN)
+    return CGN.get();
+
+  assert((!F || F->getParent() == &M) && "Function not in current module!");
+  CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
+  return CGN.get();
+}
+
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraphNode class methods.
+//
+
+void CallGraphNode::print(raw_ostream &OS) const {
+  if (Function *F = getFunction())
+    OS << "Call graph node for function: '" << F->getName() << "'";
+  else
+    OS << "Call graph node <<null function>>";
+  
+  OS << "<<" << this << ">>  #uses=" << getNumReferences() << '\n';
+
+  for (const_iterator I = begin(), E = end(); I != E; ++I) {
+    OS << "  CS<" << I->first << "> calls ";
+    if (Function *FI = I->second->getFunction())
+      OS << "function '" << FI->getName() <<"'\n";
+    else
+      OS << "external node\n";
+  }
+  OS << '\n';
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void CallGraphNode::dump() const { print(dbgs()); }
+#endif
+
+/// removeCallEdgeFor - This method removes the edge in the node for the
+/// specified call site.  Note that this method takes linear time, so it
+/// should be used sparingly.
+void CallGraphNode::removeCallEdgeFor(CallSite CS) {
+  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
+    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
+    if (I->first == CS.getInstruction()) {
+      I->second->DropRef();
+      *I = CalledFunctions.back();
+      CalledFunctions.pop_back();
+      return;
+    }
+  }
+}
+
+// removeAnyCallEdgeTo - This method removes any call edges from this node to
+// the specified callee function.  This takes more time to execute than
+// removeCallEdgeTo, so it should not be used unless necessary.
+void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
+  for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
+    if (CalledFunctions[i].second == Callee) {
+      Callee->DropRef();
+      CalledFunctions[i] = CalledFunctions.back();
+      CalledFunctions.pop_back();
+      --i; --e;
+    }
+}
+
+/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
+/// from this node to the specified callee function.
+void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
+  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
+    assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
+    CallRecord &CR = *I;
+    if (CR.second == Callee && CR.first == nullptr) {
+      Callee->DropRef();
+      *I = CalledFunctions.back();
+      CalledFunctions.pop_back();
+      return;
+    }
+  }
+}
+
+/// replaceCallEdge - This method replaces the edge in the node for the
+/// specified call site with a new one.  Note that this method takes linear
+/// time, so it should be used sparingly.
+void CallGraphNode::replaceCallEdge(CallSite CS,
+                                    CallSite NewCS, CallGraphNode *NewNode){
+  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
+    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
+    if (I->first == CS.getInstruction()) {
+      I->second->DropRef();
+      I->first = NewCS.getInstruction();
+      I->second = NewNode;
+      NewNode->AddRef();
+      return;
+    }
+  }
+}
+
+//===----------------------------------------------------------------------===//
+// Out-of-line definitions of CallGraphAnalysis class members.
+//
+
+char CallGraphAnalysis::PassID;
+
+//===----------------------------------------------------------------------===//
+// Implementations of the CallGraphWrapperPass class methods.
+//
+
+CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
+  initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
+CallGraphWrapperPass::~CallGraphWrapperPass() {}
+
+void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+}
+
+bool CallGraphWrapperPass::runOnModule(Module &M) {
+  // All the real work is done in the constructor for the CallGraph.
+  G.reset(new CallGraph(M));
+  return false;
+}
+
+INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
+                false, true)
+
+char CallGraphWrapperPass::ID = 0;
+
+void CallGraphWrapperPass::releaseMemory() { G.reset(); }
+
+void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
+  if (!G) {
+    OS << "No call graph has been built!\n";
+    return;
+  }
+
+  // Just delegate.
+  G->print(OS);
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
+#endif
Index: llvm/trunk/lib/Analysis/CallGraphSCCPass.cpp
===================================================================
--- llvm/trunk/lib/Analysis/CallGraphSCCPass.cpp
+++ llvm/trunk/lib/Analysis/CallGraphSCCPass.cpp
@@ -0,0 +1,632 @@
+//===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the CallGraphSCCPass class, which is used for passes
+// which are implemented as bottom-up traversals on the call graph.  Because
+// there may be cycles in the call graph, passes of this type operate on the
+// call-graph in SCC order: that is, they process function bottom-up, except for
+// recursive functions, which they process all at once.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/LegacyPassManagers.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Timer.h"
+#include "llvm/Support/raw_ostream.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "cgscc-passmgr"
+
+static cl::opt<unsigned> 
+MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
+
+STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
+
+//===----------------------------------------------------------------------===//
+// CGPassManager
+//
+/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
+
+namespace {
+
+class CGPassManager : public ModulePass, public PMDataManager {
+public:
+  static char ID;
+  explicit CGPassManager() 
+    : ModulePass(ID), PMDataManager() { }
+
+  /// Execute all of the passes scheduled for execution.  Keep track of
+  /// whether any of the passes modifies the module, and if so, return true.
+  bool runOnModule(Module &M) override;
+
+  using ModulePass::doInitialization;
+  using ModulePass::doFinalization;
+
+  bool doInitialization(CallGraph &CG);
+  bool doFinalization(CallGraph &CG);
+
+  /// Pass Manager itself does not invalidate any analysis info.
+  void getAnalysisUsage(AnalysisUsage &Info) const override {
+    // CGPassManager walks SCC and it needs CallGraph.
+    Info.addRequired<CallGraphWrapperPass>();
+    Info.setPreservesAll();
+  }
+
+  const char *getPassName() const override {
+    return "CallGraph Pass Manager";
+  }
+
+  PMDataManager *getAsPMDataManager() override { return this; }
+  Pass *getAsPass() override { return this; }
+
+  // Print passes managed by this manager
+  void dumpPassStructure(unsigned Offset) override {
+    errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
+    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
+      Pass *P = getContainedPass(Index);
+      P->dumpPassStructure(Offset + 1);
+      dumpLastUses(P, Offset+1);
+    }
+  }
+
+  Pass *getContainedPass(unsigned N) {
+    assert(N < PassVector.size() && "Pass number out of range!");
+    return static_cast<Pass *>(PassVector[N]);
+  }
+
+  PassManagerType getPassManagerType() const override {
+    return PMT_CallGraphPassManager; 
+  }
+  
+private:
+  bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
+                         bool &DevirtualizedCall);
+  
+  bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
+                    CallGraph &CG, bool &CallGraphUpToDate,
+                    bool &DevirtualizedCall);
+  bool RefreshCallGraph(CallGraphSCC &CurSCC, CallGraph &CG,
+                        bool IsCheckingMode);
+};
+
+} // end anonymous namespace.
+
+char CGPassManager::ID = 0;
+
+
+bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
+                                 CallGraph &CG, bool &CallGraphUpToDate,
+                                 bool &DevirtualizedCall) {
+  bool Changed = false;
+  PMDataManager *PM = P->getAsPMDataManager();
+
+  if (!PM) {
+    CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P;
+    if (!CallGraphUpToDate) {
+      DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
+      CallGraphUpToDate = true;
+    }
+
+    {
+      TimeRegion PassTimer(getPassTimer(CGSP));
+      Changed = CGSP->runOnSCC(CurSCC);
+    }
+    
+    // After the CGSCCPass is done, when assertions are enabled, use
+    // RefreshCallGraph to verify that the callgraph was correctly updated.
+#ifndef NDEBUG
+    if (Changed)
+      RefreshCallGraph(CurSCC, CG, true);
+#endif
+    
+    return Changed;
+  }
+  
+  
+  assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
+         "Invalid CGPassManager member");
+  FPPassManager *FPP = (FPPassManager*)P;
+  
+  // Run pass P on all functions in the current SCC.
+  for (CallGraphNode *CGN : CurSCC) {
+    if (Function *F = CGN->getFunction()) {
+      dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
+      {
+        TimeRegion PassTimer(getPassTimer(FPP));
+        Changed |= FPP->runOnFunction(*F);
+      }
+      F->getContext().yield();
+    }
+  }
+  
+  // The function pass(es) modified the IR, they may have clobbered the
+  // callgraph.
+  if (Changed && CallGraphUpToDate) {
+    DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
+                 << P->getPassName() << '\n');
+    CallGraphUpToDate = false;
+  }
+  return Changed;
+}
+
+
+/// Scan the functions in the specified CFG and resync the
+/// callgraph with the call sites found in it.  This is used after
+/// FunctionPasses have potentially munged the callgraph, and can be used after
+/// CallGraphSCC passes to verify that they correctly updated the callgraph.
+///
+/// This function returns true if it devirtualized an existing function call,
+/// meaning it turned an indirect call into a direct call.  This happens when
+/// a function pass like GVN optimizes away stuff feeding the indirect call.
+/// This never happens in checking mode.
+///
+bool CGPassManager::RefreshCallGraph(CallGraphSCC &CurSCC,
+                                     CallGraph &CG, bool CheckingMode) {
+  DenseMap<Value*, CallGraphNode*> CallSites;
+  
+  DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
+               << " nodes:\n";
+        for (CallGraphNode *CGN : CurSCC)
+          CGN->dump();
+        );
+
+  bool MadeChange = false;
+  bool DevirtualizedCall = false;
+  
+  // Scan all functions in the SCC.
+  unsigned FunctionNo = 0;
+  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
+       SCCIdx != E; ++SCCIdx, ++FunctionNo) {
+    CallGraphNode *CGN = *SCCIdx;
+    Function *F = CGN->getFunction();
+    if (!F || F->isDeclaration()) continue;
+    
+    // Walk the function body looking for call sites.  Sync up the call sites in
+    // CGN with those actually in the function.
+
+    // Keep track of the number of direct and indirect calls that were
+    // invalidated and removed.
+    unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
+    
+    // Get the set of call sites currently in the function.
+    for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
+      // If this call site is null, then the function pass deleted the call
+      // entirely and the WeakVH nulled it out.  
+      if (!I->first ||
+          // If we've already seen this call site, then the FunctionPass RAUW'd
+          // one call with another, which resulted in two "uses" in the edge
+          // list of the same call.
+          CallSites.count(I->first) ||
+
+          // If the call edge is not from a call or invoke, or it is a
+          // instrinsic call, then the function pass RAUW'd a call with 
+          // another value. This can happen when constant folding happens
+          // of well known functions etc.
+          !CallSite(I->first) ||
+          (CallSite(I->first).getCalledFunction() &&
+           CallSite(I->first).getCalledFunction()->isIntrinsic() &&
+           Intrinsic::isLeaf(
+               CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
+        assert(!CheckingMode &&
+               "CallGraphSCCPass did not update the CallGraph correctly!");
+        
+        // If this was an indirect call site, count it.
+        if (!I->second->getFunction())
+          ++NumIndirectRemoved;
+        else 
+          ++NumDirectRemoved;
+        
+        // Just remove the edge from the set of callees, keep track of whether
+        // I points to the last element of the vector.
+        bool WasLast = I + 1 == E;
+        CGN->removeCallEdge(I);
+        
+        // If I pointed to the last element of the vector, we have to bail out:
+        // iterator checking rejects comparisons of the resultant pointer with
+        // end.
+        if (WasLast)
+          break;
+        E = CGN->end();
+        continue;
+      }
+      
+      assert(!CallSites.count(I->first) &&
+             "Call site occurs in node multiple times");
+      
+      CallSite CS(I->first);
+      if (CS) {
+        Function *Callee = CS.getCalledFunction();
+        // Ignore intrinsics because they're not really function calls.
+        if (!Callee || !(Callee->isIntrinsic()))
+          CallSites.insert(std::make_pair(I->first, I->second));
+      }
+      ++I;
+    }
+    
+    // Loop over all of the instructions in the function, getting the callsites.
+    // Keep track of the number of direct/indirect calls added.
+    unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
+    
+    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
+      for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
+        CallSite CS(cast<Value>(I));
+        if (!CS) continue;
+        Function *Callee = CS.getCalledFunction();
+        if (Callee && Callee->isIntrinsic()) continue;
+        
+        // If this call site already existed in the callgraph, just verify it
+        // matches up to expectations and remove it from CallSites.
+        DenseMap<Value*, CallGraphNode*>::iterator ExistingIt =
+          CallSites.find(CS.getInstruction());
+        if (ExistingIt != CallSites.end()) {
+          CallGraphNode *ExistingNode = ExistingIt->second;
+
+          // Remove from CallSites since we have now seen it.
+          CallSites.erase(ExistingIt);
+          
+          // Verify that the callee is right.
+          if (ExistingNode->getFunction() == CS.getCalledFunction())
+            continue;
+          
+          // If we are in checking mode, we are not allowed to actually mutate
+          // the callgraph.  If this is a case where we can infer that the
+          // callgraph is less precise than it could be (e.g. an indirect call
+          // site could be turned direct), don't reject it in checking mode, and
+          // don't tweak it to be more precise.
+          if (CheckingMode && CS.getCalledFunction() &&
+              ExistingNode->getFunction() == nullptr)
+            continue;
+          
+          assert(!CheckingMode &&
+                 "CallGraphSCCPass did not update the CallGraph correctly!");
+          
+          // If not, we either went from a direct call to indirect, indirect to
+          // direct, or direct to different direct.
+          CallGraphNode *CalleeNode;
+          if (Function *Callee = CS.getCalledFunction()) {
+            CalleeNode = CG.getOrInsertFunction(Callee);
+            // Keep track of whether we turned an indirect call into a direct
+            // one.
+            if (!ExistingNode->getFunction()) {
+              DevirtualizedCall = true;
+              DEBUG(dbgs() << "  CGSCCPASSMGR: Devirtualized call to '"
+                           << Callee->getName() << "'\n");
+            }
+          } else {
+            CalleeNode = CG.getCallsExternalNode();
+          }
+
+          // Update the edge target in CGN.
+          CGN->replaceCallEdge(CS, CS, CalleeNode);
+          MadeChange = true;
+          continue;
+        }
+        
+        assert(!CheckingMode &&
+               "CallGraphSCCPass did not update the CallGraph correctly!");
+
+        // If the call site didn't exist in the CGN yet, add it.
+        CallGraphNode *CalleeNode;
+        if (Function *Callee = CS.getCalledFunction()) {
+          CalleeNode = CG.getOrInsertFunction(Callee);
+          ++NumDirectAdded;
+        } else {
+          CalleeNode = CG.getCallsExternalNode();
+          ++NumIndirectAdded;
+        }
+        
+        CGN->addCalledFunction(CS, CalleeNode);
+        MadeChange = true;
+      }
+    
+    // We scanned the old callgraph node, removing invalidated call sites and
+    // then added back newly found call sites.  One thing that can happen is
+    // that an old indirect call site was deleted and replaced with a new direct
+    // call.  In this case, we have devirtualized a call, and CGSCCPM would like
+    // to iteratively optimize the new code.  Unfortunately, we don't really
+    // have a great way to detect when this happens.  As an approximation, we
+    // just look at whether the number of indirect calls is reduced and the
+    // number of direct calls is increased.  There are tons of ways to fool this
+    // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
+    // direct call) but this is close enough.
+    if (NumIndirectRemoved > NumIndirectAdded &&
+        NumDirectRemoved < NumDirectAdded)
+      DevirtualizedCall = true;
+    
+    // After scanning this function, if we still have entries in callsites, then
+    // they are dangling pointers.  WeakVH should save us for this, so abort if
+    // this happens.
+    assert(CallSites.empty() && "Dangling pointers found in call sites map");
+    
+    // Periodically do an explicit clear to remove tombstones when processing
+    // large scc's.
+    if ((FunctionNo & 15) == 15)
+      CallSites.clear();
+  }
+
+  DEBUG(if (MadeChange) {
+          dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
+          for (CallGraphNode *CGN : CurSCC)
+            CGN->dump();
+          if (DevirtualizedCall)
+            dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
+
+         } else {
+           dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
+         }
+        );
+  (void)MadeChange;
+
+  return DevirtualizedCall;
+}
+
+/// Execute the body of the entire pass manager on the specified SCC.
+/// This keeps track of whether a function pass devirtualizes
+/// any calls and returns it in DevirtualizedCall.
+bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
+                                      bool &DevirtualizedCall) {
+  bool Changed = false;
+  
+  // Keep track of whether the callgraph is known to be up-to-date or not.
+  // The CGSSC pass manager runs two types of passes:
+  // CallGraphSCC Passes and other random function passes.  Because other
+  // random function passes are not CallGraph aware, they may clobber the
+  // call graph by introducing new calls or deleting other ones.  This flag
+  // is set to false when we run a function pass so that we know to clean up
+  // the callgraph when we need to run a CGSCCPass again.
+  bool CallGraphUpToDate = true;
+
+  // Run all passes on current SCC.
+  for (unsigned PassNo = 0, e = getNumContainedPasses();
+       PassNo != e; ++PassNo) {
+    Pass *P = getContainedPass(PassNo);
+    
+    // If we're in -debug-pass=Executions mode, construct the SCC node list,
+    // otherwise avoid constructing this string as it is expensive.
+    if (isPassDebuggingExecutionsOrMore()) {
+      std::string Functions;
+  #ifndef NDEBUG
+      raw_string_ostream OS(Functions);
+      for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
+           I != E; ++I) {
+        if (I != CurSCC.begin()) OS << ", ";
+        (*I)->print(OS);
+      }
+      OS.flush();
+  #endif
+      dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
+    }
+    dumpRequiredSet(P);
+    
+    initializeAnalysisImpl(P);
+    
+    // Actually run this pass on the current SCC.
+    Changed |= RunPassOnSCC(P, CurSCC, CG,
+                            CallGraphUpToDate, DevirtualizedCall);
+    
+    if (Changed)
+      dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
+    dumpPreservedSet(P);
+    
+    verifyPreservedAnalysis(P);      
+    removeNotPreservedAnalysis(P);
+    recordAvailableAnalysis(P);
+    removeDeadPasses(P, "", ON_CG_MSG);
+  }
+  
+  // If the callgraph was left out of date (because the last pass run was a
+  // functionpass), refresh it before we move on to the next SCC.
+  if (!CallGraphUpToDate)
+    DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
+  return Changed;
+}
+
+/// Execute all of the passes scheduled for execution.  Keep track of
+/// whether any of the passes modifies the module, and if so, return true.
+bool CGPassManager::runOnModule(Module &M) {
+  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+  bool Changed = doInitialization(CG);
+  
+  // Walk the callgraph in bottom-up SCC order.
+  scc_iterator<CallGraph*> CGI = scc_begin(&CG);
+
+  CallGraphSCC CurSCC(&CGI);
+  while (!CGI.isAtEnd()) {
+    // Copy the current SCC and increment past it so that the pass can hack
+    // on the SCC if it wants to without invalidating our iterator.
+    const std::vector<CallGraphNode *> &NodeVec = *CGI;
+    CurSCC.initialize(NodeVec.data(), NodeVec.data() + NodeVec.size());
+    ++CGI;
+
+    // At the top level, we run all the passes in this pass manager on the
+    // functions in this SCC.  However, we support iterative compilation in the
+    // case where a function pass devirtualizes a call to a function.  For
+    // example, it is very common for a function pass (often GVN or instcombine)
+    // to eliminate the addressing that feeds into a call.  With that improved
+    // information, we would like the call to be an inline candidate, infer
+    // mod-ref information etc.
+    //
+    // Because of this, we allow iteration up to a specified iteration count.
+    // This only happens in the case of a devirtualized call, so we only burn
+    // compile time in the case that we're making progress.  We also have a hard
+    // iteration count limit in case there is crazy code.
+    unsigned Iteration = 0;
+    bool DevirtualizedCall = false;
+    do {
+      DEBUG(if (Iteration)
+              dbgs() << "  SCCPASSMGR: Re-visiting SCC, iteration #"
+                     << Iteration << '\n');
+      DevirtualizedCall = false;
+      Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
+    } while (Iteration++ < MaxIterations && DevirtualizedCall);
+    
+    if (DevirtualizedCall)
+      DEBUG(dbgs() << "  CGSCCPASSMGR: Stopped iteration after " << Iteration
+                   << " times, due to -max-cg-scc-iterations\n");
+    
+    if (Iteration > MaxSCCIterations)
+      MaxSCCIterations = Iteration;
+    
+  }
+  Changed |= doFinalization(CG);
+  return Changed;
+}
+
+
+/// Initialize CG
+bool CGPassManager::doInitialization(CallGraph &CG) {
+  bool Changed = false;
+  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {  
+    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
+      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
+             "Invalid CGPassManager member");
+      Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
+    } else {
+      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
+    }
+  }
+  return Changed;
+}
+
+/// Finalize CG
+bool CGPassManager::doFinalization(CallGraph &CG) {
+  bool Changed = false;
+  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {  
+    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
+      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
+             "Invalid CGPassManager member");
+      Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
+    } else {
+      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
+    }
+  }
+  return Changed;
+}
+
+//===----------------------------------------------------------------------===//
+// CallGraphSCC Implementation
+//===----------------------------------------------------------------------===//
+
+/// This informs the SCC and the pass manager that the specified
+/// Old node has been deleted, and New is to be used in its place.
+void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
+  assert(Old != New && "Should not replace node with self");
+  for (unsigned i = 0; ; ++i) {
+    assert(i != Nodes.size() && "Node not in SCC");
+    if (Nodes[i] != Old) continue;
+    Nodes[i] = New;
+    break;
+  }
+  
+  // Update the active scc_iterator so that it doesn't contain dangling
+  // pointers to the old CallGraphNode.
+  scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
+  CGI->ReplaceNode(Old, New);
+}
+
+
+//===----------------------------------------------------------------------===//
+// CallGraphSCCPass Implementation
+//===----------------------------------------------------------------------===//
+
+/// Assign pass manager to manage this pass.
+void CallGraphSCCPass::assignPassManager(PMStack &PMS,
+                                         PassManagerType PreferredType) {
+  // Find CGPassManager 
+  while (!PMS.empty() &&
+         PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
+    PMS.pop();
+
+  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
+  CGPassManager *CGP;
+  
+  if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
+    CGP = (CGPassManager*)PMS.top();
+  else {
+    // Create new Call Graph SCC Pass Manager if it does not exist. 
+    assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
+    PMDataManager *PMD = PMS.top();
+
+    // [1] Create new Call Graph Pass Manager
+    CGP = new CGPassManager();
+
+    // [2] Set up new manager's top level manager
+    PMTopLevelManager *TPM = PMD->getTopLevelManager();
+    TPM->addIndirectPassManager(CGP);
+
+    // [3] Assign manager to manage this new manager. This may create
+    // and push new managers into PMS
+    Pass *P = CGP;
+    TPM->schedulePass(P);
+
+    // [4] Push new manager into PMS
+    PMS.push(CGP);
+  }
+
+  CGP->add(this);
+}
+
+/// For this class, we declare that we require and preserve the call graph.
+/// If the derived class implements this method, it should
+/// always explicitly call the implementation here.
+void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<CallGraphWrapperPass>();
+  AU.addPreserved<CallGraphWrapperPass>();
+}
+
+
+//===----------------------------------------------------------------------===//
+// PrintCallGraphPass Implementation
+//===----------------------------------------------------------------------===//
+
+namespace {
+  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
+  ///
+  class PrintCallGraphPass : public CallGraphSCCPass {
+    std::string Banner;
+    raw_ostream &Out;       // raw_ostream to print on.
+    
+  public:
+    static char ID;
+    PrintCallGraphPass(const std::string &B, raw_ostream &o)
+      : CallGraphSCCPass(ID), Banner(B), Out(o) {}
+
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.setPreservesAll();
+    }
+
+    bool runOnSCC(CallGraphSCC &SCC) override {
+      Out << Banner;
+      for (CallGraphNode *CGN : SCC) {
+        if (CGN->getFunction())
+          CGN->getFunction()->print(Out);
+        else
+          Out << "\nPrinting <null> Function\n";
+      }
+      return false;
+    }
+  };
+  
+} // end anonymous namespace.
+
+char PrintCallGraphPass::ID = 0;
+
+Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &O,
+                                          const std::string &Banner) const {
+  return new PrintCallGraphPass(Banner, O);
+}
+
Index: llvm/trunk/lib/Analysis/CallPrinter.cpp
===================================================================
--- llvm/trunk/lib/Analysis/CallPrinter.cpp
+++ llvm/trunk/lib/Analysis/CallPrinter.cpp
@@ -0,0 +1,92 @@
+//===- CallPrinter.cpp - DOT printer for call graph -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines '-dot-callgraph', which emit a callgraph.<fnname>.dot
+// containing the call graph of a module.
+//
+// There is also a pass available to directly call dotty ('-view-callgraph').
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/CallPrinter.h"
+#include "llvm/Analysis/DOTGraphTraitsPass.h"
+
+using namespace llvm;
+
+namespace llvm {
+
+template <> struct DOTGraphTraits<CallGraph *> : public DefaultDOTGraphTraits {
+  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
+
+  static std::string getGraphName(CallGraph *Graph) { return "Call graph"; }
+
+  std::string getNodeLabel(CallGraphNode *Node, CallGraph *Graph) {
+    if (Function *Func = Node->getFunction())
+      return Func->getName();
+
+    return "external node";
+  }
+};
+
+struct AnalysisCallGraphWrapperPassTraits {
+  static CallGraph *getGraph(CallGraphWrapperPass *P) {
+    return &P->getCallGraph();
+  }
+};
+
+} // end llvm namespace
+
+namespace {
+
+struct CallGraphViewer
+    : public DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
+                                        AnalysisCallGraphWrapperPassTraits> {
+  static char ID;
+
+  CallGraphViewer()
+      : DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
+                                   AnalysisCallGraphWrapperPassTraits>(
+            "callgraph", ID) {
+    initializeCallGraphViewerPass(*PassRegistry::getPassRegistry());
+  }
+};
+
+struct CallGraphPrinter : public DOTGraphTraitsModulePrinter<
+                              CallGraphWrapperPass, true, CallGraph *,
+                              AnalysisCallGraphWrapperPassTraits> {
+  static char ID;
+
+  CallGraphPrinter()
+      : DOTGraphTraitsModulePrinter<CallGraphWrapperPass, true, CallGraph *,
+                                    AnalysisCallGraphWrapperPassTraits>(
+            "callgraph", ID) {
+    initializeCallGraphPrinterPass(*PassRegistry::getPassRegistry());
+  }
+};
+
+} // end anonymous namespace
+
+char CallGraphViewer::ID = 0;
+INITIALIZE_PASS(CallGraphViewer, "view-callgraph", "View call graph", false,
+                false)
+
+char CallGraphPrinter::ID = 0;
+INITIALIZE_PASS(CallGraphPrinter, "dot-callgraph",
+                "Print call graph to 'dot' file", false, false)
+
+// Create methods available outside of this file, to use them
+// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
+// the link time optimization.
+
+ModulePass *llvm::createCallGraphViewerPass() { return new CallGraphViewer(); }
+
+ModulePass *llvm::createCallGraphPrinterPass() {
+  return new CallGraphPrinter();
+}
Index: llvm/trunk/lib/Analysis/GlobalsModRef.cpp
===================================================================
--- llvm/trunk/lib/Analysis/GlobalsModRef.cpp
+++ llvm/trunk/lib/Analysis/GlobalsModRef.cpp
@@ -0,0 +1,798 @@
+//===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This simple pass provides alias and mod/ref information for global values
+// that do not have their address taken, and keeps track of whether functions
+// read or write memory (are "pure").  For this simple (but very common) case,
+// we can provide pretty accurate and useful information.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+using namespace llvm;
+
+#define DEBUG_TYPE "globalsmodref-aa"
+
+STATISTIC(NumNonAddrTakenGlobalVars,
+          "Number of global vars without address taken");
+STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
+STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
+STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
+STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");
+
+// An option to enable unsafe alias results from the GlobalsModRef analysis.
+// When enabled, GlobalsModRef will provide no-alias results which in extremely
+// rare cases may not be conservatively correct. In particular, in the face of
+// transforms which cause assymetry between how effective GetUnderlyingObject
+// is for two pointers, it may produce incorrect results.
+//
+// These unsafe results have been returned by GMR for many years without
+// causing significant issues in the wild and so we provide a mechanism to
+// re-enable them for users of LLVM that have a particular performance
+// sensitivity and no known issues. The option also makes it easy to evaluate
+// the performance impact of these results.
+static cl::opt<bool> EnableUnsafeGlobalsModRefAliasResults(
+    "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden);
+
+/// The mod/ref information collected for a particular function.
+///
+/// We collect information about mod/ref behavior of a function here, both in
+/// general and as pertains to specific globals. We only have this detailed
+/// information when we know *something* useful about the behavior. If we
+/// saturate to fully general mod/ref, we remove the info for the function.
+class GlobalsModRef::FunctionInfo {
+  typedef SmallDenseMap<const GlobalValue *, ModRefInfo, 16> GlobalInfoMapType;
+
+  /// Build a wrapper struct that has 8-byte alignment. All heap allocations
+  /// should provide this much alignment at least, but this makes it clear we
+  /// specifically rely on this amount of alignment.
+  struct LLVM_ALIGNAS(8) AlignedMap {
+    AlignedMap() {}
+    AlignedMap(const AlignedMap &Arg) : Map(Arg.Map) {}
+    GlobalInfoMapType Map;
+  };
+
+  /// Pointer traits for our aligned map.
+  struct AlignedMapPointerTraits {
+    static inline void *getAsVoidPointer(AlignedMap *P) { return P; }
+    static inline AlignedMap *getFromVoidPointer(void *P) {
+      return (AlignedMap *)P;
+    }
+    enum { NumLowBitsAvailable = 3 };
+    static_assert(AlignOf<AlignedMap>::Alignment >= (1 << NumLowBitsAvailable),
+                  "AlignedMap insufficiently aligned to have enough low bits.");
+  };
+
+  /// The bit that flags that this function may read any global. This is
+  /// chosen to mix together with ModRefInfo bits.
+  enum { MayReadAnyGlobal = 4 };
+
+  /// Checks to document the invariants of the bit packing here.
+  static_assert((MayReadAnyGlobal & MRI_ModRef) == 0,
+                "ModRef and the MayReadAnyGlobal flag bits overlap.");
+  static_assert(((MayReadAnyGlobal | MRI_ModRef) >>
+                 AlignedMapPointerTraits::NumLowBitsAvailable) == 0,
+                "Insufficient low bits to store our flag and ModRef info.");
+
+public:
+  FunctionInfo() : Info() {}
+  ~FunctionInfo() {
+    delete Info.getPointer();
+  }
+  // Spell out the copy ond move constructors and assignment operators to get
+  // deep copy semantics and correct move semantics in the face of the
+  // pointer-int pair.
+  FunctionInfo(const FunctionInfo &Arg)
+      : Info(nullptr, Arg.Info.getInt()) {
+    if (const auto *ArgPtr = Arg.Info.getPointer())
+      Info.setPointer(new AlignedMap(*ArgPtr));
+  }
+  FunctionInfo(FunctionInfo &&Arg)
+      : Info(Arg.Info.getPointer(), Arg.Info.getInt()) {
+    Arg.Info.setPointerAndInt(nullptr, 0);
+  }
+  FunctionInfo &operator=(const FunctionInfo &RHS) {
+    delete Info.getPointer();
+    Info.setPointerAndInt(nullptr, RHS.Info.getInt());
+    if (const auto *RHSPtr = RHS.Info.getPointer())
+      Info.setPointer(new AlignedMap(*RHSPtr));
+    return *this;
+  }
+  FunctionInfo &operator=(FunctionInfo &&RHS) {
+    delete Info.getPointer();
+    Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt());
+    RHS.Info.setPointerAndInt(nullptr, 0);
+    return *this;
+  }
+
+  /// Returns the \c ModRefInfo info for this function.
+  ModRefInfo getModRefInfo() const {
+    return ModRefInfo(Info.getInt() & MRI_ModRef);
+  }
+
+  /// Adds new \c ModRefInfo for this function to its state.
+  void addModRefInfo(ModRefInfo NewMRI) {
+    Info.setInt(Info.getInt() | NewMRI);
+  }
+
+  /// Returns whether this function may read any global variable, and we don't
+  /// know which global.
+  bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; }
+
+  /// Sets this function as potentially reading from any global.
+  void setMayReadAnyGlobal() { Info.setInt(Info.getInt() | MayReadAnyGlobal); }
+
+  /// Returns the \c ModRefInfo info for this function w.r.t. a particular
+  /// global, which may be more precise than the general information above.
+  ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const {
+    ModRefInfo GlobalMRI = mayReadAnyGlobal() ? MRI_Ref : MRI_NoModRef;
+    if (AlignedMap *P = Info.getPointer()) {
+      auto I = P->Map.find(&GV);
+      if (I != P->Map.end())
+        GlobalMRI = ModRefInfo(GlobalMRI | I->second);
+    }
+    return GlobalMRI;
+  }
+
+  /// Add mod/ref info from another function into ours, saturating towards
+  /// MRI_ModRef.
+  void addFunctionInfo(const FunctionInfo &FI) {
+    addModRefInfo(FI.getModRefInfo());
+
+    if (FI.mayReadAnyGlobal())
+      setMayReadAnyGlobal();
+
+    if (AlignedMap *P = FI.Info.getPointer())
+      for (const auto &G : P->Map)
+        addModRefInfoForGlobal(*G.first, G.second);
+  }
+
+  void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI) {
+    AlignedMap *P = Info.getPointer();
+    if (!P) {
+      P = new AlignedMap();
+      Info.setPointer(P);
+    }
+    auto &GlobalMRI = P->Map[&GV];
+    GlobalMRI = ModRefInfo(GlobalMRI | NewMRI);
+  }
+
+  /// Clear a global's ModRef info. Should be used when a global is being
+  /// deleted.
+  void eraseModRefInfoForGlobal(const GlobalValue &GV) {
+    if (AlignedMap *P = Info.getPointer())
+      P->Map.erase(&GV);
+  }
+
+private:
+  /// All of the information is encoded into a single pointer, with a three bit
+  /// integer in the low three bits. The high bit provides a flag for when this
+  /// function may read any global. The low two bits are the ModRefInfo. And
+  /// the pointer, when non-null, points to a map from GlobalValue to
+  /// ModRefInfo specific to that GlobalValue.
+  PointerIntPair<AlignedMap *, 3, unsigned, AlignedMapPointerTraits> Info;
+};
+
+void GlobalsModRef::DeletionCallbackHandle::deleted() {
+  Value *V = getValPtr();
+  if (auto *F = dyn_cast<Function>(V))
+    GMR.FunctionInfos.erase(F);
+
+  if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
+    if (GMR.NonAddressTakenGlobals.erase(GV)) {
+      // This global might be an indirect global.  If so, remove it and
+      // remove any AllocRelatedValues for it.
+      if (GMR.IndirectGlobals.erase(GV)) {
+        // Remove any entries in AllocsForIndirectGlobals for this global.
+        for (auto I = GMR.AllocsForIndirectGlobals.begin(),
+                  E = GMR.AllocsForIndirectGlobals.end();
+             I != E; ++I)
+          if (I->second == GV)
+            GMR.AllocsForIndirectGlobals.erase(I);
+      }
+
+      // Scan the function info we have collected and remove this global
+      // from all of them.
+      for (auto &FIPair : GMR.FunctionInfos)
+        FIPair.second.eraseModRefInfoForGlobal(*GV);
+    }
+  }
+
+  // If this is an allocation related to an indirect global, remove it.
+  GMR.AllocsForIndirectGlobals.erase(V);
+
+  // And clear out the handle.
+  setValPtr(nullptr);
+  GMR.Handles.erase(I);
+  // This object is now destroyed!
+}
+
+char GlobalsModRef::ID = 0;
+INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
+                         "Simple mod/ref analysis for globals", false, true,
+                         false)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
+INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
+                       "Simple mod/ref analysis for globals", false, true,
+                       false)
+
+Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); }
+
+GlobalsModRef::GlobalsModRef() : ModulePass(ID) {
+  initializeGlobalsModRefPass(*PassRegistry::getPassRegistry());
+}
+
+FunctionModRefBehavior GlobalsModRef::getModRefBehavior(const Function *F) {
+  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
+
+  if (FunctionInfo *FI = getFunctionInfo(F)) {
+    if (FI->getModRefInfo() == MRI_NoModRef)
+      Min = FMRB_DoesNotAccessMemory;
+    else if ((FI->getModRefInfo() & MRI_Mod) == 0)
+      Min = FMRB_OnlyReadsMemory;
+  }
+
+  return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min);
+}
+
+FunctionModRefBehavior GlobalsModRef::getModRefBehavior(ImmutableCallSite CS) {
+  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
+
+  if (const Function *F = CS.getCalledFunction())
+    if (FunctionInfo *FI = getFunctionInfo(F)) {
+      if (FI->getModRefInfo() == MRI_NoModRef)
+        Min = FMRB_DoesNotAccessMemory;
+      else if ((FI->getModRefInfo() & MRI_Mod) == 0)
+        Min = FMRB_OnlyReadsMemory;
+    }
+
+  return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
+}
+
+/// Returns the function info for the function, or null if we don't have
+/// anything useful to say about it.
+GlobalsModRef::FunctionInfo *GlobalsModRef::getFunctionInfo(const Function *F) {
+  auto I = FunctionInfos.find(F);
+  if (I != FunctionInfos.end())
+    return &I->second;
+  return nullptr;
+}
+
+/// AnalyzeGlobals - Scan through the users of all of the internal
+/// GlobalValue's in the program.  If none of them have their "address taken"
+/// (really, their address passed to something nontrivial), record this fact,
+/// and record the functions that they are used directly in.
+void GlobalsModRef::AnalyzeGlobals(Module &M) {
+  SmallPtrSet<Function *, 64> TrackedFunctions;
+  for (Function &F : M)
+    if (F.hasLocalLinkage())
+      if (!AnalyzeUsesOfPointer(&F)) {
+        // Remember that we are tracking this global.
+        NonAddressTakenGlobals.insert(&F);
+        TrackedFunctions.insert(&F);
+        Handles.emplace_front(*this, &F);
+        Handles.front().I = Handles.begin();
+        ++NumNonAddrTakenFunctions;
+      }
+
+  SmallPtrSet<Function *, 64> Readers, Writers;
+  for (GlobalVariable &GV : M.globals())
+    if (GV.hasLocalLinkage()) {
+      if (!AnalyzeUsesOfPointer(&GV, &Readers,
+                                GV.isConstant() ? nullptr : &Writers)) {
+        // Remember that we are tracking this global, and the mod/ref fns
+        NonAddressTakenGlobals.insert(&GV);
+        Handles.emplace_front(*this, &GV);
+        Handles.front().I = Handles.begin();
+
+        for (Function *Reader : Readers) {
+          if (TrackedFunctions.insert(Reader).second) {
+            Handles.emplace_front(*this, Reader);
+            Handles.front().I = Handles.begin();
+          }
+          FunctionInfos[Reader].addModRefInfoForGlobal(GV, MRI_Ref);
+        }
+
+        if (!GV.isConstant()) // No need to keep track of writers to constants
+          for (Function *Writer : Writers) {
+            if (TrackedFunctions.insert(Writer).second) {
+              Handles.emplace_front(*this, Writer);
+              Handles.front().I = Handles.begin();
+            }
+            FunctionInfos[Writer].addModRefInfoForGlobal(GV, MRI_Mod);
+          }
+        ++NumNonAddrTakenGlobalVars;
+
+        // If this global holds a pointer type, see if it is an indirect global.
+        if (GV.getType()->getElementType()->isPointerTy() &&
+            AnalyzeIndirectGlobalMemory(&GV))
+          ++NumIndirectGlobalVars;
+      }
+      Readers.clear();
+      Writers.clear();
+    }
+}
+
+/// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
+/// If this is used by anything complex (i.e., the address escapes), return
+/// true.  Also, while we are at it, keep track of those functions that read and
+/// write to the value.
+///
+/// If OkayStoreDest is non-null, stores into this global are allowed.
+bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
+                                         SmallPtrSetImpl<Function *> *Readers,
+                                         SmallPtrSetImpl<Function *> *Writers,
+                                         GlobalValue *OkayStoreDest) {
+  if (!V->getType()->isPointerTy())
+    return true;
+
+  for (Use &U : V->uses()) {
+    User *I = U.getUser();
+    if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
+      if (Readers)
+        Readers->insert(LI->getParent()->getParent());
+    } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
+      if (V == SI->getOperand(1)) {
+        if (Writers)
+          Writers->insert(SI->getParent()->getParent());
+      } else if (SI->getOperand(1) != OkayStoreDest) {
+        return true; // Storing the pointer
+      }
+    } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) {
+      if (AnalyzeUsesOfPointer(I, Readers, Writers))
+        return true;
+    } else if (Operator::getOpcode(I) == Instruction::BitCast) {
+      if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest))
+        return true;
+    } else if (auto CS = CallSite(I)) {
+      // Make sure that this is just the function being called, not that it is
+      // passing into the function.
+      if (!CS.isCallee(&U)) {
+        // Detect calls to free.
+        if (isFreeCall(I, TLI)) {
+          if (Writers)
+            Writers->insert(CS->getParent()->getParent());
+        } else {
+          return true; // Argument of an unknown call.
+        }
+      }
+    } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
+      if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
+        return true; // Allow comparison against null.
+    } else {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+/// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
+/// which holds a pointer type.  See if the global always points to non-aliased
+/// heap memory: that is, all initializers of the globals are allocations, and
+/// those allocations have no use other than initialization of the global.
+/// Further, all loads out of GV must directly use the memory, not store the
+/// pointer somewhere.  If this is true, we consider the memory pointed to by
+/// GV to be owned by GV and can disambiguate other pointers from it.
+bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
+  // Keep track of values related to the allocation of the memory, f.e. the
+  // value produced by the malloc call and any casts.
+  std::vector<Value *> AllocRelatedValues;
+
+  // Walk the user list of the global.  If we find anything other than a direct
+  // load or store, bail out.
+  for (User *U : GV->users()) {
+    if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
+      // The pointer loaded from the global can only be used in simple ways:
+      // we allow addressing of it and loading storing to it.  We do *not* allow
+      // storing the loaded pointer somewhere else or passing to a function.
+      if (AnalyzeUsesOfPointer(LI))
+        return false; // Loaded pointer escapes.
+      // TODO: Could try some IP mod/ref of the loaded pointer.
+    } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
+      // Storing the global itself.
+      if (SI->getOperand(0) == GV)
+        return false;
+
+      // If storing the null pointer, ignore it.
+      if (isa<ConstantPointerNull>(SI->getOperand(0)))
+        continue;
+
+      // Check the value being stored.
+      Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
+                                       GV->getParent()->getDataLayout());
+
+      if (!isAllocLikeFn(Ptr, TLI))
+        return false; // Too hard to analyze.
+
+      // Analyze all uses of the allocation.  If any of them are used in a
+      // non-simple way (e.g. stored to another global) bail out.
+      if (AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr,
+                               GV))
+        return false; // Loaded pointer escapes.
+
+      // Remember that this allocation is related to the indirect global.
+      AllocRelatedValues.push_back(Ptr);
+    } else {
+      // Something complex, bail out.
+      return false;
+    }
+  }
+
+  // Okay, this is an indirect global.  Remember all of the allocations for
+  // this global in AllocsForIndirectGlobals.
+  while (!AllocRelatedValues.empty()) {
+    AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
+    Handles.emplace_front(*this, AllocRelatedValues.back());
+    Handles.front().I = Handles.begin();
+    AllocRelatedValues.pop_back();
+  }
+  IndirectGlobals.insert(GV);
+  Handles.emplace_front(*this, GV);
+  Handles.front().I = Handles.begin();
+  return true;
+}
+
+/// AnalyzeCallGraph - At this point, we know the functions where globals are
+/// immediately stored to and read from.  Propagate this information up the call
+/// graph to all callers and compute the mod/ref info for all memory for each
+/// function.
+void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
+  // We do a bottom-up SCC traversal of the call graph.  In other words, we
+  // visit all callees before callers (leaf-first).
+  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
+    const std::vector<CallGraphNode *> &SCC = *I;
+    assert(!SCC.empty() && "SCC with no functions?");
+
+    if (!SCC[0]->getFunction()) {
+      // Calls externally - can't say anything useful.  Remove any existing
+      // function records (may have been created when scanning globals).
+      for (auto *Node : SCC)
+        FunctionInfos.erase(Node->getFunction());
+      continue;
+    }
+
+    FunctionInfo &FI = FunctionInfos[SCC[0]->getFunction()];
+    bool KnowNothing = false;
+
+    // Collect the mod/ref properties due to called functions.  We only compute
+    // one mod-ref set.
+    for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
+      Function *F = SCC[i]->getFunction();
+      if (!F) {
+        KnowNothing = true;
+        break;
+      }
+
+      if (F->isDeclaration()) {
+        // Try to get mod/ref behaviour from function attributes.
+        if (F->doesNotAccessMemory()) {
+          // Can't do better than that!
+        } else if (F->onlyReadsMemory()) {
+          FI.addModRefInfo(MRI_Ref);
+          if (!F->isIntrinsic())
+            // This function might call back into the module and read a global -
+            // consider every global as possibly being read by this function.
+            FI.setMayReadAnyGlobal();
+        } else {
+          FI.addModRefInfo(MRI_ModRef);
+          // Can't say anything useful unless it's an intrinsic - they don't
+          // read or write global variables of the kind considered here.
+          KnowNothing = !F->isIntrinsic();
+        }
+        continue;
+      }
+
+      for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
+           CI != E && !KnowNothing; ++CI)
+        if (Function *Callee = CI->second->getFunction()) {
+          if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
+            // Propagate function effect up.
+            FI.addFunctionInfo(*CalleeFI);
+          } else {
+            // Can't say anything about it.  However, if it is inside our SCC,
+            // then nothing needs to be done.
+            CallGraphNode *CalleeNode = CG[Callee];
+            if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end())
+              KnowNothing = true;
+          }
+        } else {
+          KnowNothing = true;
+        }
+    }
+
+    // If we can't say anything useful about this SCC, remove all SCC functions
+    // from the FunctionInfos map.
+    if (KnowNothing) {
+      for (auto *Node : SCC)
+        FunctionInfos.erase(Node->getFunction());
+      continue;
+    }
+
+    // Scan the function bodies for explicit loads or stores.
+    for (auto *Node : SCC) {
+      if (FI.getModRefInfo() == MRI_ModRef)
+        break; // The mod/ref lattice saturates here.
+      for (Instruction &I : instructions(Node->getFunction())) {
+        if (FI.getModRefInfo() == MRI_ModRef)
+          break; // The mod/ref lattice saturates here.
+
+        // We handle calls specially because the graph-relevant aspects are
+        // handled above.
+        if (auto CS = CallSite(&I)) {
+          if (isAllocationFn(&I, TLI) || isFreeCall(&I, TLI)) {
+            // FIXME: It is completely unclear why this is necessary and not
+            // handled by the above graph code.
+            FI.addModRefInfo(MRI_ModRef);
+          } else if (Function *Callee = CS.getCalledFunction()) {
+            // The callgraph doesn't include intrinsic calls.
+            if (Callee->isIntrinsic()) {
+              FunctionModRefBehavior Behaviour =
+                  AliasAnalysis::getModRefBehavior(Callee);
+              FI.addModRefInfo(ModRefInfo(Behaviour & MRI_ModRef));
+            }
+          }
+          continue;
+        }
+
+        // All non-call instructions we use the primary predicates for whether
+        // thay read or write memory.
+        if (I.mayReadFromMemory())
+          FI.addModRefInfo(MRI_Ref);
+        if (I.mayWriteToMemory())
+          FI.addModRefInfo(MRI_Mod);
+      }
+    }
+
+    if ((FI.getModRefInfo() & MRI_Mod) == 0)
+      ++NumReadMemFunctions;
+    if (FI.getModRefInfo() == MRI_NoModRef)
+      ++NumNoMemFunctions;
+
+    // Finally, now that we know the full effect on this SCC, clone the
+    // information to each function in the SCC.
+    for (unsigned i = 1, e = SCC.size(); i != e; ++i)
+      FunctionInfos[SCC[i]->getFunction()] = FI;
+  }
+}
+
+// There are particular cases where we can conclude no-alias between
+// a non-addr-taken global and some other underlying object. Specifically,
+// a non-addr-taken global is known to not be escaped from any function. It is
+// also incorrect for a transformation to introduce an escape of a global in
+// a way that is observable when it was not there previously. One function
+// being transformed to introduce an escape which could possibly be observed
+// (via loading from a global or the return value for example) within another
+// function is never safe. If the observation is made through non-atomic
+// operations on different threads, it is a data-race and UB. If the
+// observation is well defined, by being observed the transformation would have
+// changed program behavior by introducing the observed escape, making it an
+// invalid transform.
+//
+// This property does require that transformations which *temporarily* escape
+// a global that was not previously escaped, prior to restoring it, cannot rely
+// on the results of GMR::alias. This seems a reasonable restriction, although
+// currently there is no way to enforce it. There is also no realistic
+// optimization pass that would make this mistake. The closest example is
+// a transformation pass which does reg2mem of SSA values but stores them into
+// global variables temporarily before restoring the global variable's value.
+// This could be useful to expose "benign" races for example. However, it seems
+// reasonable to require that a pass which introduces escapes of global
+// variables in this way to either not trust AA results while the escape is
+// active, or to be forced to operate as a module pass that cannot co-exist
+// with an alias analysis such as GMR.
+bool GlobalsModRef::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
+                                               const Value *V) {
+  // In order to know that the underlying object cannot alias the
+  // non-addr-taken global, we must know that it would have to be an escape.
+  // Thus if the underlying object is a function argument, a load from
+  // a global, or the return of a function, it cannot alias. We can also
+  // recurse through PHI nodes and select nodes provided all of their inputs
+  // resolve to one of these known-escaping roots.
+  SmallPtrSet<const Value *, 8> Visited;
+  SmallVector<const Value *, 8> Inputs;
+  Visited.insert(V);
+  Inputs.push_back(V);
+  int Depth = 0;
+  do {
+    const Value *Input = Inputs.pop_back_val();
+
+    if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
+      // If one input is the very global we're querying against, then we can't
+      // conclude no-alias.
+      if (InputGV == GV)
+        return false;
+
+      // Distinct GlobalVariables never alias, unless overriden or zero-sized.
+      // FIXME: The condition can be refined, but be conservative for now.
+      auto *GVar = dyn_cast<GlobalVariable>(GV);
+      auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
+      if (GVar && InputGVar &&
+          !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
+          !GVar->mayBeOverridden() && !InputGVar->mayBeOverridden()) {
+        Type *GVType = GVar->getInitializer()->getType();
+        Type *InputGVType = InputGVar->getInitializer()->getType();
+        if (GVType->isSized() && InputGVType->isSized() &&
+            (DL->getTypeAllocSize(GVType) > 0) &&
+            (DL->getTypeAllocSize(InputGVType) > 0))
+          continue;
+      }
+
+      // Conservatively return false, even though we could be smarter
+      // (e.g. look through GlobalAliases).
+      return false;
+    }
+
+    if (isa<Argument>(Input) || isa<CallInst>(Input) ||
+        isa<InvokeInst>(Input)) {
+      // Arguments to functions or returns from functions are inherently
+      // escaping, so we can immediately classify those as not aliasing any
+      // non-addr-taken globals.
+      continue;
+    }
+    if (auto *LI = dyn_cast<LoadInst>(Input)) {
+      // A pointer loaded from a global would have been captured, and we know
+      // that the global is non-escaping, so no alias.
+      if (isa<GlobalValue>(GetUnderlyingObject(LI->getPointerOperand(), *DL)))
+        continue;
+
+      // Otherwise, a load could come from anywhere, so bail.
+      return false;
+    }
+
+    // Recurse through a limited number of selects and PHIs. This is an
+    // arbitrary depth of 4, lower numbers could be used to fix compile time
+    // issues if needed, but this is generally expected to be only be important
+    // for small depths.
+    if (++Depth > 4)
+      return false;
+    if (auto *SI = dyn_cast<SelectInst>(Input)) {
+      const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), *DL);
+      const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), *DL);
+      if (Visited.insert(LHS).second)
+        Inputs.push_back(LHS);
+      if (Visited.insert(RHS).second)
+        Inputs.push_back(RHS);
+      continue;
+    }
+    if (auto *PN = dyn_cast<PHINode>(Input)) {
+      for (const Value *Op : PN->incoming_values()) {
+        Op = GetUnderlyingObject(Op, *DL);
+        if (Visited.insert(Op).second)
+          Inputs.push_back(Op);
+      }
+      continue;
+    }
+
+    // FIXME: It would be good to handle other obvious no-alias cases here, but
+    // it isn't clear how to do so reasonbly without building a small version
+    // of BasicAA into this code. We could recurse into AliasAnalysis::alias
+    // here but that seems likely to go poorly as we're inside the
+    // implementation of such a query. Until then, just conservatievly retun
+    // false.
+    return false;
+  } while (!Inputs.empty());
+
+  // If all the inputs to V were definitively no-alias, then V is no-alias.
+  return true;
+}
+
+/// alias - If one of the pointers is to a global that we are tracking, and the
+/// other is some random pointer, we know there cannot be an alias, because the
+/// address of the global isn't taken.
+AliasResult GlobalsModRef::alias(const MemoryLocation &LocA,
+                                 const MemoryLocation &LocB) {
+  // Get the base object these pointers point to.
+  const Value *UV1 = GetUnderlyingObject(LocA.Ptr, *DL);
+  const Value *UV2 = GetUnderlyingObject(LocB.Ptr, *DL);
+
+  // If either of the underlying values is a global, they may be non-addr-taken
+  // globals, which we can answer queries about.
+  const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
+  const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
+  if (GV1 || GV2) {
+    // If the global's address is taken, pretend we don't know it's a pointer to
+    // the global.
+    if (GV1 && !NonAddressTakenGlobals.count(GV1))
+      GV1 = nullptr;
+    if (GV2 && !NonAddressTakenGlobals.count(GV2))
+      GV2 = nullptr;
+
+    // If the two pointers are derived from two different non-addr-taken
+    // globals we know these can't alias.
+    if (GV1 && GV2 && GV1 != GV2)
+      return NoAlias;
+
+    // If one is and the other isn't, it isn't strictly safe but we can fake
+    // this result if necessary for performance. This does not appear to be
+    // a common problem in practice.
+    if (EnableUnsafeGlobalsModRefAliasResults)
+      if ((GV1 || GV2) && GV1 != GV2)
+        return NoAlias;
+
+    // Check for a special case where a non-escaping global can be used to
+    // conclude no-alias.
+    if ((GV1 || GV2) && GV1 != GV2) {
+      const GlobalValue *GV = GV1 ? GV1 : GV2;
+      const Value *UV = GV1 ? UV2 : UV1;
+      if (isNonEscapingGlobalNoAlias(GV, UV))
+        return NoAlias;
+    }
+
+    // Otherwise if they are both derived from the same addr-taken global, we
+    // can't know the two accesses don't overlap.
+  }
+
+  // These pointers may be based on the memory owned by an indirect global.  If
+  // so, we may be able to handle this.  First check to see if the base pointer
+  // is a direct load from an indirect global.
+  GV1 = GV2 = nullptr;
+  if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
+    if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
+      if (IndirectGlobals.count(GV))
+        GV1 = GV;
+  if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
+    if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
+      if (IndirectGlobals.count(GV))
+        GV2 = GV;
+
+  // These pointers may also be from an allocation for the indirect global.  If
+  // so, also handle them.
+  if (!GV1)
+    GV1 = AllocsForIndirectGlobals.lookup(UV1);
+  if (!GV2)
+    GV2 = AllocsForIndirectGlobals.lookup(UV2);
+
+  // Now that we know whether the two pointers are related to indirect globals,
+  // use this to disambiguate the pointers. If the pointers are based on
+  // different indirect globals they cannot alias.
+  if (GV1 && GV2 && GV1 != GV2)
+    return NoAlias;
+
+  // If one is based on an indirect global and the other isn't, it isn't
+  // strictly safe but we can fake this result if necessary for performance.
+  // This does not appear to be a common problem in practice.
+  if (EnableUnsafeGlobalsModRefAliasResults)
+    if ((GV1 || GV2) && GV1 != GV2)
+      return NoAlias;
+
+  return AliasAnalysis::alias(LocA, LocB);
+}
+
+ModRefInfo GlobalsModRef::getModRefInfo(ImmutableCallSite CS,
+                                        const MemoryLocation &Loc) {
+  unsigned Known = MRI_ModRef;
+
+  // If we are asking for mod/ref info of a direct call with a pointer to a
+  // global we are tracking, return information if we have it.
+  const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout();
+  if (const GlobalValue *GV =
+          dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
+    if (GV->hasLocalLinkage())
+      if (const Function *F = CS.getCalledFunction())
+        if (NonAddressTakenGlobals.count(GV))
+          if (const FunctionInfo *FI = getFunctionInfo(F))
+            Known = FI->getModRefInfoForGlobal(*GV);
+
+  if (Known == MRI_NoModRef)
+    return MRI_NoModRef; // No need to query other mod/ref analyses
+  return ModRefInfo(Known & AliasAnalysis::getModRefInfo(CS, Loc));
+}
Index: llvm/trunk/lib/Analysis/IPA/CMakeLists.txt
===================================================================
--- llvm/trunk/lib/Analysis/IPA/CMakeLists.txt
+++ llvm/trunk/lib/Analysis/IPA/CMakeLists.txt
@@ -1,10 +0,0 @@
-add_llvm_library(LLVMipa
-  CallGraph.cpp
-  CallGraphSCCPass.cpp
-  CallPrinter.cpp
-  GlobalsModRef.cpp
-  IPA.cpp
-  InlineCost.cpp
-  )
-
-add_dependencies(LLVMipa intrinsics_gen)
Index: llvm/trunk/lib/Analysis/IPA/CallGraph.cpp
===================================================================
--- llvm/trunk/lib/Analysis/IPA/CallGraph.cpp
+++ llvm/trunk/lib/Analysis/IPA/CallGraph.cpp
@@ -1,309 +0,0 @@
-//===- CallGraph.cpp - Build a Module's call graph ------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/CallGraph.h"
-#include "llvm/IR/CallSite.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/Module.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-using namespace llvm;
-
-//===----------------------------------------------------------------------===//
-// Implementations of the CallGraph class methods.
-//
-
-CallGraph::CallGraph(Module &M)
-    : M(M), Root(nullptr), ExternalCallingNode(getOrInsertFunction(nullptr)),
-      CallsExternalNode(llvm::make_unique<CallGraphNode>(nullptr)) {
-  // Add every function to the call graph.
-  for (Function &F : M)
-    addToCallGraph(&F);
-
-  // If we didn't find a main function, use the external call graph node
-  if (!Root)
-    Root = ExternalCallingNode;
-}
-
-CallGraph::CallGraph(CallGraph &&Arg)
-    : M(Arg.M), FunctionMap(std::move(Arg.FunctionMap)), Root(Arg.Root),
-      ExternalCallingNode(Arg.ExternalCallingNode),
-      CallsExternalNode(std::move(Arg.CallsExternalNode)) {
-  Arg.FunctionMap.clear();
-  Arg.Root = nullptr;
-  Arg.ExternalCallingNode = nullptr;
-}
-
-CallGraph::~CallGraph() {
-  // CallsExternalNode is not in the function map, delete it explicitly.
-  if (CallsExternalNode)
-    CallsExternalNode->allReferencesDropped();
-
-// Reset all node's use counts to zero before deleting them to prevent an
-// assertion from firing.
-#ifndef NDEBUG
-  for (auto &I : FunctionMap)
-    I.second->allReferencesDropped();
-#endif
-}
-
-void CallGraph::addToCallGraph(Function *F) {
-  CallGraphNode *Node = getOrInsertFunction(F);
-
-  // If this function has external linkage, anything could call it.
-  if (!F->hasLocalLinkage()) {
-    ExternalCallingNode->addCalledFunction(CallSite(), Node);
-
-    // Found the entry point?
-    if (F->getName() == "main") {
-      if (Root) // Found multiple external mains?  Don't pick one.
-        Root = ExternalCallingNode;
-      else
-        Root = Node; // Found a main, keep track of it!
-    }
-  }
-
-  // If this function has its address taken, anything could call it.
-  if (F->hasAddressTaken())
-    ExternalCallingNode->addCalledFunction(CallSite(), Node);
-
-  // If this function is not defined in this translation unit, it could call
-  // anything.
-  if (F->isDeclaration() && !F->isIntrinsic())
-    Node->addCalledFunction(CallSite(), CallsExternalNode.get());
-
-  // Look for calls by this function.
-  for (Function::iterator BB = F->begin(), BBE = F->end(); BB != BBE; ++BB)
-    for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); II != IE;
-         ++II) {
-      CallSite CS(cast<Value>(II));
-      if (CS) {
-        const Function *Callee = CS.getCalledFunction();
-        if (!Callee || !Intrinsic::isLeaf(Callee->getIntrinsicID()))
-          // Indirect calls of intrinsics are not allowed so no need to check.
-          // We can be more precise here by using TargetArg returned by
-          // Intrinsic::isLeaf.
-          Node->addCalledFunction(CS, CallsExternalNode.get());
-        else if (!Callee->isIntrinsic())
-          Node->addCalledFunction(CS, getOrInsertFunction(Callee));
-      }
-    }
-}
-
-void CallGraph::print(raw_ostream &OS) const {
-  OS << "CallGraph Root is: ";
-  if (Function *F = Root->getFunction())
-    OS << F->getName() << "\n";
-  else {
-    OS << "<<null function: 0x" << Root << ">>\n";
-  }
-
-  // Print in a deterministic order by sorting CallGraphNodes by name.  We do
-  // this here to avoid slowing down the non-printing fast path.
-
-  SmallVector<CallGraphNode *, 16> Nodes;
-  Nodes.reserve(FunctionMap.size());
-
-  for (auto I = begin(), E = end(); I != E; ++I)
-    Nodes.push_back(I->second.get());
-
-  std::sort(Nodes.begin(), Nodes.end(),
-            [](CallGraphNode *LHS, CallGraphNode *RHS) {
-    if (Function *LF = LHS->getFunction())
-      if (Function *RF = RHS->getFunction())
-        return LF->getName() < RF->getName();
-
-    return RHS->getFunction() != nullptr;
-  });
-
-  for (CallGraphNode *CN : Nodes)
-    CN->print(OS);
-}
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-void CallGraph::dump() const { print(dbgs()); }
-#endif
-
-// removeFunctionFromModule - Unlink the function from this module, returning
-// it.  Because this removes the function from the module, the call graph node
-// is destroyed.  This is only valid if the function does not call any other
-// functions (ie, there are no edges in it's CGN).  The easiest way to do this
-// is to dropAllReferences before calling this.
-//
-Function *CallGraph::removeFunctionFromModule(CallGraphNode *CGN) {
-  assert(CGN->empty() && "Cannot remove function from call "
-         "graph if it references other functions!");
-  Function *F = CGN->getFunction(); // Get the function for the call graph node
-  FunctionMap.erase(F);             // Remove the call graph node from the map
-
-  M.getFunctionList().remove(F);
-  return F;
-}
-
-/// spliceFunction - Replace the function represented by this node by another.
-/// This does not rescan the body of the function, so it is suitable when
-/// splicing the body of the old function to the new while also updating all
-/// callers from old to new.
-///
-void CallGraph::spliceFunction(const Function *From, const Function *To) {
-  assert(FunctionMap.count(From) && "No CallGraphNode for function!");
-  assert(!FunctionMap.count(To) &&
-         "Pointing CallGraphNode at a function that already exists");
-  FunctionMapTy::iterator I = FunctionMap.find(From);
-  I->second->F = const_cast<Function*>(To);
-  FunctionMap[To] = std::move(I->second);
-  FunctionMap.erase(I);
-}
-
-// getOrInsertFunction - This method is identical to calling operator[], but
-// it will insert a new CallGraphNode for the specified function if one does
-// not already exist.
-CallGraphNode *CallGraph::getOrInsertFunction(const Function *F) {
-  auto &CGN = FunctionMap[F];
-  if (CGN)
-    return CGN.get();
-
-  assert((!F || F->getParent() == &M) && "Function not in current module!");
-  CGN = llvm::make_unique<CallGraphNode>(const_cast<Function *>(F));
-  return CGN.get();
-}
-
-//===----------------------------------------------------------------------===//
-// Implementations of the CallGraphNode class methods.
-//
-
-void CallGraphNode::print(raw_ostream &OS) const {
-  if (Function *F = getFunction())
-    OS << "Call graph node for function: '" << F->getName() << "'";
-  else
-    OS << "Call graph node <<null function>>";
-  
-  OS << "<<" << this << ">>  #uses=" << getNumReferences() << '\n';
-
-  for (const_iterator I = begin(), E = end(); I != E; ++I) {
-    OS << "  CS<" << I->first << "> calls ";
-    if (Function *FI = I->second->getFunction())
-      OS << "function '" << FI->getName() <<"'\n";
-    else
-      OS << "external node\n";
-  }
-  OS << '\n';
-}
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-void CallGraphNode::dump() const { print(dbgs()); }
-#endif
-
-/// removeCallEdgeFor - This method removes the edge in the node for the
-/// specified call site.  Note that this method takes linear time, so it
-/// should be used sparingly.
-void CallGraphNode::removeCallEdgeFor(CallSite CS) {
-  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
-    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
-    if (I->first == CS.getInstruction()) {
-      I->second->DropRef();
-      *I = CalledFunctions.back();
-      CalledFunctions.pop_back();
-      return;
-    }
-  }
-}
-
-// removeAnyCallEdgeTo - This method removes any call edges from this node to
-// the specified callee function.  This takes more time to execute than
-// removeCallEdgeTo, so it should not be used unless necessary.
-void CallGraphNode::removeAnyCallEdgeTo(CallGraphNode *Callee) {
-  for (unsigned i = 0, e = CalledFunctions.size(); i != e; ++i)
-    if (CalledFunctions[i].second == Callee) {
-      Callee->DropRef();
-      CalledFunctions[i] = CalledFunctions.back();
-      CalledFunctions.pop_back();
-      --i; --e;
-    }
-}
-
-/// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite
-/// from this node to the specified callee function.
-void CallGraphNode::removeOneAbstractEdgeTo(CallGraphNode *Callee) {
-  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
-    assert(I != CalledFunctions.end() && "Cannot find callee to remove!");
-    CallRecord &CR = *I;
-    if (CR.second == Callee && CR.first == nullptr) {
-      Callee->DropRef();
-      *I = CalledFunctions.back();
-      CalledFunctions.pop_back();
-      return;
-    }
-  }
-}
-
-/// replaceCallEdge - This method replaces the edge in the node for the
-/// specified call site with a new one.  Note that this method takes linear
-/// time, so it should be used sparingly.
-void CallGraphNode::replaceCallEdge(CallSite CS,
-                                    CallSite NewCS, CallGraphNode *NewNode){
-  for (CalledFunctionsVector::iterator I = CalledFunctions.begin(); ; ++I) {
-    assert(I != CalledFunctions.end() && "Cannot find callsite to remove!");
-    if (I->first == CS.getInstruction()) {
-      I->second->DropRef();
-      I->first = NewCS.getInstruction();
-      I->second = NewNode;
-      NewNode->AddRef();
-      return;
-    }
-  }
-}
-
-//===----------------------------------------------------------------------===//
-// Out-of-line definitions of CallGraphAnalysis class members.
-//
-
-char CallGraphAnalysis::PassID;
-
-//===----------------------------------------------------------------------===//
-// Implementations of the CallGraphWrapperPass class methods.
-//
-
-CallGraphWrapperPass::CallGraphWrapperPass() : ModulePass(ID) {
-  initializeCallGraphWrapperPassPass(*PassRegistry::getPassRegistry());
-}
-
-CallGraphWrapperPass::~CallGraphWrapperPass() {}
-
-void CallGraphWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesAll();
-}
-
-bool CallGraphWrapperPass::runOnModule(Module &M) {
-  // All the real work is done in the constructor for the CallGraph.
-  G.reset(new CallGraph(M));
-  return false;
-}
-
-INITIALIZE_PASS(CallGraphWrapperPass, "basiccg", "CallGraph Construction",
-                false, true)
-
-char CallGraphWrapperPass::ID = 0;
-
-void CallGraphWrapperPass::releaseMemory() { G.reset(); }
-
-void CallGraphWrapperPass::print(raw_ostream &OS, const Module *) const {
-  if (!G) {
-    OS << "No call graph has been built!\n";
-    return;
-  }
-
-  // Just delegate.
-  G->print(OS);
-}
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-void CallGraphWrapperPass::dump() const { print(dbgs(), nullptr); }
-#endif
Index: llvm/trunk/lib/Analysis/IPA/CallGraphSCCPass.cpp
===================================================================
--- llvm/trunk/lib/Analysis/IPA/CallGraphSCCPass.cpp
+++ llvm/trunk/lib/Analysis/IPA/CallGraphSCCPass.cpp
@@ -1,632 +0,0 @@
-//===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements the CallGraphSCCPass class, which is used for passes
-// which are implemented as bottom-up traversals on the call graph.  Because
-// there may be cycles in the call graph, passes of this type operate on the
-// call-graph in SCC order: that is, they process function bottom-up, except for
-// recursive functions, which they process all at once.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/CallGraphSCCPass.h"
-#include "llvm/ADT/SCCIterator.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/CallGraph.h"
-#include "llvm/IR/Function.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/LLVMContext.h"
-#include "llvm/IR/LegacyPassManagers.h"
-#include "llvm/Support/CommandLine.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/Timer.h"
-#include "llvm/Support/raw_ostream.h"
-using namespace llvm;
-
-#define DEBUG_TYPE "cgscc-passmgr"
-
-static cl::opt<unsigned> 
-MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
-
-STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
-
-//===----------------------------------------------------------------------===//
-// CGPassManager
-//
-/// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
-
-namespace {
-
-class CGPassManager : public ModulePass, public PMDataManager {
-public:
-  static char ID;
-  explicit CGPassManager() 
-    : ModulePass(ID), PMDataManager() { }
-
-  /// Execute all of the passes scheduled for execution.  Keep track of
-  /// whether any of the passes modifies the module, and if so, return true.
-  bool runOnModule(Module &M) override;
-
-  using ModulePass::doInitialization;
-  using ModulePass::doFinalization;
-
-  bool doInitialization(CallGraph &CG);
-  bool doFinalization(CallGraph &CG);
-
-  /// Pass Manager itself does not invalidate any analysis info.
-  void getAnalysisUsage(AnalysisUsage &Info) const override {
-    // CGPassManager walks SCC and it needs CallGraph.
-    Info.addRequired<CallGraphWrapperPass>();
-    Info.setPreservesAll();
-  }
-
-  const char *getPassName() const override {
-    return "CallGraph Pass Manager";
-  }
-
-  PMDataManager *getAsPMDataManager() override { return this; }
-  Pass *getAsPass() override { return this; }
-
-  // Print passes managed by this manager
-  void dumpPassStructure(unsigned Offset) override {
-    errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
-    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
-      Pass *P = getContainedPass(Index);
-      P->dumpPassStructure(Offset + 1);
-      dumpLastUses(P, Offset+1);
-    }
-  }
-
-  Pass *getContainedPass(unsigned N) {
-    assert(N < PassVector.size() && "Pass number out of range!");
-    return static_cast<Pass *>(PassVector[N]);
-  }
-
-  PassManagerType getPassManagerType() const override {
-    return PMT_CallGraphPassManager; 
-  }
-  
-private:
-  bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
-                         bool &DevirtualizedCall);
-  
-  bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
-                    CallGraph &CG, bool &CallGraphUpToDate,
-                    bool &DevirtualizedCall);
-  bool RefreshCallGraph(CallGraphSCC &CurSCC, CallGraph &CG,
-                        bool IsCheckingMode);
-};
-
-} // end anonymous namespace.
-
-char CGPassManager::ID = 0;
-
-
-bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
-                                 CallGraph &CG, bool &CallGraphUpToDate,
-                                 bool &DevirtualizedCall) {
-  bool Changed = false;
-  PMDataManager *PM = P->getAsPMDataManager();
-
-  if (!PM) {
-    CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P;
-    if (!CallGraphUpToDate) {
-      DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
-      CallGraphUpToDate = true;
-    }
-
-    {
-      TimeRegion PassTimer(getPassTimer(CGSP));
-      Changed = CGSP->runOnSCC(CurSCC);
-    }
-    
-    // After the CGSCCPass is done, when assertions are enabled, use
-    // RefreshCallGraph to verify that the callgraph was correctly updated.
-#ifndef NDEBUG
-    if (Changed)
-      RefreshCallGraph(CurSCC, CG, true);
-#endif
-    
-    return Changed;
-  }
-  
-  
-  assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
-         "Invalid CGPassManager member");
-  FPPassManager *FPP = (FPPassManager*)P;
-  
-  // Run pass P on all functions in the current SCC.
-  for (CallGraphNode *CGN : CurSCC) {
-    if (Function *F = CGN->getFunction()) {
-      dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
-      {
-        TimeRegion PassTimer(getPassTimer(FPP));
-        Changed |= FPP->runOnFunction(*F);
-      }
-      F->getContext().yield();
-    }
-  }
-  
-  // The function pass(es) modified the IR, they may have clobbered the
-  // callgraph.
-  if (Changed && CallGraphUpToDate) {
-    DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
-                 << P->getPassName() << '\n');
-    CallGraphUpToDate = false;
-  }
-  return Changed;
-}
-
-
-/// Scan the functions in the specified CFG and resync the
-/// callgraph with the call sites found in it.  This is used after
-/// FunctionPasses have potentially munged the callgraph, and can be used after
-/// CallGraphSCC passes to verify that they correctly updated the callgraph.
-///
-/// This function returns true if it devirtualized an existing function call,
-/// meaning it turned an indirect call into a direct call.  This happens when
-/// a function pass like GVN optimizes away stuff feeding the indirect call.
-/// This never happens in checking mode.
-///
-bool CGPassManager::RefreshCallGraph(CallGraphSCC &CurSCC,
-                                     CallGraph &CG, bool CheckingMode) {
-  DenseMap<Value*, CallGraphNode*> CallSites;
-  
-  DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
-               << " nodes:\n";
-        for (CallGraphNode *CGN : CurSCC)
-          CGN->dump();
-        );
-
-  bool MadeChange = false;
-  bool DevirtualizedCall = false;
-  
-  // Scan all functions in the SCC.
-  unsigned FunctionNo = 0;
-  for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
-       SCCIdx != E; ++SCCIdx, ++FunctionNo) {
-    CallGraphNode *CGN = *SCCIdx;
-    Function *F = CGN->getFunction();
-    if (!F || F->isDeclaration()) continue;
-    
-    // Walk the function body looking for call sites.  Sync up the call sites in
-    // CGN with those actually in the function.
-
-    // Keep track of the number of direct and indirect calls that were
-    // invalidated and removed.
-    unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
-    
-    // Get the set of call sites currently in the function.
-    for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
-      // If this call site is null, then the function pass deleted the call
-      // entirely and the WeakVH nulled it out.  
-      if (!I->first ||
-          // If we've already seen this call site, then the FunctionPass RAUW'd
-          // one call with another, which resulted in two "uses" in the edge
-          // list of the same call.
-          CallSites.count(I->first) ||
-
-          // If the call edge is not from a call or invoke, or it is a
-          // instrinsic call, then the function pass RAUW'd a call with 
-          // another value. This can happen when constant folding happens
-          // of well known functions etc.
-          !CallSite(I->first) ||
-          (CallSite(I->first).getCalledFunction() &&
-           CallSite(I->first).getCalledFunction()->isIntrinsic() &&
-           Intrinsic::isLeaf(
-               CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
-        assert(!CheckingMode &&
-               "CallGraphSCCPass did not update the CallGraph correctly!");
-        
-        // If this was an indirect call site, count it.
-        if (!I->second->getFunction())
-          ++NumIndirectRemoved;
-        else 
-          ++NumDirectRemoved;
-        
-        // Just remove the edge from the set of callees, keep track of whether
-        // I points to the last element of the vector.
-        bool WasLast = I + 1 == E;
-        CGN->removeCallEdge(I);
-        
-        // If I pointed to the last element of the vector, we have to bail out:
-        // iterator checking rejects comparisons of the resultant pointer with
-        // end.
-        if (WasLast)
-          break;
-        E = CGN->end();
-        continue;
-      }
-      
-      assert(!CallSites.count(I->first) &&
-             "Call site occurs in node multiple times");
-      
-      CallSite CS(I->first);
-      if (CS) {
-        Function *Callee = CS.getCalledFunction();
-        // Ignore intrinsics because they're not really function calls.
-        if (!Callee || !(Callee->isIntrinsic()))
-          CallSites.insert(std::make_pair(I->first, I->second));
-      }
-      ++I;
-    }
-    
-    // Loop over all of the instructions in the function, getting the callsites.
-    // Keep track of the number of direct/indirect calls added.
-    unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
-    
-    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
-      for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
-        CallSite CS(cast<Value>(I));
-        if (!CS) continue;
-        Function *Callee = CS.getCalledFunction();
-        if (Callee && Callee->isIntrinsic()) continue;
-        
-        // If this call site already existed in the callgraph, just verify it
-        // matches up to expectations and remove it from CallSites.
-        DenseMap<Value*, CallGraphNode*>::iterator ExistingIt =
-          CallSites.find(CS.getInstruction());
-        if (ExistingIt != CallSites.end()) {
-          CallGraphNode *ExistingNode = ExistingIt->second;
-
-          // Remove from CallSites since we have now seen it.
-          CallSites.erase(ExistingIt);
-          
-          // Verify that the callee is right.
-          if (ExistingNode->getFunction() == CS.getCalledFunction())
-            continue;
-          
-          // If we are in checking mode, we are not allowed to actually mutate
-          // the callgraph.  If this is a case where we can infer that the
-          // callgraph is less precise than it could be (e.g. an indirect call
-          // site could be turned direct), don't reject it in checking mode, and
-          // don't tweak it to be more precise.
-          if (CheckingMode && CS.getCalledFunction() &&
-              ExistingNode->getFunction() == nullptr)
-            continue;
-          
-          assert(!CheckingMode &&
-                 "CallGraphSCCPass did not update the CallGraph correctly!");
-          
-          // If not, we either went from a direct call to indirect, indirect to
-          // direct, or direct to different direct.
-          CallGraphNode *CalleeNode;
-          if (Function *Callee = CS.getCalledFunction()) {
-            CalleeNode = CG.getOrInsertFunction(Callee);
-            // Keep track of whether we turned an indirect call into a direct
-            // one.
-            if (!ExistingNode->getFunction()) {
-              DevirtualizedCall = true;
-              DEBUG(dbgs() << "  CGSCCPASSMGR: Devirtualized call to '"
-                           << Callee->getName() << "'\n");
-            }
-          } else {
-            CalleeNode = CG.getCallsExternalNode();
-          }
-
-          // Update the edge target in CGN.
-          CGN->replaceCallEdge(CS, CS, CalleeNode);
-          MadeChange = true;
-          continue;
-        }
-        
-        assert(!CheckingMode &&
-               "CallGraphSCCPass did not update the CallGraph correctly!");
-
-        // If the call site didn't exist in the CGN yet, add it.
-        CallGraphNode *CalleeNode;
-        if (Function *Callee = CS.getCalledFunction()) {
-          CalleeNode = CG.getOrInsertFunction(Callee);
-          ++NumDirectAdded;
-        } else {
-          CalleeNode = CG.getCallsExternalNode();
-          ++NumIndirectAdded;
-        }
-        
-        CGN->addCalledFunction(CS, CalleeNode);
-        MadeChange = true;
-      }
-    
-    // We scanned the old callgraph node, removing invalidated call sites and
-    // then added back newly found call sites.  One thing that can happen is
-    // that an old indirect call site was deleted and replaced with a new direct
-    // call.  In this case, we have devirtualized a call, and CGSCCPM would like
-    // to iteratively optimize the new code.  Unfortunately, we don't really
-    // have a great way to detect when this happens.  As an approximation, we
-    // just look at whether the number of indirect calls is reduced and the
-    // number of direct calls is increased.  There are tons of ways to fool this
-    // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
-    // direct call) but this is close enough.
-    if (NumIndirectRemoved > NumIndirectAdded &&
-        NumDirectRemoved < NumDirectAdded)
-      DevirtualizedCall = true;
-    
-    // After scanning this function, if we still have entries in callsites, then
-    // they are dangling pointers.  WeakVH should save us for this, so abort if
-    // this happens.
-    assert(CallSites.empty() && "Dangling pointers found in call sites map");
-    
-    // Periodically do an explicit clear to remove tombstones when processing
-    // large scc's.
-    if ((FunctionNo & 15) == 15)
-      CallSites.clear();
-  }
-
-  DEBUG(if (MadeChange) {
-          dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
-          for (CallGraphNode *CGN : CurSCC)
-            CGN->dump();
-          if (DevirtualizedCall)
-            dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
-
-         } else {
-           dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
-         }
-        );
-  (void)MadeChange;
-
-  return DevirtualizedCall;
-}
-
-/// Execute the body of the entire pass manager on the specified SCC.
-/// This keeps track of whether a function pass devirtualizes
-/// any calls and returns it in DevirtualizedCall.
-bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
-                                      bool &DevirtualizedCall) {
-  bool Changed = false;
-  
-  // Keep track of whether the callgraph is known to be up-to-date or not.
-  // The CGSSC pass manager runs two types of passes:
-  // CallGraphSCC Passes and other random function passes.  Because other
-  // random function passes are not CallGraph aware, they may clobber the
-  // call graph by introducing new calls or deleting other ones.  This flag
-  // is set to false when we run a function pass so that we know to clean up
-  // the callgraph when we need to run a CGSCCPass again.
-  bool CallGraphUpToDate = true;
-
-  // Run all passes on current SCC.
-  for (unsigned PassNo = 0, e = getNumContainedPasses();
-       PassNo != e; ++PassNo) {
-    Pass *P = getContainedPass(PassNo);
-    
-    // If we're in -debug-pass=Executions mode, construct the SCC node list,
-    // otherwise avoid constructing this string as it is expensive.
-    if (isPassDebuggingExecutionsOrMore()) {
-      std::string Functions;
-  #ifndef NDEBUG
-      raw_string_ostream OS(Functions);
-      for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
-           I != E; ++I) {
-        if (I != CurSCC.begin()) OS << ", ";
-        (*I)->print(OS);
-      }
-      OS.flush();
-  #endif
-      dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
-    }
-    dumpRequiredSet(P);
-    
-    initializeAnalysisImpl(P);
-    
-    // Actually run this pass on the current SCC.
-    Changed |= RunPassOnSCC(P, CurSCC, CG,
-                            CallGraphUpToDate, DevirtualizedCall);
-    
-    if (Changed)
-      dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
-    dumpPreservedSet(P);
-    
-    verifyPreservedAnalysis(P);      
-    removeNotPreservedAnalysis(P);
-    recordAvailableAnalysis(P);
-    removeDeadPasses(P, "", ON_CG_MSG);
-  }
-  
-  // If the callgraph was left out of date (because the last pass run was a
-  // functionpass), refresh it before we move on to the next SCC.
-  if (!CallGraphUpToDate)
-    DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
-  return Changed;
-}
-
-/// Execute all of the passes scheduled for execution.  Keep track of
-/// whether any of the passes modifies the module, and if so, return true.
-bool CGPassManager::runOnModule(Module &M) {
-  CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
-  bool Changed = doInitialization(CG);
-  
-  // Walk the callgraph in bottom-up SCC order.
-  scc_iterator<CallGraph*> CGI = scc_begin(&CG);
-
-  CallGraphSCC CurSCC(&CGI);
-  while (!CGI.isAtEnd()) {
-    // Copy the current SCC and increment past it so that the pass can hack
-    // on the SCC if it wants to without invalidating our iterator.
-    const std::vector<CallGraphNode *> &NodeVec = *CGI;
-    CurSCC.initialize(NodeVec.data(), NodeVec.data() + NodeVec.size());
-    ++CGI;
-
-    // At the top level, we run all the passes in this pass manager on the
-    // functions in this SCC.  However, we support iterative compilation in the
-    // case where a function pass devirtualizes a call to a function.  For
-    // example, it is very common for a function pass (often GVN or instcombine)
-    // to eliminate the addressing that feeds into a call.  With that improved
-    // information, we would like the call to be an inline candidate, infer
-    // mod-ref information etc.
-    //
-    // Because of this, we allow iteration up to a specified iteration count.
-    // This only happens in the case of a devirtualized call, so we only burn
-    // compile time in the case that we're making progress.  We also have a hard
-    // iteration count limit in case there is crazy code.
-    unsigned Iteration = 0;
-    bool DevirtualizedCall = false;
-    do {
-      DEBUG(if (Iteration)
-              dbgs() << "  SCCPASSMGR: Re-visiting SCC, iteration #"
-                     << Iteration << '\n');
-      DevirtualizedCall = false;
-      Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
-    } while (Iteration++ < MaxIterations && DevirtualizedCall);
-    
-    if (DevirtualizedCall)
-      DEBUG(dbgs() << "  CGSCCPASSMGR: Stopped iteration after " << Iteration
-                   << " times, due to -max-cg-scc-iterations\n");
-    
-    if (Iteration > MaxSCCIterations)
-      MaxSCCIterations = Iteration;
-    
-  }
-  Changed |= doFinalization(CG);
-  return Changed;
-}
-
-
-/// Initialize CG
-bool CGPassManager::doInitialization(CallGraph &CG) {
-  bool Changed = false;
-  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {  
-    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
-      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
-             "Invalid CGPassManager member");
-      Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
-    } else {
-      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
-    }
-  }
-  return Changed;
-}
-
-/// Finalize CG
-bool CGPassManager::doFinalization(CallGraph &CG) {
-  bool Changed = false;
-  for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {  
-    if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
-      assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
-             "Invalid CGPassManager member");
-      Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
-    } else {
-      Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
-    }
-  }
-  return Changed;
-}
-
-//===----------------------------------------------------------------------===//
-// CallGraphSCC Implementation
-//===----------------------------------------------------------------------===//
-
-/// This informs the SCC and the pass manager that the specified
-/// Old node has been deleted, and New is to be used in its place.
-void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
-  assert(Old != New && "Should not replace node with self");
-  for (unsigned i = 0; ; ++i) {
-    assert(i != Nodes.size() && "Node not in SCC");
-    if (Nodes[i] != Old) continue;
-    Nodes[i] = New;
-    break;
-  }
-  
-  // Update the active scc_iterator so that it doesn't contain dangling
-  // pointers to the old CallGraphNode.
-  scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
-  CGI->ReplaceNode(Old, New);
-}
-
-
-//===----------------------------------------------------------------------===//
-// CallGraphSCCPass Implementation
-//===----------------------------------------------------------------------===//
-
-/// Assign pass manager to manage this pass.
-void CallGraphSCCPass::assignPassManager(PMStack &PMS,
-                                         PassManagerType PreferredType) {
-  // Find CGPassManager 
-  while (!PMS.empty() &&
-         PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
-    PMS.pop();
-
-  assert(!PMS.empty() && "Unable to handle Call Graph Pass");
-  CGPassManager *CGP;
-  
-  if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
-    CGP = (CGPassManager*)PMS.top();
-  else {
-    // Create new Call Graph SCC Pass Manager if it does not exist. 
-    assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
-    PMDataManager *PMD = PMS.top();
-
-    // [1] Create new Call Graph Pass Manager
-    CGP = new CGPassManager();
-
-    // [2] Set up new manager's top level manager
-    PMTopLevelManager *TPM = PMD->getTopLevelManager();
-    TPM->addIndirectPassManager(CGP);
-
-    // [3] Assign manager to manage this new manager. This may create
-    // and push new managers into PMS
-    Pass *P = CGP;
-    TPM->schedulePass(P);
-
-    // [4] Push new manager into PMS
-    PMS.push(CGP);
-  }
-
-  CGP->add(this);
-}
-
-/// For this class, we declare that we require and preserve the call graph.
-/// If the derived class implements this method, it should
-/// always explicitly call the implementation here.
-void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequired<CallGraphWrapperPass>();
-  AU.addPreserved<CallGraphWrapperPass>();
-}
-
-
-//===----------------------------------------------------------------------===//
-// PrintCallGraphPass Implementation
-//===----------------------------------------------------------------------===//
-
-namespace {
-  /// PrintCallGraphPass - Print a Module corresponding to a call graph.
-  ///
-  class PrintCallGraphPass : public CallGraphSCCPass {
-    std::string Banner;
-    raw_ostream &Out;       // raw_ostream to print on.
-    
-  public:
-    static char ID;
-    PrintCallGraphPass(const std::string &B, raw_ostream &o)
-      : CallGraphSCCPass(ID), Banner(B), Out(o) {}
-
-    void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.setPreservesAll();
-    }
-
-    bool runOnSCC(CallGraphSCC &SCC) override {
-      Out << Banner;
-      for (CallGraphNode *CGN : SCC) {
-        if (CGN->getFunction())
-          CGN->getFunction()->print(Out);
-        else
-          Out << "\nPrinting <null> Function\n";
-      }
-      return false;
-    }
-  };
-  
-} // end anonymous namespace.
-
-char PrintCallGraphPass::ID = 0;
-
-Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &O,
-                                          const std::string &Banner) const {
-  return new PrintCallGraphPass(Banner, O);
-}
-
Index: llvm/trunk/lib/Analysis/IPA/CallPrinter.cpp
===================================================================
--- llvm/trunk/lib/Analysis/IPA/CallPrinter.cpp
+++ llvm/trunk/lib/Analysis/IPA/CallPrinter.cpp
@@ -1,92 +0,0 @@
-//===- CallPrinter.cpp - DOT printer for call graph -----------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file defines '-dot-callgraph', which emit a callgraph.<fnname>.dot
-// containing the call graph of a module.
-//
-// There is also a pass available to directly call dotty ('-view-callgraph').
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/CallGraph.h"
-#include "llvm/Analysis/CallPrinter.h"
-#include "llvm/Analysis/DOTGraphTraitsPass.h"
-
-using namespace llvm;
-
-namespace llvm {
-
-template <> struct DOTGraphTraits<CallGraph *> : public DefaultDOTGraphTraits {
-  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
-
-  static std::string getGraphName(CallGraph *Graph) { return "Call graph"; }
-
-  std::string getNodeLabel(CallGraphNode *Node, CallGraph *Graph) {
-    if (Function *Func = Node->getFunction())
-      return Func->getName();
-
-    return "external node";
-  }
-};
-
-struct AnalysisCallGraphWrapperPassTraits {
-  static CallGraph *getGraph(CallGraphWrapperPass *P) {
-    return &P->getCallGraph();
-  }
-};
-
-} // end llvm namespace
-
-namespace {
-
-struct CallGraphViewer
-    : public DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
-                                        AnalysisCallGraphWrapperPassTraits> {
-  static char ID;
-
-  CallGraphViewer()
-      : DOTGraphTraitsModuleViewer<CallGraphWrapperPass, true, CallGraph *,
-                                   AnalysisCallGraphWrapperPassTraits>(
-            "callgraph", ID) {
-    initializeCallGraphViewerPass(*PassRegistry::getPassRegistry());
-  }
-};
-
-struct CallGraphPrinter : public DOTGraphTraitsModulePrinter<
-                              CallGraphWrapperPass, true, CallGraph *,
-                              AnalysisCallGraphWrapperPassTraits> {
-  static char ID;
-
-  CallGraphPrinter()
-      : DOTGraphTraitsModulePrinter<CallGraphWrapperPass, true, CallGraph *,
-                                    AnalysisCallGraphWrapperPassTraits>(
-            "callgraph", ID) {
-    initializeCallGraphPrinterPass(*PassRegistry::getPassRegistry());
-  }
-};
-
-} // end anonymous namespace
-
-char CallGraphViewer::ID = 0;
-INITIALIZE_PASS(CallGraphViewer, "view-callgraph", "View call graph", false,
-                false)
-
-char CallGraphPrinter::ID = 0;
-INITIALIZE_PASS(CallGraphPrinter, "dot-callgraph",
-                "Print call graph to 'dot' file", false, false)
-
-// Create methods available outside of this file, to use them
-// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
-// the link time optimization.
-
-ModulePass *llvm::createCallGraphViewerPass() { return new CallGraphViewer(); }
-
-ModulePass *llvm::createCallGraphPrinterPass() {
-  return new CallGraphPrinter();
-}
Index: llvm/trunk/lib/Analysis/IPA/GlobalsModRef.cpp
===================================================================
--- llvm/trunk/lib/Analysis/IPA/GlobalsModRef.cpp
+++ llvm/trunk/lib/Analysis/IPA/GlobalsModRef.cpp
@@ -1,798 +0,0 @@
-//===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This simple pass provides alias and mod/ref information for global values
-// that do not have their address taken, and keeps track of whether functions
-// read or write memory (are "pure").  For this simple (but very common) case,
-// we can provide pretty accurate and useful information.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/GlobalsModRef.h"
-#include "llvm/ADT/SCCIterator.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
-#include "llvm/Analysis/ValueTracking.h"
-#include "llvm/IR/DerivedTypes.h"
-#include "llvm/IR/InstIterator.h"
-#include "llvm/IR/Instructions.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/Module.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/CommandLine.h"
-using namespace llvm;
-
-#define DEBUG_TYPE "globalsmodref-aa"
-
-STATISTIC(NumNonAddrTakenGlobalVars,
-          "Number of global vars without address taken");
-STATISTIC(NumNonAddrTakenFunctions,"Number of functions without address taken");
-STATISTIC(NumNoMemFunctions, "Number of functions that do not access memory");
-STATISTIC(NumReadMemFunctions, "Number of functions that only read memory");
-STATISTIC(NumIndirectGlobalVars, "Number of indirect global objects");
-
-// An option to enable unsafe alias results from the GlobalsModRef analysis.
-// When enabled, GlobalsModRef will provide no-alias results which in extremely
-// rare cases may not be conservatively correct. In particular, in the face of
-// transforms which cause assymetry between how effective GetUnderlyingObject
-// is for two pointers, it may produce incorrect results.
-//
-// These unsafe results have been returned by GMR for many years without
-// causing significant issues in the wild and so we provide a mechanism to
-// re-enable them for users of LLVM that have a particular performance
-// sensitivity and no known issues. The option also makes it easy to evaluate
-// the performance impact of these results.
-static cl::opt<bool> EnableUnsafeGlobalsModRefAliasResults(
-    "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden);
-
-/// The mod/ref information collected for a particular function.
-///
-/// We collect information about mod/ref behavior of a function here, both in
-/// general and as pertains to specific globals. We only have this detailed
-/// information when we know *something* useful about the behavior. If we
-/// saturate to fully general mod/ref, we remove the info for the function.
-class GlobalsModRef::FunctionInfo {
-  typedef SmallDenseMap<const GlobalValue *, ModRefInfo, 16> GlobalInfoMapType;
-
-  /// Build a wrapper struct that has 8-byte alignment. All heap allocations
-  /// should provide this much alignment at least, but this makes it clear we
-  /// specifically rely on this amount of alignment.
-  struct LLVM_ALIGNAS(8) AlignedMap {
-    AlignedMap() {}
-    AlignedMap(const AlignedMap &Arg) : Map(Arg.Map) {}
-    GlobalInfoMapType Map;
-  };
-
-  /// Pointer traits for our aligned map.
-  struct AlignedMapPointerTraits {
-    static inline void *getAsVoidPointer(AlignedMap *P) { return P; }
-    static inline AlignedMap *getFromVoidPointer(void *P) {
-      return (AlignedMap *)P;
-    }
-    enum { NumLowBitsAvailable = 3 };
-    static_assert(AlignOf<AlignedMap>::Alignment >= (1 << NumLowBitsAvailable),
-                  "AlignedMap insufficiently aligned to have enough low bits.");
-  };
-
-  /// The bit that flags that this function may read any global. This is
-  /// chosen to mix together with ModRefInfo bits.
-  enum { MayReadAnyGlobal = 4 };
-
-  /// Checks to document the invariants of the bit packing here.
-  static_assert((MayReadAnyGlobal & MRI_ModRef) == 0,
-                "ModRef and the MayReadAnyGlobal flag bits overlap.");
-  static_assert(((MayReadAnyGlobal | MRI_ModRef) >>
-                 AlignedMapPointerTraits::NumLowBitsAvailable) == 0,
-                "Insufficient low bits to store our flag and ModRef info.");
-
-public:
-  FunctionInfo() : Info() {}
-  ~FunctionInfo() {
-    delete Info.getPointer();
-  }
-  // Spell out the copy ond move constructors and assignment operators to get
-  // deep copy semantics and correct move semantics in the face of the
-  // pointer-int pair.
-  FunctionInfo(const FunctionInfo &Arg)
-      : Info(nullptr, Arg.Info.getInt()) {
-    if (const auto *ArgPtr = Arg.Info.getPointer())
-      Info.setPointer(new AlignedMap(*ArgPtr));
-  }
-  FunctionInfo(FunctionInfo &&Arg)
-      : Info(Arg.Info.getPointer(), Arg.Info.getInt()) {
-    Arg.Info.setPointerAndInt(nullptr, 0);
-  }
-  FunctionInfo &operator=(const FunctionInfo &RHS) {
-    delete Info.getPointer();
-    Info.setPointerAndInt(nullptr, RHS.Info.getInt());
-    if (const auto *RHSPtr = RHS.Info.getPointer())
-      Info.setPointer(new AlignedMap(*RHSPtr));
-    return *this;
-  }
-  FunctionInfo &operator=(FunctionInfo &&RHS) {
-    delete Info.getPointer();
-    Info.setPointerAndInt(RHS.Info.getPointer(), RHS.Info.getInt());
-    RHS.Info.setPointerAndInt(nullptr, 0);
-    return *this;
-  }
-
-  /// Returns the \c ModRefInfo info for this function.
-  ModRefInfo getModRefInfo() const {
-    return ModRefInfo(Info.getInt() & MRI_ModRef);
-  }
-
-  /// Adds new \c ModRefInfo for this function to its state.
-  void addModRefInfo(ModRefInfo NewMRI) {
-    Info.setInt(Info.getInt() | NewMRI);
-  }
-
-  /// Returns whether this function may read any global variable, and we don't
-  /// know which global.
-  bool mayReadAnyGlobal() const { return Info.getInt() & MayReadAnyGlobal; }
-
-  /// Sets this function as potentially reading from any global.
-  void setMayReadAnyGlobal() { Info.setInt(Info.getInt() | MayReadAnyGlobal); }
-
-  /// Returns the \c ModRefInfo info for this function w.r.t. a particular
-  /// global, which may be more precise than the general information above.
-  ModRefInfo getModRefInfoForGlobal(const GlobalValue &GV) const {
-    ModRefInfo GlobalMRI = mayReadAnyGlobal() ? MRI_Ref : MRI_NoModRef;
-    if (AlignedMap *P = Info.getPointer()) {
-      auto I = P->Map.find(&GV);
-      if (I != P->Map.end())
-        GlobalMRI = ModRefInfo(GlobalMRI | I->second);
-    }
-    return GlobalMRI;
-  }
-
-  /// Add mod/ref info from another function into ours, saturating towards
-  /// MRI_ModRef.
-  void addFunctionInfo(const FunctionInfo &FI) {
-    addModRefInfo(FI.getModRefInfo());
-
-    if (FI.mayReadAnyGlobal())
-      setMayReadAnyGlobal();
-
-    if (AlignedMap *P = FI.Info.getPointer())
-      for (const auto &G : P->Map)
-        addModRefInfoForGlobal(*G.first, G.second);
-  }
-
-  void addModRefInfoForGlobal(const GlobalValue &GV, ModRefInfo NewMRI) {
-    AlignedMap *P = Info.getPointer();
-    if (!P) {
-      P = new AlignedMap();
-      Info.setPointer(P);
-    }
-    auto &GlobalMRI = P->Map[&GV];
-    GlobalMRI = ModRefInfo(GlobalMRI | NewMRI);
-  }
-
-  /// Clear a global's ModRef info. Should be used when a global is being
-  /// deleted.
-  void eraseModRefInfoForGlobal(const GlobalValue &GV) {
-    if (AlignedMap *P = Info.getPointer())
-      P->Map.erase(&GV);
-  }
-
-private:
-  /// All of the information is encoded into a single pointer, with a three bit
-  /// integer in the low three bits. The high bit provides a flag for when this
-  /// function may read any global. The low two bits are the ModRefInfo. And
-  /// the pointer, when non-null, points to a map from GlobalValue to
-  /// ModRefInfo specific to that GlobalValue.
-  PointerIntPair<AlignedMap *, 3, unsigned, AlignedMapPointerTraits> Info;
-};
-
-void GlobalsModRef::DeletionCallbackHandle::deleted() {
-  Value *V = getValPtr();
-  if (auto *F = dyn_cast<Function>(V))
-    GMR.FunctionInfos.erase(F);
-
-  if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
-    if (GMR.NonAddressTakenGlobals.erase(GV)) {
-      // This global might be an indirect global.  If so, remove it and
-      // remove any AllocRelatedValues for it.
-      if (GMR.IndirectGlobals.erase(GV)) {
-        // Remove any entries in AllocsForIndirectGlobals for this global.
-        for (auto I = GMR.AllocsForIndirectGlobals.begin(),
-                  E = GMR.AllocsForIndirectGlobals.end();
-             I != E; ++I)
-          if (I->second == GV)
-            GMR.AllocsForIndirectGlobals.erase(I);
-      }
-
-      // Scan the function info we have collected and remove this global
-      // from all of them.
-      for (auto &FIPair : GMR.FunctionInfos)
-        FIPair.second.eraseModRefInfoForGlobal(*GV);
-    }
-  }
-
-  // If this is an allocation related to an indirect global, remove it.
-  GMR.AllocsForIndirectGlobals.erase(V);
-
-  // And clear out the handle.
-  setValPtr(nullptr);
-  GMR.Handles.erase(I);
-  // This object is now destroyed!
-}
-
-char GlobalsModRef::ID = 0;
-INITIALIZE_AG_PASS_BEGIN(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
-                         "Simple mod/ref analysis for globals", false, true,
-                         false)
-INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
-INITIALIZE_AG_PASS_END(GlobalsModRef, AliasAnalysis, "globalsmodref-aa",
-                       "Simple mod/ref analysis for globals", false, true,
-                       false)
-
-Pass *llvm::createGlobalsModRefPass() { return new GlobalsModRef(); }
-
-GlobalsModRef::GlobalsModRef() : ModulePass(ID) {
-  initializeGlobalsModRefPass(*PassRegistry::getPassRegistry());
-}
-
-FunctionModRefBehavior GlobalsModRef::getModRefBehavior(const Function *F) {
-  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
-
-  if (FunctionInfo *FI = getFunctionInfo(F)) {
-    if (FI->getModRefInfo() == MRI_NoModRef)
-      Min = FMRB_DoesNotAccessMemory;
-    else if ((FI->getModRefInfo() & MRI_Mod) == 0)
-      Min = FMRB_OnlyReadsMemory;
-  }
-
-  return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(F) & Min);
-}
-
-FunctionModRefBehavior GlobalsModRef::getModRefBehavior(ImmutableCallSite CS) {
-  FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
-
-  if (const Function *F = CS.getCalledFunction())
-    if (FunctionInfo *FI = getFunctionInfo(F)) {
-      if (FI->getModRefInfo() == MRI_NoModRef)
-        Min = FMRB_DoesNotAccessMemory;
-      else if ((FI->getModRefInfo() & MRI_Mod) == 0)
-        Min = FMRB_OnlyReadsMemory;
-    }
-
-  return FunctionModRefBehavior(AliasAnalysis::getModRefBehavior(CS) & Min);
-}
-
-/// Returns the function info for the function, or null if we don't have
-/// anything useful to say about it.
-GlobalsModRef::FunctionInfo *GlobalsModRef::getFunctionInfo(const Function *F) {
-  auto I = FunctionInfos.find(F);
-  if (I != FunctionInfos.end())
-    return &I->second;
-  return nullptr;
-}
-
-/// AnalyzeGlobals - Scan through the users of all of the internal
-/// GlobalValue's in the program.  If none of them have their "address taken"
-/// (really, their address passed to something nontrivial), record this fact,
-/// and record the functions that they are used directly in.
-void GlobalsModRef::AnalyzeGlobals(Module &M) {
-  SmallPtrSet<Function *, 64> TrackedFunctions;
-  for (Function &F : M)
-    if (F.hasLocalLinkage())
-      if (!AnalyzeUsesOfPointer(&F)) {
-        // Remember that we are tracking this global.
-        NonAddressTakenGlobals.insert(&F);
-        TrackedFunctions.insert(&F);
-        Handles.emplace_front(*this, &F);
-        Handles.front().I = Handles.begin();
-        ++NumNonAddrTakenFunctions;
-      }
-
-  SmallPtrSet<Function *, 64> Readers, Writers;
-  for (GlobalVariable &GV : M.globals())
-    if (GV.hasLocalLinkage()) {
-      if (!AnalyzeUsesOfPointer(&GV, &Readers,
-                                GV.isConstant() ? nullptr : &Writers)) {
-        // Remember that we are tracking this global, and the mod/ref fns
-        NonAddressTakenGlobals.insert(&GV);
-        Handles.emplace_front(*this, &GV);
-        Handles.front().I = Handles.begin();
-
-        for (Function *Reader : Readers) {
-          if (TrackedFunctions.insert(Reader).second) {
-            Handles.emplace_front(*this, Reader);
-            Handles.front().I = Handles.begin();
-          }
-          FunctionInfos[Reader].addModRefInfoForGlobal(GV, MRI_Ref);
-        }
-
-        if (!GV.isConstant()) // No need to keep track of writers to constants
-          for (Function *Writer : Writers) {
-            if (TrackedFunctions.insert(Writer).second) {
-              Handles.emplace_front(*this, Writer);
-              Handles.front().I = Handles.begin();
-            }
-            FunctionInfos[Writer].addModRefInfoForGlobal(GV, MRI_Mod);
-          }
-        ++NumNonAddrTakenGlobalVars;
-
-        // If this global holds a pointer type, see if it is an indirect global.
-        if (GV.getType()->getElementType()->isPointerTy() &&
-            AnalyzeIndirectGlobalMemory(&GV))
-          ++NumIndirectGlobalVars;
-      }
-      Readers.clear();
-      Writers.clear();
-    }
-}
-
-/// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
-/// If this is used by anything complex (i.e., the address escapes), return
-/// true.  Also, while we are at it, keep track of those functions that read and
-/// write to the value.
-///
-/// If OkayStoreDest is non-null, stores into this global are allowed.
-bool GlobalsModRef::AnalyzeUsesOfPointer(Value *V,
-                                         SmallPtrSetImpl<Function *> *Readers,
-                                         SmallPtrSetImpl<Function *> *Writers,
-                                         GlobalValue *OkayStoreDest) {
-  if (!V->getType()->isPointerTy())
-    return true;
-
-  for (Use &U : V->uses()) {
-    User *I = U.getUser();
-    if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
-      if (Readers)
-        Readers->insert(LI->getParent()->getParent());
-    } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
-      if (V == SI->getOperand(1)) {
-        if (Writers)
-          Writers->insert(SI->getParent()->getParent());
-      } else if (SI->getOperand(1) != OkayStoreDest) {
-        return true; // Storing the pointer
-      }
-    } else if (Operator::getOpcode(I) == Instruction::GetElementPtr) {
-      if (AnalyzeUsesOfPointer(I, Readers, Writers))
-        return true;
-    } else if (Operator::getOpcode(I) == Instruction::BitCast) {
-      if (AnalyzeUsesOfPointer(I, Readers, Writers, OkayStoreDest))
-        return true;
-    } else if (auto CS = CallSite(I)) {
-      // Make sure that this is just the function being called, not that it is
-      // passing into the function.
-      if (!CS.isCallee(&U)) {
-        // Detect calls to free.
-        if (isFreeCall(I, TLI)) {
-          if (Writers)
-            Writers->insert(CS->getParent()->getParent());
-        } else {
-          return true; // Argument of an unknown call.
-        }
-      }
-    } else if (ICmpInst *ICI = dyn_cast<ICmpInst>(I)) {
-      if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
-        return true; // Allow comparison against null.
-    } else {
-      return true;
-    }
-  }
-
-  return false;
-}
-
-/// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
-/// which holds a pointer type.  See if the global always points to non-aliased
-/// heap memory: that is, all initializers of the globals are allocations, and
-/// those allocations have no use other than initialization of the global.
-/// Further, all loads out of GV must directly use the memory, not store the
-/// pointer somewhere.  If this is true, we consider the memory pointed to by
-/// GV to be owned by GV and can disambiguate other pointers from it.
-bool GlobalsModRef::AnalyzeIndirectGlobalMemory(GlobalValue *GV) {
-  // Keep track of values related to the allocation of the memory, f.e. the
-  // value produced by the malloc call and any casts.
-  std::vector<Value *> AllocRelatedValues;
-
-  // Walk the user list of the global.  If we find anything other than a direct
-  // load or store, bail out.
-  for (User *U : GV->users()) {
-    if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
-      // The pointer loaded from the global can only be used in simple ways:
-      // we allow addressing of it and loading storing to it.  We do *not* allow
-      // storing the loaded pointer somewhere else or passing to a function.
-      if (AnalyzeUsesOfPointer(LI))
-        return false; // Loaded pointer escapes.
-      // TODO: Could try some IP mod/ref of the loaded pointer.
-    } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
-      // Storing the global itself.
-      if (SI->getOperand(0) == GV)
-        return false;
-
-      // If storing the null pointer, ignore it.
-      if (isa<ConstantPointerNull>(SI->getOperand(0)))
-        continue;
-
-      // Check the value being stored.
-      Value *Ptr = GetUnderlyingObject(SI->getOperand(0),
-                                       GV->getParent()->getDataLayout());
-
-      if (!isAllocLikeFn(Ptr, TLI))
-        return false; // Too hard to analyze.
-
-      // Analyze all uses of the allocation.  If any of them are used in a
-      // non-simple way (e.g. stored to another global) bail out.
-      if (AnalyzeUsesOfPointer(Ptr, /*Readers*/ nullptr, /*Writers*/ nullptr,
-                               GV))
-        return false; // Loaded pointer escapes.
-
-      // Remember that this allocation is related to the indirect global.
-      AllocRelatedValues.push_back(Ptr);
-    } else {
-      // Something complex, bail out.
-      return false;
-    }
-  }
-
-  // Okay, this is an indirect global.  Remember all of the allocations for
-  // this global in AllocsForIndirectGlobals.
-  while (!AllocRelatedValues.empty()) {
-    AllocsForIndirectGlobals[AllocRelatedValues.back()] = GV;
-    Handles.emplace_front(*this, AllocRelatedValues.back());
-    Handles.front().I = Handles.begin();
-    AllocRelatedValues.pop_back();
-  }
-  IndirectGlobals.insert(GV);
-  Handles.emplace_front(*this, GV);
-  Handles.front().I = Handles.begin();
-  return true;
-}
-
-/// AnalyzeCallGraph - At this point, we know the functions where globals are
-/// immediately stored to and read from.  Propagate this information up the call
-/// graph to all callers and compute the mod/ref info for all memory for each
-/// function.
-void GlobalsModRef::AnalyzeCallGraph(CallGraph &CG, Module &M) {
-  // We do a bottom-up SCC traversal of the call graph.  In other words, we
-  // visit all callees before callers (leaf-first).
-  for (scc_iterator<CallGraph *> I = scc_begin(&CG); !I.isAtEnd(); ++I) {
-    const std::vector<CallGraphNode *> &SCC = *I;
-    assert(!SCC.empty() && "SCC with no functions?");
-
-    if (!SCC[0]->getFunction()) {
-      // Calls externally - can't say anything useful.  Remove any existing
-      // function records (may have been created when scanning globals).
-      for (auto *Node : SCC)
-        FunctionInfos.erase(Node->getFunction());
-      continue;
-    }
-
-    FunctionInfo &FI = FunctionInfos[SCC[0]->getFunction()];
-    bool KnowNothing = false;
-
-    // Collect the mod/ref properties due to called functions.  We only compute
-    // one mod-ref set.
-    for (unsigned i = 0, e = SCC.size(); i != e && !KnowNothing; ++i) {
-      Function *F = SCC[i]->getFunction();
-      if (!F) {
-        KnowNothing = true;
-        break;
-      }
-
-      if (F->isDeclaration()) {
-        // Try to get mod/ref behaviour from function attributes.
-        if (F->doesNotAccessMemory()) {
-          // Can't do better than that!
-        } else if (F->onlyReadsMemory()) {
-          FI.addModRefInfo(MRI_Ref);
-          if (!F->isIntrinsic())
-            // This function might call back into the module and read a global -
-            // consider every global as possibly being read by this function.
-            FI.setMayReadAnyGlobal();
-        } else {
-          FI.addModRefInfo(MRI_ModRef);
-          // Can't say anything useful unless it's an intrinsic - they don't
-          // read or write global variables of the kind considered here.
-          KnowNothing = !F->isIntrinsic();
-        }
-        continue;
-      }
-
-      for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end();
-           CI != E && !KnowNothing; ++CI)
-        if (Function *Callee = CI->second->getFunction()) {
-          if (FunctionInfo *CalleeFI = getFunctionInfo(Callee)) {
-            // Propagate function effect up.
-            FI.addFunctionInfo(*CalleeFI);
-          } else {
-            // Can't say anything about it.  However, if it is inside our SCC,
-            // then nothing needs to be done.
-            CallGraphNode *CalleeNode = CG[Callee];
-            if (std::find(SCC.begin(), SCC.end(), CalleeNode) == SCC.end())
-              KnowNothing = true;
-          }
-        } else {
-          KnowNothing = true;
-        }
-    }
-
-    // If we can't say anything useful about this SCC, remove all SCC functions
-    // from the FunctionInfos map.
-    if (KnowNothing) {
-      for (auto *Node : SCC)
-        FunctionInfos.erase(Node->getFunction());
-      continue;
-    }
-
-    // Scan the function bodies for explicit loads or stores.
-    for (auto *Node : SCC) {
-      if (FI.getModRefInfo() == MRI_ModRef)
-        break; // The mod/ref lattice saturates here.
-      for (Instruction &I : instructions(Node->getFunction())) {
-        if (FI.getModRefInfo() == MRI_ModRef)
-          break; // The mod/ref lattice saturates here.
-
-        // We handle calls specially because the graph-relevant aspects are
-        // handled above.
-        if (auto CS = CallSite(&I)) {
-          if (isAllocationFn(&I, TLI) || isFreeCall(&I, TLI)) {
-            // FIXME: It is completely unclear why this is necessary and not
-            // handled by the above graph code.
-            FI.addModRefInfo(MRI_ModRef);
-          } else if (Function *Callee = CS.getCalledFunction()) {
-            // The callgraph doesn't include intrinsic calls.
-            if (Callee->isIntrinsic()) {
-              FunctionModRefBehavior Behaviour =
-                  AliasAnalysis::getModRefBehavior(Callee);
-              FI.addModRefInfo(ModRefInfo(Behaviour & MRI_ModRef));
-            }
-          }
-          continue;
-        }
-
-        // All non-call instructions we use the primary predicates for whether
-        // thay read or write memory.
-        if (I.mayReadFromMemory())
-          FI.addModRefInfo(MRI_Ref);
-        if (I.mayWriteToMemory())
-          FI.addModRefInfo(MRI_Mod);
-      }
-    }
-
-    if ((FI.getModRefInfo() & MRI_Mod) == 0)
-      ++NumReadMemFunctions;
-    if (FI.getModRefInfo() == MRI_NoModRef)
-      ++NumNoMemFunctions;
-
-    // Finally, now that we know the full effect on this SCC, clone the
-    // information to each function in the SCC.
-    for (unsigned i = 1, e = SCC.size(); i != e; ++i)
-      FunctionInfos[SCC[i]->getFunction()] = FI;
-  }
-}
-
-// There are particular cases where we can conclude no-alias between
-// a non-addr-taken global and some other underlying object. Specifically,
-// a non-addr-taken global is known to not be escaped from any function. It is
-// also incorrect for a transformation to introduce an escape of a global in
-// a way that is observable when it was not there previously. One function
-// being transformed to introduce an escape which could possibly be observed
-// (via loading from a global or the return value for example) within another
-// function is never safe. If the observation is made through non-atomic
-// operations on different threads, it is a data-race and UB. If the
-// observation is well defined, by being observed the transformation would have
-// changed program behavior by introducing the observed escape, making it an
-// invalid transform.
-//
-// This property does require that transformations which *temporarily* escape
-// a global that was not previously escaped, prior to restoring it, cannot rely
-// on the results of GMR::alias. This seems a reasonable restriction, although
-// currently there is no way to enforce it. There is also no realistic
-// optimization pass that would make this mistake. The closest example is
-// a transformation pass which does reg2mem of SSA values but stores them into
-// global variables temporarily before restoring the global variable's value.
-// This could be useful to expose "benign" races for example. However, it seems
-// reasonable to require that a pass which introduces escapes of global
-// variables in this way to either not trust AA results while the escape is
-// active, or to be forced to operate as a module pass that cannot co-exist
-// with an alias analysis such as GMR.
-bool GlobalsModRef::isNonEscapingGlobalNoAlias(const GlobalValue *GV,
-                                               const Value *V) {
-  // In order to know that the underlying object cannot alias the
-  // non-addr-taken global, we must know that it would have to be an escape.
-  // Thus if the underlying object is a function argument, a load from
-  // a global, or the return of a function, it cannot alias. We can also
-  // recurse through PHI nodes and select nodes provided all of their inputs
-  // resolve to one of these known-escaping roots.
-  SmallPtrSet<const Value *, 8> Visited;
-  SmallVector<const Value *, 8> Inputs;
-  Visited.insert(V);
-  Inputs.push_back(V);
-  int Depth = 0;
-  do {
-    const Value *Input = Inputs.pop_back_val();
-
-    if (auto *InputGV = dyn_cast<GlobalValue>(Input)) {
-      // If one input is the very global we're querying against, then we can't
-      // conclude no-alias.
-      if (InputGV == GV)
-        return false;
-
-      // Distinct GlobalVariables never alias, unless overriden or zero-sized.
-      // FIXME: The condition can be refined, but be conservative for now.
-      auto *GVar = dyn_cast<GlobalVariable>(GV);
-      auto *InputGVar = dyn_cast<GlobalVariable>(InputGV);
-      if (GVar && InputGVar &&
-          !GVar->isDeclaration() && !InputGVar->isDeclaration() &&
-          !GVar->mayBeOverridden() && !InputGVar->mayBeOverridden()) {
-        Type *GVType = GVar->getInitializer()->getType();
-        Type *InputGVType = InputGVar->getInitializer()->getType();
-        if (GVType->isSized() && InputGVType->isSized() &&
-            (DL->getTypeAllocSize(GVType) > 0) &&
-            (DL->getTypeAllocSize(InputGVType) > 0))
-          continue;
-      }
-
-      // Conservatively return false, even though we could be smarter
-      // (e.g. look through GlobalAliases).
-      return false;
-    }
-
-    if (isa<Argument>(Input) || isa<CallInst>(Input) ||
-        isa<InvokeInst>(Input)) {
-      // Arguments to functions or returns from functions are inherently
-      // escaping, so we can immediately classify those as not aliasing any
-      // non-addr-taken globals.
-      continue;
-    }
-    if (auto *LI = dyn_cast<LoadInst>(Input)) {
-      // A pointer loaded from a global would have been captured, and we know
-      // that the global is non-escaping, so no alias.
-      if (isa<GlobalValue>(GetUnderlyingObject(LI->getPointerOperand(), *DL)))
-        continue;
-
-      // Otherwise, a load could come from anywhere, so bail.
-      return false;
-    }
-
-    // Recurse through a limited number of selects and PHIs. This is an
-    // arbitrary depth of 4, lower numbers could be used to fix compile time
-    // issues if needed, but this is generally expected to be only be important
-    // for small depths.
-    if (++Depth > 4)
-      return false;
-    if (auto *SI = dyn_cast<SelectInst>(Input)) {
-      const Value *LHS = GetUnderlyingObject(SI->getTrueValue(), *DL);
-      const Value *RHS = GetUnderlyingObject(SI->getFalseValue(), *DL);
-      if (Visited.insert(LHS).second)
-        Inputs.push_back(LHS);
-      if (Visited.insert(RHS).second)
-        Inputs.push_back(RHS);
-      continue;
-    }
-    if (auto *PN = dyn_cast<PHINode>(Input)) {
-      for (const Value *Op : PN->incoming_values()) {
-        Op = GetUnderlyingObject(Op, *DL);
-        if (Visited.insert(Op).second)
-          Inputs.push_back(Op);
-      }
-      continue;
-    }
-
-    // FIXME: It would be good to handle other obvious no-alias cases here, but
-    // it isn't clear how to do so reasonbly without building a small version
-    // of BasicAA into this code. We could recurse into AliasAnalysis::alias
-    // here but that seems likely to go poorly as we're inside the
-    // implementation of such a query. Until then, just conservatievly retun
-    // false.
-    return false;
-  } while (!Inputs.empty());
-
-  // If all the inputs to V were definitively no-alias, then V is no-alias.
-  return true;
-}
-
-/// alias - If one of the pointers is to a global that we are tracking, and the
-/// other is some random pointer, we know there cannot be an alias, because the
-/// address of the global isn't taken.
-AliasResult GlobalsModRef::alias(const MemoryLocation &LocA,
-                                 const MemoryLocation &LocB) {
-  // Get the base object these pointers point to.
-  const Value *UV1 = GetUnderlyingObject(LocA.Ptr, *DL);
-  const Value *UV2 = GetUnderlyingObject(LocB.Ptr, *DL);
-
-  // If either of the underlying values is a global, they may be non-addr-taken
-  // globals, which we can answer queries about.
-  const GlobalValue *GV1 = dyn_cast<GlobalValue>(UV1);
-  const GlobalValue *GV2 = dyn_cast<GlobalValue>(UV2);
-  if (GV1 || GV2) {
-    // If the global's address is taken, pretend we don't know it's a pointer to
-    // the global.
-    if (GV1 && !NonAddressTakenGlobals.count(GV1))
-      GV1 = nullptr;
-    if (GV2 && !NonAddressTakenGlobals.count(GV2))
-      GV2 = nullptr;
-
-    // If the two pointers are derived from two different non-addr-taken
-    // globals we know these can't alias.
-    if (GV1 && GV2 && GV1 != GV2)
-      return NoAlias;
-
-    // If one is and the other isn't, it isn't strictly safe but we can fake
-    // this result if necessary for performance. This does not appear to be
-    // a common problem in practice.
-    if (EnableUnsafeGlobalsModRefAliasResults)
-      if ((GV1 || GV2) && GV1 != GV2)
-        return NoAlias;
-
-    // Check for a special case where a non-escaping global can be used to
-    // conclude no-alias.
-    if ((GV1 || GV2) && GV1 != GV2) {
-      const GlobalValue *GV = GV1 ? GV1 : GV2;
-      const Value *UV = GV1 ? UV2 : UV1;
-      if (isNonEscapingGlobalNoAlias(GV, UV))
-        return NoAlias;
-    }
-
-    // Otherwise if they are both derived from the same addr-taken global, we
-    // can't know the two accesses don't overlap.
-  }
-
-  // These pointers may be based on the memory owned by an indirect global.  If
-  // so, we may be able to handle this.  First check to see if the base pointer
-  // is a direct load from an indirect global.
-  GV1 = GV2 = nullptr;
-  if (const LoadInst *LI = dyn_cast<LoadInst>(UV1))
-    if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
-      if (IndirectGlobals.count(GV))
-        GV1 = GV;
-  if (const LoadInst *LI = dyn_cast<LoadInst>(UV2))
-    if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0)))
-      if (IndirectGlobals.count(GV))
-        GV2 = GV;
-
-  // These pointers may also be from an allocation for the indirect global.  If
-  // so, also handle them.
-  if (!GV1)
-    GV1 = AllocsForIndirectGlobals.lookup(UV1);
-  if (!GV2)
-    GV2 = AllocsForIndirectGlobals.lookup(UV2);
-
-  // Now that we know whether the two pointers are related to indirect globals,
-  // use this to disambiguate the pointers. If the pointers are based on
-  // different indirect globals they cannot alias.
-  if (GV1 && GV2 && GV1 != GV2)
-    return NoAlias;
-
-  // If one is based on an indirect global and the other isn't, it isn't
-  // strictly safe but we can fake this result if necessary for performance.
-  // This does not appear to be a common problem in practice.
-  if (EnableUnsafeGlobalsModRefAliasResults)
-    if ((GV1 || GV2) && GV1 != GV2)
-      return NoAlias;
-
-  return AliasAnalysis::alias(LocA, LocB);
-}
-
-ModRefInfo GlobalsModRef::getModRefInfo(ImmutableCallSite CS,
-                                        const MemoryLocation &Loc) {
-  unsigned Known = MRI_ModRef;
-
-  // If we are asking for mod/ref info of a direct call with a pointer to a
-  // global we are tracking, return information if we have it.
-  const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout();
-  if (const GlobalValue *GV =
-          dyn_cast<GlobalValue>(GetUnderlyingObject(Loc.Ptr, DL)))
-    if (GV->hasLocalLinkage())
-      if (const Function *F = CS.getCalledFunction())
-        if (NonAddressTakenGlobals.count(GV))
-          if (const FunctionInfo *FI = getFunctionInfo(F))
-            Known = FI->getModRefInfoForGlobal(*GV);
-
-  if (Known == MRI_NoModRef)
-    return MRI_NoModRef; // No need to query other mod/ref analyses
-  return ModRefInfo(Known & AliasAnalysis::getModRefInfo(CS, Loc));
-}
Index: llvm/trunk/lib/Analysis/IPA/IPA.cpp
===================================================================
--- llvm/trunk/lib/Analysis/IPA/IPA.cpp
+++ llvm/trunk/lib/Analysis/IPA/IPA.cpp
@@ -1,30 +0,0 @@
-//===-- IPA.cpp -----------------------------------------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements the common initialization routines for the IPA library.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/InitializePasses.h"
-#include "llvm-c/Initialization.h"
-#include "llvm/PassRegistry.h"
-
-using namespace llvm;
-
-/// initializeIPA - Initialize all passes linked into the IPA library.
-void llvm::initializeIPA(PassRegistry &Registry) {
-  initializeCallGraphWrapperPassPass(Registry);
-  initializeCallGraphPrinterPass(Registry);
-  initializeCallGraphViewerPass(Registry);
-  initializeGlobalsModRefPass(Registry);
-}
-
-void LLVMInitializeIPA(LLVMPassRegistryRef R) {
-  initializeIPA(*unwrap(R));
-}
Index: llvm/trunk/lib/Analysis/IPA/InlineCost.cpp
===================================================================
--- llvm/trunk/lib/Analysis/IPA/InlineCost.cpp
+++ llvm/trunk/lib/Analysis/IPA/InlineCost.cpp
@@ -1,1451 +0,0 @@
-//===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// This file implements inline cost analysis.
-//
-//===----------------------------------------------------------------------===//
-
-#include "llvm/Analysis/InlineCost.h"
-#include "llvm/ADT/STLExtras.h"
-#include "llvm/ADT/SetVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/AssumptionCache.h"
-#include "llvm/Analysis/CodeMetrics.h"
-#include "llvm/Analysis/ConstantFolding.h"
-#include "llvm/Analysis/InstructionSimplify.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/IR/CallSite.h"
-#include "llvm/IR/CallingConv.h"
-#include "llvm/IR/DataLayout.h"
-#include "llvm/IR/GetElementPtrTypeIterator.h"
-#include "llvm/IR/GlobalAlias.h"
-#include "llvm/IR/InstVisitor.h"
-#include "llvm/IR/IntrinsicInst.h"
-#include "llvm/IR/Operator.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/Support/raw_ostream.h"
-
-using namespace llvm;
-
-#define DEBUG_TYPE "inline-cost"
-
-STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
-
-namespace {
-
-class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
-  typedef InstVisitor<CallAnalyzer, bool> Base;
-  friend class InstVisitor<CallAnalyzer, bool>;
-
-  /// The TargetTransformInfo available for this compilation.
-  const TargetTransformInfo &TTI;
-
-  /// The cache of @llvm.assume intrinsics.
-  AssumptionCacheTracker *ACT;
-
-  // The called function.
-  Function &F;
-
-  // The candidate callsite being analyzed. Please do not use this to do
-  // analysis in the caller function; we want the inline cost query to be
-  // easily cacheable. Instead, use the cover function paramHasAttr.
-  CallSite CandidateCS;
-
-  int Threshold;
-  int Cost;
-
-  bool IsCallerRecursive;
-  bool IsRecursiveCall;
-  bool ExposesReturnsTwice;
-  bool HasDynamicAlloca;
-  bool ContainsNoDuplicateCall;
-  bool HasReturn;
-  bool HasIndirectBr;
-  bool HasFrameEscape;
-
-  /// Number of bytes allocated statically by the callee.
-  uint64_t AllocatedSize;
-  unsigned NumInstructions, NumVectorInstructions;
-  int FiftyPercentVectorBonus, TenPercentVectorBonus;
-  int VectorBonus;
-
-  // While we walk the potentially-inlined instructions, we build up and
-  // maintain a mapping of simplified values specific to this callsite. The
-  // idea is to propagate any special information we have about arguments to
-  // this call through the inlinable section of the function, and account for
-  // likely simplifications post-inlining. The most important aspect we track
-  // is CFG altering simplifications -- when we prove a basic block dead, that
-  // can cause dramatic shifts in the cost of inlining a function.
-  DenseMap<Value *, Constant *> SimplifiedValues;
-
-  // Keep track of the values which map back (through function arguments) to
-  // allocas on the caller stack which could be simplified through SROA.
-  DenseMap<Value *, Value *> SROAArgValues;
-
-  // The mapping of caller Alloca values to their accumulated cost savings. If
-  // we have to disable SROA for one of the allocas, this tells us how much
-  // cost must be added.
-  DenseMap<Value *, int> SROAArgCosts;
-
-  // Keep track of values which map to a pointer base and constant offset.
-  DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;
-
-  // Custom simplification helper routines.
-  bool isAllocaDerivedArg(Value *V);
-  bool lookupSROAArgAndCost(Value *V, Value *&Arg,
-                            DenseMap<Value *, int>::iterator &CostIt);
-  void disableSROA(DenseMap<Value *, int>::iterator CostIt);
-  void disableSROA(Value *V);
-  void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
-                          int InstructionCost);
-  bool isGEPOffsetConstant(GetElementPtrInst &GEP);
-  bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
-  bool simplifyCallSite(Function *F, CallSite CS);
-  ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
-
-  /// Return true if the given argument to the function being considered for
-  /// inlining has the given attribute set either at the call site or the
-  /// function declaration.  Primarily used to inspect call site specific
-  /// attributes since these can be more precise than the ones on the callee
-  /// itself. 
-  bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
-  
-  /// Return true if the given value is known non null within the callee if
-  /// inlined through this particular callsite. 
-  bool isKnownNonNullInCallee(Value *V);
-
-  // Custom analysis routines.
-  bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
-
-  // Disable several entry points to the visitor so we don't accidentally use
-  // them by declaring but not defining them here.
-  void visit(Module *);     void visit(Module &);
-  void visit(Function *);   void visit(Function &);
-  void visit(BasicBlock *); void visit(BasicBlock &);
-
-  // Provide base case for our instruction visit.
-  bool visitInstruction(Instruction &I);
-
-  // Our visit overrides.
-  bool visitAlloca(AllocaInst &I);
-  bool visitPHI(PHINode &I);
-  bool visitGetElementPtr(GetElementPtrInst &I);
-  bool visitBitCast(BitCastInst &I);
-  bool visitPtrToInt(PtrToIntInst &I);
-  bool visitIntToPtr(IntToPtrInst &I);
-  bool visitCastInst(CastInst &I);
-  bool visitUnaryInstruction(UnaryInstruction &I);
-  bool visitCmpInst(CmpInst &I);
-  bool visitSub(BinaryOperator &I);
-  bool visitBinaryOperator(BinaryOperator &I);
-  bool visitLoad(LoadInst &I);
-  bool visitStore(StoreInst &I);
-  bool visitExtractValue(ExtractValueInst &I);
-  bool visitInsertValue(InsertValueInst &I);
-  bool visitCallSite(CallSite CS);
-  bool visitReturnInst(ReturnInst &RI);
-  bool visitBranchInst(BranchInst &BI);
-  bool visitSwitchInst(SwitchInst &SI);
-  bool visitIndirectBrInst(IndirectBrInst &IBI);
-  bool visitResumeInst(ResumeInst &RI);
-  bool visitCleanupReturnInst(CleanupReturnInst &RI);
-  bool visitCatchReturnInst(CatchReturnInst &RI);
-  bool visitUnreachableInst(UnreachableInst &I);
-
-public:
-  CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT,
-               Function &Callee, int Threshold, CallSite CSArg)
-    : TTI(TTI), ACT(ACT), F(Callee), CandidateCS(CSArg), Threshold(Threshold),
-        Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
-        ExposesReturnsTwice(false), HasDynamicAlloca(false),
-        ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
-        HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
-        NumVectorInstructions(0), FiftyPercentVectorBonus(0),
-        TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
-        NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
-        NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
-        SROACostSavings(0), SROACostSavingsLost(0) {}
-
-  bool analyzeCall(CallSite CS);
-
-  int getThreshold() { return Threshold; }
-  int getCost() { return Cost; }
-
-  // Keep a bunch of stats about the cost savings found so we can print them
-  // out when debugging.
-  unsigned NumConstantArgs;
-  unsigned NumConstantOffsetPtrArgs;
-  unsigned NumAllocaArgs;
-  unsigned NumConstantPtrCmps;
-  unsigned NumConstantPtrDiffs;
-  unsigned NumInstructionsSimplified;
-  unsigned SROACostSavings;
-  unsigned SROACostSavingsLost;
-
-  void dump();
-};
-
-} // namespace
-
-/// \brief Test whether the given value is an Alloca-derived function argument.
-bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
-  return SROAArgValues.count(V);
-}
-
-/// \brief Lookup the SROA-candidate argument and cost iterator which V maps to.
-/// Returns false if V does not map to a SROA-candidate.
-bool CallAnalyzer::lookupSROAArgAndCost(
-    Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
-  if (SROAArgValues.empty() || SROAArgCosts.empty())
-    return false;
-
-  DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
-  if (ArgIt == SROAArgValues.end())
-    return false;
-
-  Arg = ArgIt->second;
-  CostIt = SROAArgCosts.find(Arg);
-  return CostIt != SROAArgCosts.end();
-}
-
-/// \brief Disable SROA for the candidate marked by this cost iterator.
-///
-/// This marks the candidate as no longer viable for SROA, and adds the cost
-/// savings associated with it back into the inline cost measurement.
-void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
-  // If we're no longer able to perform SROA we need to undo its cost savings
-  // and prevent subsequent analysis.
-  Cost += CostIt->second;
-  SROACostSavings -= CostIt->second;
-  SROACostSavingsLost += CostIt->second;
-  SROAArgCosts.erase(CostIt);
-}
-
-/// \brief If 'V' maps to a SROA candidate, disable SROA for it.
-void CallAnalyzer::disableSROA(Value *V) {
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(V, SROAArg, CostIt))
-    disableSROA(CostIt);
-}
-
-/// \brief Accumulate the given cost for a particular SROA candidate.
-void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
-                                      int InstructionCost) {
-  CostIt->second += InstructionCost;
-  SROACostSavings += InstructionCost;
-}
-
-/// \brief Check whether a GEP's indices are all constant.
-///
-/// Respects any simplified values known during the analysis of this callsite.
-bool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) {
-  for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
-    if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
-      return false;
-
-  return true;
-}
-
-/// \brief Accumulate a constant GEP offset into an APInt if possible.
-///
-/// Returns false if unable to compute the offset for any reason. Respects any
-/// simplified values known during the analysis of this callsite.
-bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
-  const DataLayout &DL = F.getParent()->getDataLayout();
-  unsigned IntPtrWidth = DL.getPointerSizeInBits();
-  assert(IntPtrWidth == Offset.getBitWidth());
-
-  for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
-       GTI != GTE; ++GTI) {
-    ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
-    if (!OpC)
-      if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
-        OpC = dyn_cast<ConstantInt>(SimpleOp);
-    if (!OpC)
-      return false;
-    if (OpC->isZero()) continue;
-
-    // Handle a struct index, which adds its field offset to the pointer.
-    if (StructType *STy = dyn_cast<StructType>(*GTI)) {
-      unsigned ElementIdx = OpC->getZExtValue();
-      const StructLayout *SL = DL.getStructLayout(STy);
-      Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
-      continue;
-    }
-
-    APInt TypeSize(IntPtrWidth, DL.getTypeAllocSize(GTI.getIndexedType()));
-    Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
-  }
-  return true;
-}
-
-bool CallAnalyzer::visitAlloca(AllocaInst &I) {
-  // Check whether inlining will turn a dynamic alloca into a static
-  // alloca, and handle that case.
-  if (I.isArrayAllocation()) {
-    if (Constant *Size = SimplifiedValues.lookup(I.getArraySize())) {
-      ConstantInt *AllocSize = dyn_cast<ConstantInt>(Size);
-      assert(AllocSize && "Allocation size not a constant int?");
-      Type *Ty = I.getAllocatedType();
-      AllocatedSize += Ty->getPrimitiveSizeInBits() * AllocSize->getZExtValue();
-      return Base::visitAlloca(I);
-    }
-  }
-
-  // Accumulate the allocated size.
-  if (I.isStaticAlloca()) {
-    const DataLayout &DL = F.getParent()->getDataLayout();
-    Type *Ty = I.getAllocatedType();
-    AllocatedSize += DL.getTypeAllocSize(Ty);
-  }
-
-  // We will happily inline static alloca instructions.
-  if (I.isStaticAlloca())
-    return Base::visitAlloca(I);
-
-  // FIXME: This is overly conservative. Dynamic allocas are inefficient for
-  // a variety of reasons, and so we would like to not inline them into
-  // functions which don't currently have a dynamic alloca. This simply
-  // disables inlining altogether in the presence of a dynamic alloca.
-  HasDynamicAlloca = true;
-  return false;
-}
-
-bool CallAnalyzer::visitPHI(PHINode &I) {
-  // FIXME: We should potentially be tracking values through phi nodes,
-  // especially when they collapse to a single value due to deleted CFG edges
-  // during inlining.
-
-  // FIXME: We need to propagate SROA *disabling* through phi nodes, even
-  // though we don't want to propagate it's bonuses. The idea is to disable
-  // SROA if it *might* be used in an inappropriate manner.
-
-  // Phi nodes are always zero-cost.
-  return true;
-}
-
-bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(),
-                                            SROAArg, CostIt);
-
-  // Try to fold GEPs of constant-offset call site argument pointers. This
-  // requires target data and inbounds GEPs.
-  if (I.isInBounds()) {
-    // Check if we have a base + offset for the pointer.
-    Value *Ptr = I.getPointerOperand();
-    std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr);
-    if (BaseAndOffset.first) {
-      // Check if the offset of this GEP is constant, and if so accumulate it
-      // into Offset.
-      if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) {
-        // Non-constant GEPs aren't folded, and disable SROA.
-        if (SROACandidate)
-          disableSROA(CostIt);
-        return false;
-      }
-
-      // Add the result as a new mapping to Base + Offset.
-      ConstantOffsetPtrs[&I] = BaseAndOffset;
-
-      // Also handle SROA candidates here, we already know that the GEP is
-      // all-constant indexed.
-      if (SROACandidate)
-        SROAArgValues[&I] = SROAArg;
-
-      return true;
-    }
-  }
-
-  if (isGEPOffsetConstant(I)) {
-    if (SROACandidate)
-      SROAArgValues[&I] = SROAArg;
-
-    // Constant GEPs are modeled as free.
-    return true;
-  }
-
-  // Variable GEPs will require math and will disable SROA.
-  if (SROACandidate)
-    disableSROA(CostIt);
-  return false;
-}
-
-bool CallAnalyzer::visitBitCast(BitCastInst &I) {
-  // Propagate constants through bitcasts.
-  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
-  if (!COp)
-    COp = SimplifiedValues.lookup(I.getOperand(0));
-  if (COp)
-    if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) {
-      SimplifiedValues[&I] = C;
-      return true;
-    }
-
-  // Track base/offsets through casts
-  std::pair<Value *, APInt> BaseAndOffset
-    = ConstantOffsetPtrs.lookup(I.getOperand(0));
-  // Casts don't change the offset, just wrap it up.
-  if (BaseAndOffset.first)
-    ConstantOffsetPtrs[&I] = BaseAndOffset;
-
-  // Also look for SROA candidates here.
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
-    SROAArgValues[&I] = SROAArg;
-
-  // Bitcasts are always zero cost.
-  return true;
-}
-
-bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
-  // Propagate constants through ptrtoint.
-  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
-  if (!COp)
-    COp = SimplifiedValues.lookup(I.getOperand(0));
-  if (COp)
-    if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) {
-      SimplifiedValues[&I] = C;
-      return true;
-    }
-
-  // Track base/offset pairs when converted to a plain integer provided the
-  // integer is large enough to represent the pointer.
-  unsigned IntegerSize = I.getType()->getScalarSizeInBits();
-  const DataLayout &DL = F.getParent()->getDataLayout();
-  if (IntegerSize >= DL.getPointerSizeInBits()) {
-    std::pair<Value *, APInt> BaseAndOffset
-      = ConstantOffsetPtrs.lookup(I.getOperand(0));
-    if (BaseAndOffset.first)
-      ConstantOffsetPtrs[&I] = BaseAndOffset;
-  }
-
-  // This is really weird. Technically, ptrtoint will disable SROA. However,
-  // unless that ptrtoint is *used* somewhere in the live basic blocks after
-  // inlining, it will be nuked, and SROA should proceed. All of the uses which
-  // would block SROA would also block SROA if applied directly to a pointer,
-  // and so we can just add the integer in here. The only places where SROA is
-  // preserved either cannot fire on an integer, or won't in-and-of themselves
-  // disable SROA (ext) w/o some later use that we would see and disable.
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
-    SROAArgValues[&I] = SROAArg;
-
-  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
-}
-
-bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
-  // Propagate constants through ptrtoint.
-  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
-  if (!COp)
-    COp = SimplifiedValues.lookup(I.getOperand(0));
-  if (COp)
-    if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) {
-      SimplifiedValues[&I] = C;
-      return true;
-    }
-
-  // Track base/offset pairs when round-tripped through a pointer without
-  // modifications provided the integer is not too large.
-  Value *Op = I.getOperand(0);
-  unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
-  const DataLayout &DL = F.getParent()->getDataLayout();
-  if (IntegerSize <= DL.getPointerSizeInBits()) {
-    std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
-    if (BaseAndOffset.first)
-      ConstantOffsetPtrs[&I] = BaseAndOffset;
-  }
-
-  // "Propagate" SROA here in the same manner as we do for ptrtoint above.
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
-    SROAArgValues[&I] = SROAArg;
-
-  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
-}
-
-bool CallAnalyzer::visitCastInst(CastInst &I) {
-  // Propagate constants through ptrtoint.
-  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
-  if (!COp)
-    COp = SimplifiedValues.lookup(I.getOperand(0));
-  if (COp)
-    if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
-      SimplifiedValues[&I] = C;
-      return true;
-    }
-
-  // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere.
-  disableSROA(I.getOperand(0));
-
-  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
-}
-
-bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
-  Value *Operand = I.getOperand(0);
-  Constant *COp = dyn_cast<Constant>(Operand);
-  if (!COp)
-    COp = SimplifiedValues.lookup(Operand);
-  if (COp) {
-    const DataLayout &DL = F.getParent()->getDataLayout();
-    if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(),
-                                               COp, DL)) {
-      SimplifiedValues[&I] = C;
-      return true;
-    }
-  }
-
-  // Disable any SROA on the argument to arbitrary unary operators.
-  disableSROA(Operand);
-
-  return false;
-}
-
-bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
-  unsigned ArgNo = A->getArgNo();
-  return CandidateCS.paramHasAttr(ArgNo+1, Attr);
-}
-
-bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
-  // Does the *call site* have the NonNull attribute set on an argument?  We
-  // use the attribute on the call site to memoize any analysis done in the
-  // caller. This will also trip if the callee function has a non-null
-  // parameter attribute, but that's a less interesting case because hopefully
-  // the callee would already have been simplified based on that.
-  if (Argument *A = dyn_cast<Argument>(V))
-    if (paramHasAttr(A, Attribute::NonNull))
-      return true;
-  
-  // Is this an alloca in the caller?  This is distinct from the attribute case
-  // above because attributes aren't updated within the inliner itself and we
-  // always want to catch the alloca derived case.
-  if (isAllocaDerivedArg(V))
-    // We can actually predict the result of comparisons between an
-    // alloca-derived value and null. Note that this fires regardless of
-    // SROA firing.
-    return true;
-  
-  return false;
-}
-
-bool CallAnalyzer::visitCmpInst(CmpInst &I) {
-  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
-  // First try to handle simplified comparisons.
-  if (!isa<Constant>(LHS))
-    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
-      LHS = SimpleLHS;
-  if (!isa<Constant>(RHS))
-    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
-      RHS = SimpleRHS;
-  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
-    if (Constant *CRHS = dyn_cast<Constant>(RHS))
-      if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
-        SimplifiedValues[&I] = C;
-        return true;
-      }
-  }
-
-  if (I.getOpcode() == Instruction::FCmp)
-    return false;
-
-  // Otherwise look for a comparison between constant offset pointers with
-  // a common base.
-  Value *LHSBase, *RHSBase;
-  APInt LHSOffset, RHSOffset;
-  std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
-  if (LHSBase) {
-    std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
-    if (RHSBase && LHSBase == RHSBase) {
-      // We have common bases, fold the icmp to a constant based on the
-      // offsets.
-      Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
-      Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
-      if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
-        SimplifiedValues[&I] = C;
-        ++NumConstantPtrCmps;
-        return true;
-      }
-    }
-  }
-
-  // If the comparison is an equality comparison with null, we can simplify it
-  // if we know the value (argument) can't be null
-  if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)) &&
-      isKnownNonNullInCallee(I.getOperand(0))) {
-    bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
-    SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
-                                      : ConstantInt::getFalse(I.getType());
-    return true;
-  }
-  // Finally check for SROA candidates in comparisons.
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
-    if (isa<ConstantPointerNull>(I.getOperand(1))) {
-      accumulateSROACost(CostIt, InlineConstants::InstrCost);
-      return true;
-    }
-
-    disableSROA(CostIt);
-  }
-
-  return false;
-}
-
-bool CallAnalyzer::visitSub(BinaryOperator &I) {
-  // Try to handle a special case: we can fold computing the difference of two
-  // constant-related pointers.
-  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
-  Value *LHSBase, *RHSBase;
-  APInt LHSOffset, RHSOffset;
-  std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
-  if (LHSBase) {
-    std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
-    if (RHSBase && LHSBase == RHSBase) {
-      // We have common bases, fold the subtract to a constant based on the
-      // offsets.
-      Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
-      Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
-      if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
-        SimplifiedValues[&I] = C;
-        ++NumConstantPtrDiffs;
-        return true;
-      }
-    }
-  }
-
-  // Otherwise, fall back to the generic logic for simplifying and handling
-  // instructions.
-  return Base::visitSub(I);
-}
-
-bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
-  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
-  const DataLayout &DL = F.getParent()->getDataLayout();
-  if (!isa<Constant>(LHS))
-    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
-      LHS = SimpleLHS;
-  if (!isa<Constant>(RHS))
-    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
-      RHS = SimpleRHS;
-  Value *SimpleV = nullptr;
-  if (auto FI = dyn_cast<FPMathOperator>(&I))
-    SimpleV =
-        SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
-  else
-    SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
-
-  if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) {
-    SimplifiedValues[&I] = C;
-    return true;
-  }
-
-  // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
-  disableSROA(LHS);
-  disableSROA(RHS);
-
-  return false;
-}
-
-bool CallAnalyzer::visitLoad(LoadInst &I) {
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
-    if (I.isSimple()) {
-      accumulateSROACost(CostIt, InlineConstants::InstrCost);
-      return true;
-    }
-
-    disableSROA(CostIt);
-  }
-
-  return false;
-}
-
-bool CallAnalyzer::visitStore(StoreInst &I) {
-  Value *SROAArg;
-  DenseMap<Value *, int>::iterator CostIt;
-  if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
-    if (I.isSimple()) {
-      accumulateSROACost(CostIt, InlineConstants::InstrCost);
-      return true;
-    }
-
-    disableSROA(CostIt);
-  }
-
-  return false;
-}
-
-bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) {
-  // Constant folding for extract value is trivial.
-  Constant *C = dyn_cast<Constant>(I.getAggregateOperand());
-  if (!C)
-    C = SimplifiedValues.lookup(I.getAggregateOperand());
-  if (C) {
-    SimplifiedValues[&I] = ConstantExpr::getExtractValue(C, I.getIndices());
-    return true;
-  }
-
-  // SROA can look through these but give them a cost.
-  return false;
-}
-
-bool CallAnalyzer::visitInsertValue(InsertValueInst &I) {
-  // Constant folding for insert value is trivial.
-  Constant *AggC = dyn_cast<Constant>(I.getAggregateOperand());
-  if (!AggC)
-    AggC = SimplifiedValues.lookup(I.getAggregateOperand());
-  Constant *InsertedC = dyn_cast<Constant>(I.getInsertedValueOperand());
-  if (!InsertedC)
-    InsertedC = SimplifiedValues.lookup(I.getInsertedValueOperand());
-  if (AggC && InsertedC) {
-    SimplifiedValues[&I] = ConstantExpr::getInsertValue(AggC, InsertedC,
-                                                        I.getIndices());
-    return true;
-  }
-
-  // SROA can look through these but give them a cost.
-  return false;
-}
-
-/// \brief Try to simplify a call site.
-///
-/// Takes a concrete function and callsite and tries to actually simplify it by
-/// analyzing the arguments and call itself with instsimplify. Returns true if
-/// it has simplified the callsite to some other entity (a constant), making it
-/// free.
-bool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) {
-  // FIXME: Using the instsimplify logic directly for this is inefficient
-  // because we have to continually rebuild the argument list even when no
-  // simplifications can be performed. Until that is fixed with remapping
-  // inside of instsimplify, directly constant fold calls here.
-  if (!canConstantFoldCallTo(F))
-    return false;
-
-  // Try to re-map the arguments to constants.
-  SmallVector<Constant *, 4> ConstantArgs;
-  ConstantArgs.reserve(CS.arg_size());
-  for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
-       I != E; ++I) {
-    Constant *C = dyn_cast<Constant>(*I);
-    if (!C)
-      C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I));
-    if (!C)
-      return false; // This argument doesn't map to a constant.
-
-    ConstantArgs.push_back(C);
-  }
-  if (Constant *C = ConstantFoldCall(F, ConstantArgs)) {
-    SimplifiedValues[CS.getInstruction()] = C;
-    return true;
-  }
-
-  return false;
-}
-
-bool CallAnalyzer::visitCallSite(CallSite CS) {
-  if (CS.hasFnAttr(Attribute::ReturnsTwice) &&
-      !F.hasFnAttribute(Attribute::ReturnsTwice)) {
-    // This aborts the entire analysis.
-    ExposesReturnsTwice = true;
-    return false;
-  }
-  if (CS.isCall() &&
-      cast<CallInst>(CS.getInstruction())->cannotDuplicate())
-    ContainsNoDuplicateCall = true;
-
-  if (Function *F = CS.getCalledFunction()) {
-    // When we have a concrete function, first try to simplify it directly.
-    if (simplifyCallSite(F, CS))
-      return true;
-
-    // Next check if it is an intrinsic we know about.
-    // FIXME: Lift this into part of the InstVisitor.
-    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
-      switch (II->getIntrinsicID()) {
-      default:
-        return Base::visitCallSite(CS);
-
-      case Intrinsic::memset:
-      case Intrinsic::memcpy:
-      case Intrinsic::memmove:
-        // SROA can usually chew through these intrinsics, but they aren't free.
-        return false;
-      case Intrinsic::localescape:
-        HasFrameEscape = true;
-        return false;
-      }
-    }
-
-    if (F == CS.getInstruction()->getParent()->getParent()) {
-      // This flag will fully abort the analysis, so don't bother with anything
-      // else.
-      IsRecursiveCall = true;
-      return false;
-    }
-
-    if (TTI.isLoweredToCall(F)) {
-      // We account for the average 1 instruction per call argument setup
-      // here.
-      Cost += CS.arg_size() * InlineConstants::InstrCost;
-
-      // Everything other than inline ASM will also have a significant cost
-      // merely from making the call.
-      if (!isa<InlineAsm>(CS.getCalledValue()))
-        Cost += InlineConstants::CallPenalty;
-    }
-
-    return Base::visitCallSite(CS);
-  }
-
-  // Otherwise we're in a very special case -- an indirect function call. See
-  // if we can be particularly clever about this.
-  Value *Callee = CS.getCalledValue();
-
-  // First, pay the price of the argument setup. We account for the average
-  // 1 instruction per call argument setup here.
-  Cost += CS.arg_size() * InlineConstants::InstrCost;
-
-  // Next, check if this happens to be an indirect function call to a known
-  // function in this inline context. If not, we've done all we can.
-  Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
-  if (!F)
-    return Base::visitCallSite(CS);
-
-  // If we have a constant that we are calling as a function, we can peer
-  // through it and see the function target. This happens not infrequently
-  // during devirtualization and so we want to give it a hefty bonus for
-  // inlining, but cap that bonus in the event that inlining wouldn't pan
-  // out. Pretend to inline the function, with a custom threshold.
-  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS);
-  if (CA.analyzeCall(CS)) {
-    // We were able to inline the indirect call! Subtract the cost from the
-    // bonus we want to apply, but don't go below zero.
-    Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
-  }
-
-  return Base::visitCallSite(CS);
-}
-
-bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
-  // At least one return instruction will be free after inlining.
-  bool Free = !HasReturn;
-  HasReturn = true;
-  return Free;
-}
-
-bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
-  // We model unconditional branches as essentially free -- they really
-  // shouldn't exist at all, but handling them makes the behavior of the
-  // inliner more regular and predictable. Interestingly, conditional branches
-  // which will fold away are also free.
-  return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
-         dyn_cast_or_null<ConstantInt>(
-             SimplifiedValues.lookup(BI.getCondition()));
-}
-
-bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
-  // We model unconditional switches as free, see the comments on handling
-  // branches.
-  if (isa<ConstantInt>(SI.getCondition()))
-    return true;
-  if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
-    if (isa<ConstantInt>(V))
-      return true;
-
-  // Otherwise, we need to accumulate a cost proportional to the number of
-  // distinct successor blocks. This fan-out in the CFG cannot be represented
-  // for free even if we can represent the core switch as a jumptable that
-  // takes a single instruction.
-  //
-  // NB: We convert large switches which are just used to initialize large phi
-  // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent
-  // inlining those. It will prevent inlining in cases where the optimization
-  // does not (yet) fire.
-  SmallPtrSet<BasicBlock *, 8> SuccessorBlocks;
-  SuccessorBlocks.insert(SI.getDefaultDest());
-  for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I)
-    SuccessorBlocks.insert(I.getCaseSuccessor());
-  // Add cost corresponding to the number of distinct destinations. The first
-  // we model as free because of fallthrough.
-  Cost += (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost;
-  return false;
-}
-
-bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
-  // We never want to inline functions that contain an indirectbr.  This is
-  // incorrect because all the blockaddress's (in static global initializers
-  // for example) would be referring to the original function, and this
-  // indirect jump would jump from the inlined copy of the function into the
-  // original function which is extremely undefined behavior.
-  // FIXME: This logic isn't really right; we can safely inline functions with
-  // indirectbr's as long as no other function or global references the
-  // blockaddress of a block within the current function.
-  HasIndirectBr = true;
-  return false;
-}
-
-bool CallAnalyzer::visitResumeInst(ResumeInst &RI) {
-  // FIXME: It's not clear that a single instruction is an accurate model for
-  // the inline cost of a resume instruction.
-  return false;
-}
-
-bool CallAnalyzer::visitCleanupReturnInst(CleanupReturnInst &CRI) {
-  // FIXME: It's not clear that a single instruction is an accurate model for
-  // the inline cost of a cleanupret instruction.
-  return false;
-}
-
-bool CallAnalyzer::visitCatchReturnInst(CatchReturnInst &CRI) {
-  // FIXME: It's not clear that a single instruction is an accurate model for
-  // the inline cost of a cleanupret instruction.
-  return false;
-}
-
-bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) {
-  // FIXME: It might be reasonably to discount the cost of instructions leading
-  // to unreachable as they have the lowest possible impact on both runtime and
-  // code size.
-  return true; // No actual code is needed for unreachable.
-}
-
-bool CallAnalyzer::visitInstruction(Instruction &I) {
-  // Some instructions are free. All of the free intrinsics can also be
-  // handled by SROA, etc.
-  if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I))
-    return true;
-
-  // We found something we don't understand or can't handle. Mark any SROA-able
-  // values in the operand list as no longer viable.
-  for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI)
-    disableSROA(*OI);
-
-  return false;
-}
-
-
-/// \brief Analyze a basic block for its contribution to the inline cost.
-///
-/// This method walks the analyzer over every instruction in the given basic
-/// block and accounts for their cost during inlining at this callsite. It
-/// aborts early if the threshold has been exceeded or an impossible to inline
-/// construct has been detected. It returns false if inlining is no longer
-/// viable, and true if inlining remains viable.
-bool CallAnalyzer::analyzeBlock(BasicBlock *BB,
-                                SmallPtrSetImpl<const Value *> &EphValues) {
-  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
-    // FIXME: Currently, the number of instructions in a function regardless of
-    // our ability to simplify them during inline to constants or dead code,
-    // are actually used by the vector bonus heuristic. As long as that's true,
-    // we have to special case debug intrinsics here to prevent differences in
-    // inlining due to debug symbols. Eventually, the number of unsimplified
-    // instructions shouldn't factor into the cost computation, but until then,
-    // hack around it here.
-    if (isa<DbgInfoIntrinsic>(I))
-      continue;
-
-    // Skip ephemeral values.
-    if (EphValues.count(I))
-      continue;
-
-    ++NumInstructions;
-    if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
-      ++NumVectorInstructions;
-
-    // If the instruction is floating point, and the target says this operation is
-    // expensive or the function has the "use-soft-float" attribute, this may
-    // eventually become a library call.  Treat the cost as such.
-    if (I->getType()->isFloatingPointTy()) {
-      bool hasSoftFloatAttr = false;
-
-      // If the function has the "use-soft-float" attribute, mark it as expensive.
-      if (F.hasFnAttribute("use-soft-float")) {
-        Attribute Attr = F.getFnAttribute("use-soft-float");
-        StringRef Val = Attr.getValueAsString();
-        if (Val == "true")
-          hasSoftFloatAttr = true;
-      }
-
-      if (TTI.getFPOpCost(I->getType()) == TargetTransformInfo::TCC_Expensive ||
-          hasSoftFloatAttr)
-        Cost += InlineConstants::CallPenalty;
-    }
-
-    // If the instruction simplified to a constant, there is no cost to this
-    // instruction. Visit the instructions using our InstVisitor to account for
-    // all of the per-instruction logic. The visit tree returns true if we
-    // consumed the instruction in any way, and false if the instruction's base
-    // cost should count against inlining.
-    if (Base::visit(I))
-      ++NumInstructionsSimplified;
-    else
-      Cost += InlineConstants::InstrCost;
-
-    // If the visit this instruction detected an uninlinable pattern, abort.
-    if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
-        HasIndirectBr || HasFrameEscape)
-      return false;
-
-    // If the caller is a recursive function then we don't want to inline
-    // functions which allocate a lot of stack space because it would increase
-    // the caller stack usage dramatically.
-    if (IsCallerRecursive &&
-        AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
-      return false;
-
-    // Check if we've past the maximum possible threshold so we don't spin in
-    // huge basic blocks that will never inline.
-    if (Cost > Threshold)
-      return false;
-  }
-
-  return true;
-}
-
-/// \brief Compute the base pointer and cumulative constant offsets for V.
-///
-/// This strips all constant offsets off of V, leaving it the base pointer, and
-/// accumulates the total constant offset applied in the returned constant. It
-/// returns 0 if V is not a pointer, and returns the constant '0' if there are
-/// no constant offsets applied.
-ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
-  if (!V->getType()->isPointerTy())
-    return nullptr;
-
-  const DataLayout &DL = F.getParent()->getDataLayout();
-  unsigned IntPtrWidth = DL.getPointerSizeInBits();
-  APInt Offset = APInt::getNullValue(IntPtrWidth);
-
-  // Even though we don't look through PHI nodes, we could be called on an
-  // instruction in an unreachable block, which may be on a cycle.
-  SmallPtrSet<Value *, 4> Visited;
-  Visited.insert(V);
-  do {
-    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
-      if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
-        return nullptr;
-      V = GEP->getPointerOperand();
-    } else if (Operator::getOpcode(V) == Instruction::BitCast) {
-      V = cast<Operator>(V)->getOperand(0);
-    } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
-      if (GA->mayBeOverridden())
-        break;
-      V = GA->getAliasee();
-    } else {
-      break;
-    }
-    assert(V->getType()->isPointerTy() && "Unexpected operand type!");
-  } while (Visited.insert(V).second);
-
-  Type *IntPtrTy = DL.getIntPtrType(V->getContext());
-  return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
-}
-
-/// \brief Analyze a call site for potential inlining.
-///
-/// Returns true if inlining this call is viable, and false if it is not
-/// viable. It computes the cost and adjusts the threshold based on numerous
-/// factors and heuristics. If this method returns false but the computed cost
-/// is below the computed threshold, then inlining was forcibly disabled by
-/// some artifact of the routine.
-bool CallAnalyzer::analyzeCall(CallSite CS) {
-  ++NumCallsAnalyzed;
-
-  // Perform some tweaks to the cost and threshold based on the direct
-  // callsite information.
-
-  // We want to more aggressively inline vector-dense kernels, so up the
-  // threshold, and we'll lower it if the % of vector instructions gets too
-  // low. Note that these bonuses are some what arbitrary and evolved over time
-  // by accident as much as because they are principled bonuses.
-  //
-  // FIXME: It would be nice to remove all such bonuses. At least it would be
-  // nice to base the bonus values on something more scientific.
-  assert(NumInstructions == 0);
-  assert(NumVectorInstructions == 0);
-  FiftyPercentVectorBonus = 3 * Threshold / 2;
-  TenPercentVectorBonus = 3 * Threshold / 4;
-  const DataLayout &DL = F.getParent()->getDataLayout();
-
-  // Track whether the post-inlining function would have more than one basic
-  // block. A single basic block is often intended for inlining. Balloon the
-  // threshold by 50% until we pass the single-BB phase.
-  bool SingleBB = true;
-  int SingleBBBonus = Threshold / 2;
-
-  // Speculatively apply all possible bonuses to Threshold. If cost exceeds
-  // this Threshold any time, and cost cannot decrease, we can stop processing
-  // the rest of the function body.
-  Threshold += (SingleBBBonus + FiftyPercentVectorBonus);
-
-  // Give out bonuses per argument, as the instructions setting them up will
-  // be gone after inlining.
-  for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
-    if (CS.isByValArgument(I)) {
-      // We approximate the number of loads and stores needed by dividing the
-      // size of the byval type by the target's pointer size.
-      PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
-      unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType());
-      unsigned PointerSize = DL.getPointerSizeInBits();
-      // Ceiling division.
-      unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
-
-      // If it generates more than 8 stores it is likely to be expanded as an
-      // inline memcpy so we take that as an upper bound. Otherwise we assume
-      // one load and one store per word copied.
-      // FIXME: The maxStoresPerMemcpy setting from the target should be used
-      // here instead of a magic number of 8, but it's not available via
-      // DataLayout.
-      NumStores = std::min(NumStores, 8U);
-
-      Cost -= 2 * NumStores * InlineConstants::InstrCost;
-    } else {
-      // For non-byval arguments subtract off one instruction per call
-      // argument.
-      Cost -= InlineConstants::InstrCost;
-    }
-  }
-
-  // If there is only one call of the function, and it has internal linkage,
-  // the cost of inlining it drops dramatically.
-  bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() &&
-    &F == CS.getCalledFunction();
-  if (OnlyOneCallAndLocalLinkage)
-    Cost += InlineConstants::LastCallToStaticBonus;
-
-  // If the instruction after the call, or if the normal destination of the
-  // invoke is an unreachable instruction, the function is noreturn. As such,
-  // there is little point in inlining this unless there is literally zero
-  // cost.
-  Instruction *Instr = CS.getInstruction();
-  if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) {
-    if (isa<UnreachableInst>(II->getNormalDest()->begin()))
-      Threshold = 0;
-  } else if (isa<UnreachableInst>(++BasicBlock::iterator(Instr)))
-    Threshold = 0;
-
-  // If this function uses the coldcc calling convention, prefer not to inline
-  // it.
-  if (F.getCallingConv() == CallingConv::Cold)
-    Cost += InlineConstants::ColdccPenalty;
-
-  // Check if we're done. This can happen due to bonuses and penalties.
-  if (Cost > Threshold)
-    return false;
-
-  if (F.empty())
-    return true;
-
-  Function *Caller = CS.getInstruction()->getParent()->getParent();
-  // Check if the caller function is recursive itself.
-  for (User *U : Caller->users()) {
-    CallSite Site(U);
-    if (!Site)
-      continue;
-    Instruction *I = Site.getInstruction();
-    if (I->getParent()->getParent() == Caller) {
-      IsCallerRecursive = true;
-      break;
-    }
-  }
-
-  // Populate our simplified values by mapping from function arguments to call
-  // arguments with known important simplifications.
-  CallSite::arg_iterator CAI = CS.arg_begin();
-  for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
-       FAI != FAE; ++FAI, ++CAI) {
-    assert(CAI != CS.arg_end());
-    if (Constant *C = dyn_cast<Constant>(CAI))
-      SimplifiedValues[FAI] = C;
-
-    Value *PtrArg = *CAI;
-    if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
-      ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue());
-
-      // We can SROA any pointer arguments derived from alloca instructions.
-      if (isa<AllocaInst>(PtrArg)) {
-        SROAArgValues[FAI] = PtrArg;
-        SROAArgCosts[PtrArg] = 0;
-      }
-    }
-  }
-  NumConstantArgs = SimplifiedValues.size();
-  NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
-  NumAllocaArgs = SROAArgValues.size();
-
-  // FIXME: If a caller has multiple calls to a callee, we end up recomputing
-  // the ephemeral values multiple times (and they're completely determined by
-  // the callee, so this is purely duplicate work).
-  SmallPtrSet<const Value *, 32> EphValues;
-  CodeMetrics::collectEphemeralValues(&F, &ACT->getAssumptionCache(F), EphValues);
-
-  // The worklist of live basic blocks in the callee *after* inlining. We avoid
-  // adding basic blocks of the callee which can be proven to be dead for this
-  // particular call site in order to get more accurate cost estimates. This
-  // requires a somewhat heavyweight iteration pattern: we need to walk the
-  // basic blocks in a breadth-first order as we insert live successors. To
-  // accomplish this, prioritizing for small iterations because we exit after
-  // crossing our threshold, we use a small-size optimized SetVector.
-  typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
-                                  SmallPtrSet<BasicBlock *, 16> > BBSetVector;
-  BBSetVector BBWorklist;
-  BBWorklist.insert(&F.getEntryBlock());
-  // Note that we *must not* cache the size, this loop grows the worklist.
-  for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
-    // Bail out the moment we cross the threshold. This means we'll under-count
-    // the cost, but only when undercounting doesn't matter.
-    if (Cost > Threshold)
-      break;
-
-    BasicBlock *BB = BBWorklist[Idx];
-    if (BB->empty())
-      continue;
-
-    // Disallow inlining a blockaddress. A blockaddress only has defined
-    // behavior for an indirect branch in the same function, and we do not
-    // currently support inlining indirect branches. But, the inliner may not
-    // see an indirect branch that ends up being dead code at a particular call
-    // site. If the blockaddress escapes the function, e.g., via a global
-    // variable, inlining may lead to an invalid cross-function reference.
-    if (BB->hasAddressTaken())
-      return false;
-
-    // Analyze the cost of this block. If we blow through the threshold, this
-    // returns false, and we can bail on out.
-    if (!analyzeBlock(BB, EphValues)) {
-      if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
-          HasIndirectBr || HasFrameEscape)
-        return false;
-
-      // If the caller is a recursive function then we don't want to inline
-      // functions which allocate a lot of stack space because it would increase
-      // the caller stack usage dramatically.
-      if (IsCallerRecursive &&
-          AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
-        return false;
-
-      break;
-    }
-
-    TerminatorInst *TI = BB->getTerminator();
-
-    // Add in the live successors by first checking whether we have terminator
-    // that may be simplified based on the values simplified by this call.
-    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
-      if (BI->isConditional()) {
-        Value *Cond = BI->getCondition();
-        if (ConstantInt *SimpleCond
-              = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
-          BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0));
-          continue;
-        }
-      }
-    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
-      Value *Cond = SI->getCondition();
-      if (ConstantInt *SimpleCond
-            = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
-        BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor());
-        continue;
-      }
-    }
-
-    // If we're unable to select a particular successor, just count all of
-    // them.
-    for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
-         ++TIdx)
-      BBWorklist.insert(TI->getSuccessor(TIdx));
-
-    // If we had any successors at this point, than post-inlining is likely to
-    // have them as well. Note that we assume any basic blocks which existed
-    // due to branches or switches which folded above will also fold after
-    // inlining.
-    if (SingleBB && TI->getNumSuccessors() > 1) {
-      // Take off the bonus we applied to the threshold.
-      Threshold -= SingleBBBonus;
-      SingleBB = false;
-    }
-  }
-
-  // If this is a noduplicate call, we can still inline as long as
-  // inlining this would cause the removal of the caller (so the instruction
-  // is not actually duplicated, just moved).
-  if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
-    return false;
-
-  // We applied the maximum possible vector bonus at the beginning. Now,
-  // subtract the excess bonus, if any, from the Threshold before
-  // comparing against Cost.
-  if (NumVectorInstructions <= NumInstructions / 10)
-    Threshold -= FiftyPercentVectorBonus;
-  else if (NumVectorInstructions <= NumInstructions / 2)
-    Threshold -= (FiftyPercentVectorBonus - TenPercentVectorBonus);
-
-  return Cost < Threshold;
-}
-
-#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
-/// \brief Dump stats about this call's analysis.
-void CallAnalyzer::dump() {
-#define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"
-  DEBUG_PRINT_STAT(NumConstantArgs);
-  DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
-  DEBUG_PRINT_STAT(NumAllocaArgs);
-  DEBUG_PRINT_STAT(NumConstantPtrCmps);
-  DEBUG_PRINT_STAT(NumConstantPtrDiffs);
-  DEBUG_PRINT_STAT(NumInstructionsSimplified);
-  DEBUG_PRINT_STAT(NumInstructions);
-  DEBUG_PRINT_STAT(SROACostSavings);
-  DEBUG_PRINT_STAT(SROACostSavingsLost);
-  DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
-  DEBUG_PRINT_STAT(Cost);
-  DEBUG_PRINT_STAT(Threshold);
-#undef DEBUG_PRINT_STAT
-}
-#endif
-
-INITIALIZE_PASS_BEGIN(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
-                      true, true)
-INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
-INITIALIZE_PASS_END(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
-                    true, true)
-
-char InlineCostAnalysis::ID = 0;
-
-InlineCostAnalysis::InlineCostAnalysis() : CallGraphSCCPass(ID) {}
-
-InlineCostAnalysis::~InlineCostAnalysis() {}
-
-void InlineCostAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.setPreservesAll();
-  AU.addRequired<AssumptionCacheTracker>();
-  AU.addRequired<TargetTransformInfoWrapperPass>();
-  CallGraphSCCPass::getAnalysisUsage(AU);
-}
-
-bool InlineCostAnalysis::runOnSCC(CallGraphSCC &SCC) {
-  TTIWP = &getAnalysis<TargetTransformInfoWrapperPass>();
-  ACT = &getAnalysis<AssumptionCacheTracker>();
-  return false;
-}
-
-InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, int Threshold) {
-  return getInlineCost(CS, CS.getCalledFunction(), Threshold);
-}
-
-/// \brief Test that two functions either have or have not the given attribute
-///        at the same time.
-template<typename AttrKind>
-static bool attributeMatches(Function *F1, Function *F2, AttrKind Attr) {
-  return F1->getFnAttribute(Attr) == F2->getFnAttribute(Attr);
-}
-
-/// \brief Test that there are no attribute conflicts between Caller and Callee
-///        that prevent inlining.
-static bool functionsHaveCompatibleAttributes(Function *Caller,
-                                              Function *Callee,
-                                              TargetTransformInfo &TTI) {
-  return TTI.areInlineCompatible(Caller, Callee) &&
-         attributeMatches(Caller, Callee, Attribute::SanitizeAddress) &&
-         attributeMatches(Caller, Callee, Attribute::SanitizeMemory) &&
-         attributeMatches(Caller, Callee, Attribute::SanitizeThread);
-}
-
-InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee,
-                                             int Threshold) {
-  // Cannot inline indirect calls.
-  if (!Callee)
-    return llvm::InlineCost::getNever();
-
-  // Calls to functions with always-inline attributes should be inlined
-  // whenever possible.
-  if (CS.hasFnAttr(Attribute::AlwaysInline)) {
-    if (isInlineViable(*Callee))
-      return llvm::InlineCost::getAlways();
-    return llvm::InlineCost::getNever();
-  }
-
-  // Never inline functions with conflicting attributes (unless callee has
-  // always-inline attribute).
-  if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee,
-                                         TTIWP->getTTI(*Callee)))
-    return llvm::InlineCost::getNever();
-
-  // Don't inline this call if the caller has the optnone attribute.
-  if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone))
-    return llvm::InlineCost::getNever();
-
-  // Don't inline functions which can be redefined at link-time to mean
-  // something else.  Don't inline functions marked noinline or call sites
-  // marked noinline.
-  if (Callee->mayBeOverridden() ||
-      Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
-    return llvm::InlineCost::getNever();
-
-  DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
-        << "...\n");
-
-  CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold, CS);
-  bool ShouldInline = CA.analyzeCall(CS);
-
-  DEBUG(CA.dump());
-
-  // Check if there was a reason to force inlining or no inlining.
-  if (!ShouldInline && CA.getCost() < CA.getThreshold())
-    return InlineCost::getNever();
-  if (ShouldInline && CA.getCost() >= CA.getThreshold())
-    return InlineCost::getAlways();
-
-  return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
-}
-
-bool InlineCostAnalysis::isInlineViable(Function &F) {
-  bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice);
-  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
-    // Disallow inlining of functions which contain indirect branches or
-    // blockaddresses.
-    if (isa<IndirectBrInst>(BI->getTerminator()) || BI->hasAddressTaken())
-      return false;
-
-    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;
-         ++II) {
-      CallSite CS(II);
-      if (!CS)
-        continue;
-
-      // Disallow recursive calls.
-      if (&F == CS.getCalledFunction())
-        return false;
-
-      // Disallow calls which expose returns-twice to a function not previously
-      // attributed as such.
-      if (!ReturnsTwice && CS.isCall() &&
-          cast<CallInst>(CS.getInstruction())->canReturnTwice())
-        return false;
-
-      // Disallow inlining functions that call @llvm.localescape. Doing this
-      // correctly would require major changes to the inliner.
-      if (CS.getCalledFunction() &&
-          CS.getCalledFunction()->getIntrinsicID() ==
-              llvm::Intrinsic::localescape)
-        return false;
-    }
-  }
-
-  return true;
-}
Index: llvm/trunk/lib/Analysis/IPA/LLVMBuild.txt
===================================================================
--- llvm/trunk/lib/Analysis/IPA/LLVMBuild.txt
+++ llvm/trunk/lib/Analysis/IPA/LLVMBuild.txt
@@ -1,23 +0,0 @@
-;===- ./lib/Analysis/IPA/LLVMBuild.txt -------------------------*- Conf -*--===;
-;
-;                     The LLVM Compiler Infrastructure
-;
-; This file is distributed under the University of Illinois Open Source
-; License. See LICENSE.TXT for details.
-;
-;===------------------------------------------------------------------------===;
-;
-; This is an LLVMBuild description file for the components in this subdirectory.
-;
-; For more information on the LLVMBuild system, please see:
-;
-;   http://llvm.org/docs/LLVMBuild.html
-;
-;===------------------------------------------------------------------------===;
-
-[component_0]
-type = Library
-name = IPA
-parent = Libraries
-library_name = ipa
-required_libraries = Analysis Core Support
Index: llvm/trunk/lib/Analysis/IPA/Makefile
===================================================================
--- llvm/trunk/lib/Analysis/IPA/Makefile
+++ llvm/trunk/lib/Analysis/IPA/Makefile
@@ -1,15 +0,0 @@
-##===- lib/Analysis/IPA/Makefile ---------------------------*- Makefile -*-===##
-#
-#                     The LLVM Compiler Infrastructure
-#
-# This file is distributed under the University of Illinois Open Source
-# License. See LICENSE.TXT for details.
-#
-##===----------------------------------------------------------------------===##
-
-LEVEL = ../../..
-LIBRARYNAME = LLVMipa
-BUILD_ARCHIVE = 1
-
-include $(LEVEL)/Makefile.common
-
Index: llvm/trunk/lib/Analysis/InlineCost.cpp
===================================================================
--- llvm/trunk/lib/Analysis/InlineCost.cpp
+++ llvm/trunk/lib/Analysis/InlineCost.cpp
@@ -0,0 +1,1451 @@
+//===- InlineCost.cpp - Cost analysis for inliner -------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements inline cost analysis.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/InlineCost.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CodeMetrics.h"
+#include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/CallingConv.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/GetElementPtrTypeIterator.h"
+#include "llvm/IR/GlobalAlias.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "inline-cost"
+
+STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed");
+
+namespace {
+
+class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
+  typedef InstVisitor<CallAnalyzer, bool> Base;
+  friend class InstVisitor<CallAnalyzer, bool>;
+
+  /// The TargetTransformInfo available for this compilation.
+  const TargetTransformInfo &TTI;
+
+  /// The cache of @llvm.assume intrinsics.
+  AssumptionCacheTracker *ACT;
+
+  // The called function.
+  Function &F;
+
+  // The candidate callsite being analyzed. Please do not use this to do
+  // analysis in the caller function; we want the inline cost query to be
+  // easily cacheable. Instead, use the cover function paramHasAttr.
+  CallSite CandidateCS;
+
+  int Threshold;
+  int Cost;
+
+  bool IsCallerRecursive;
+  bool IsRecursiveCall;
+  bool ExposesReturnsTwice;
+  bool HasDynamicAlloca;
+  bool ContainsNoDuplicateCall;
+  bool HasReturn;
+  bool HasIndirectBr;
+  bool HasFrameEscape;
+
+  /// Number of bytes allocated statically by the callee.
+  uint64_t AllocatedSize;
+  unsigned NumInstructions, NumVectorInstructions;
+  int FiftyPercentVectorBonus, TenPercentVectorBonus;
+  int VectorBonus;
+
+  // While we walk the potentially-inlined instructions, we build up and
+  // maintain a mapping of simplified values specific to this callsite. The
+  // idea is to propagate any special information we have about arguments to
+  // this call through the inlinable section of the function, and account for
+  // likely simplifications post-inlining. The most important aspect we track
+  // is CFG altering simplifications -- when we prove a basic block dead, that
+  // can cause dramatic shifts in the cost of inlining a function.
+  DenseMap<Value *, Constant *> SimplifiedValues;
+
+  // Keep track of the values which map back (through function arguments) to
+  // allocas on the caller stack which could be simplified through SROA.
+  DenseMap<Value *, Value *> SROAArgValues;
+
+  // The mapping of caller Alloca values to their accumulated cost savings. If
+  // we have to disable SROA for one of the allocas, this tells us how much
+  // cost must be added.
+  DenseMap<Value *, int> SROAArgCosts;
+
+  // Keep track of values which map to a pointer base and constant offset.
+  DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs;
+
+  // Custom simplification helper routines.
+  bool isAllocaDerivedArg(Value *V);
+  bool lookupSROAArgAndCost(Value *V, Value *&Arg,
+                            DenseMap<Value *, int>::iterator &CostIt);
+  void disableSROA(DenseMap<Value *, int>::iterator CostIt);
+  void disableSROA(Value *V);
+  void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
+                          int InstructionCost);
+  bool isGEPOffsetConstant(GetElementPtrInst &GEP);
+  bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset);
+  bool simplifyCallSite(Function *F, CallSite CS);
+  ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V);
+
+  /// Return true if the given argument to the function being considered for
+  /// inlining has the given attribute set either at the call site or the
+  /// function declaration.  Primarily used to inspect call site specific
+  /// attributes since these can be more precise than the ones on the callee
+  /// itself. 
+  bool paramHasAttr(Argument *A, Attribute::AttrKind Attr);
+  
+  /// Return true if the given value is known non null within the callee if
+  /// inlined through this particular callsite. 
+  bool isKnownNonNullInCallee(Value *V);
+
+  // Custom analysis routines.
+  bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues);
+
+  // Disable several entry points to the visitor so we don't accidentally use
+  // them by declaring but not defining them here.
+  void visit(Module *);     void visit(Module &);
+  void visit(Function *);   void visit(Function &);
+  void visit(BasicBlock *); void visit(BasicBlock &);
+
+  // Provide base case for our instruction visit.
+  bool visitInstruction(Instruction &I);
+
+  // Our visit overrides.
+  bool visitAlloca(AllocaInst &I);
+  bool visitPHI(PHINode &I);
+  bool visitGetElementPtr(GetElementPtrInst &I);
+  bool visitBitCast(BitCastInst &I);
+  bool visitPtrToInt(PtrToIntInst &I);
+  bool visitIntToPtr(IntToPtrInst &I);
+  bool visitCastInst(CastInst &I);
+  bool visitUnaryInstruction(UnaryInstruction &I);
+  bool visitCmpInst(CmpInst &I);
+  bool visitSub(BinaryOperator &I);
+  bool visitBinaryOperator(BinaryOperator &I);
+  bool visitLoad(LoadInst &I);
+  bool visitStore(StoreInst &I);
+  bool visitExtractValue(ExtractValueInst &I);
+  bool visitInsertValue(InsertValueInst &I);
+  bool visitCallSite(CallSite CS);
+  bool visitReturnInst(ReturnInst &RI);
+  bool visitBranchInst(BranchInst &BI);
+  bool visitSwitchInst(SwitchInst &SI);
+  bool visitIndirectBrInst(IndirectBrInst &IBI);
+  bool visitResumeInst(ResumeInst &RI);
+  bool visitCleanupReturnInst(CleanupReturnInst &RI);
+  bool visitCatchReturnInst(CatchReturnInst &RI);
+  bool visitUnreachableInst(UnreachableInst &I);
+
+public:
+  CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT,
+               Function &Callee, int Threshold, CallSite CSArg)
+    : TTI(TTI), ACT(ACT), F(Callee), CandidateCS(CSArg), Threshold(Threshold),
+        Cost(0), IsCallerRecursive(false), IsRecursiveCall(false),
+        ExposesReturnsTwice(false), HasDynamicAlloca(false),
+        ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false),
+        HasFrameEscape(false), AllocatedSize(0), NumInstructions(0),
+        NumVectorInstructions(0), FiftyPercentVectorBonus(0),
+        TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0),
+        NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0),
+        NumConstantPtrDiffs(0), NumInstructionsSimplified(0),
+        SROACostSavings(0), SROACostSavingsLost(0) {}
+
+  bool analyzeCall(CallSite CS);
+
+  int getThreshold() { return Threshold; }
+  int getCost() { return Cost; }
+
+  // Keep a bunch of stats about the cost savings found so we can print them
+  // out when debugging.
+  unsigned NumConstantArgs;
+  unsigned NumConstantOffsetPtrArgs;
+  unsigned NumAllocaArgs;
+  unsigned NumConstantPtrCmps;
+  unsigned NumConstantPtrDiffs;
+  unsigned NumInstructionsSimplified;
+  unsigned SROACostSavings;
+  unsigned SROACostSavingsLost;
+
+  void dump();
+};
+
+} // namespace
+
+/// \brief Test whether the given value is an Alloca-derived function argument.
+bool CallAnalyzer::isAllocaDerivedArg(Value *V) {
+  return SROAArgValues.count(V);
+}
+
+/// \brief Lookup the SROA-candidate argument and cost iterator which V maps to.
+/// Returns false if V does not map to a SROA-candidate.
+bool CallAnalyzer::lookupSROAArgAndCost(
+    Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) {
+  if (SROAArgValues.empty() || SROAArgCosts.empty())
+    return false;
+
+  DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V);
+  if (ArgIt == SROAArgValues.end())
+    return false;
+
+  Arg = ArgIt->second;
+  CostIt = SROAArgCosts.find(Arg);
+  return CostIt != SROAArgCosts.end();
+}
+
+/// \brief Disable SROA for the candidate marked by this cost iterator.
+///
+/// This marks the candidate as no longer viable for SROA, and adds the cost
+/// savings associated with it back into the inline cost measurement.
+void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) {
+  // If we're no longer able to perform SROA we need to undo its cost savings
+  // and prevent subsequent analysis.
+  Cost += CostIt->second;
+  SROACostSavings -= CostIt->second;
+  SROACostSavingsLost += CostIt->second;
+  SROAArgCosts.erase(CostIt);
+}
+
+/// \brief If 'V' maps to a SROA candidate, disable SROA for it.
+void CallAnalyzer::disableSROA(Value *V) {
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  if (lookupSROAArgAndCost(V, SROAArg, CostIt))
+    disableSROA(CostIt);
+}
+
+/// \brief Accumulate the given cost for a particular SROA candidate.
+void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt,
+                                      int InstructionCost) {
+  CostIt->second += InstructionCost;
+  SROACostSavings += InstructionCost;
+}
+
+/// \brief Check whether a GEP's indices are all constant.
+///
+/// Respects any simplified values known during the analysis of this callsite.
+bool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) {
+  for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I)
+    if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I))
+      return false;
+
+  return true;
+}
+
+/// \brief Accumulate a constant GEP offset into an APInt if possible.
+///
+/// Returns false if unable to compute the offset for any reason. Respects any
+/// simplified values known during the analysis of this callsite.
+bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) {
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  unsigned IntPtrWidth = DL.getPointerSizeInBits();
+  assert(IntPtrWidth == Offset.getBitWidth());
+
+  for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP);
+       GTI != GTE; ++GTI) {
+    ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
+    if (!OpC)
+      if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand()))
+        OpC = dyn_cast<ConstantInt>(SimpleOp);
+    if (!OpC)
+      return false;
+    if (OpC->isZero()) continue;
+
+    // Handle a struct index, which adds its field offset to the pointer.
+    if (StructType *STy = dyn_cast<StructType>(*GTI)) {
+      unsigned ElementIdx = OpC->getZExtValue();
+      const StructLayout *SL = DL.getStructLayout(STy);
+      Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx));
+      continue;
+    }
+
+    APInt TypeSize(IntPtrWidth, DL.getTypeAllocSize(GTI.getIndexedType()));
+    Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize;
+  }
+  return true;
+}
+
+bool CallAnalyzer::visitAlloca(AllocaInst &I) {
+  // Check whether inlining will turn a dynamic alloca into a static
+  // alloca, and handle that case.
+  if (I.isArrayAllocation()) {
+    if (Constant *Size = SimplifiedValues.lookup(I.getArraySize())) {
+      ConstantInt *AllocSize = dyn_cast<ConstantInt>(Size);
+      assert(AllocSize && "Allocation size not a constant int?");
+      Type *Ty = I.getAllocatedType();
+      AllocatedSize += Ty->getPrimitiveSizeInBits() * AllocSize->getZExtValue();
+      return Base::visitAlloca(I);
+    }
+  }
+
+  // Accumulate the allocated size.
+  if (I.isStaticAlloca()) {
+    const DataLayout &DL = F.getParent()->getDataLayout();
+    Type *Ty = I.getAllocatedType();
+    AllocatedSize += DL.getTypeAllocSize(Ty);
+  }
+
+  // We will happily inline static alloca instructions.
+  if (I.isStaticAlloca())
+    return Base::visitAlloca(I);
+
+  // FIXME: This is overly conservative. Dynamic allocas are inefficient for
+  // a variety of reasons, and so we would like to not inline them into
+  // functions which don't currently have a dynamic alloca. This simply
+  // disables inlining altogether in the presence of a dynamic alloca.
+  HasDynamicAlloca = true;
+  return false;
+}
+
+bool CallAnalyzer::visitPHI(PHINode &I) {
+  // FIXME: We should potentially be tracking values through phi nodes,
+  // especially when they collapse to a single value due to deleted CFG edges
+  // during inlining.
+
+  // FIXME: We need to propagate SROA *disabling* through phi nodes, even
+  // though we don't want to propagate it's bonuses. The idea is to disable
+  // SROA if it *might* be used in an inappropriate manner.
+
+  // Phi nodes are always zero-cost.
+  return true;
+}
+
+bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) {
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(),
+                                            SROAArg, CostIt);
+
+  // Try to fold GEPs of constant-offset call site argument pointers. This
+  // requires target data and inbounds GEPs.
+  if (I.isInBounds()) {
+    // Check if we have a base + offset for the pointer.
+    Value *Ptr = I.getPointerOperand();
+    std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr);
+    if (BaseAndOffset.first) {
+      // Check if the offset of this GEP is constant, and if so accumulate it
+      // into Offset.
+      if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) {
+        // Non-constant GEPs aren't folded, and disable SROA.
+        if (SROACandidate)
+          disableSROA(CostIt);
+        return false;
+      }
+
+      // Add the result as a new mapping to Base + Offset.
+      ConstantOffsetPtrs[&I] = BaseAndOffset;
+
+      // Also handle SROA candidates here, we already know that the GEP is
+      // all-constant indexed.
+      if (SROACandidate)
+        SROAArgValues[&I] = SROAArg;
+
+      return true;
+    }
+  }
+
+  if (isGEPOffsetConstant(I)) {
+    if (SROACandidate)
+      SROAArgValues[&I] = SROAArg;
+
+    // Constant GEPs are modeled as free.
+    return true;
+  }
+
+  // Variable GEPs will require math and will disable SROA.
+  if (SROACandidate)
+    disableSROA(CostIt);
+  return false;
+}
+
+bool CallAnalyzer::visitBitCast(BitCastInst &I) {
+  // Propagate constants through bitcasts.
+  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
+  if (!COp)
+    COp = SimplifiedValues.lookup(I.getOperand(0));
+  if (COp)
+    if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) {
+      SimplifiedValues[&I] = C;
+      return true;
+    }
+
+  // Track base/offsets through casts
+  std::pair<Value *, APInt> BaseAndOffset
+    = ConstantOffsetPtrs.lookup(I.getOperand(0));
+  // Casts don't change the offset, just wrap it up.
+  if (BaseAndOffset.first)
+    ConstantOffsetPtrs[&I] = BaseAndOffset;
+
+  // Also look for SROA candidates here.
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
+    SROAArgValues[&I] = SROAArg;
+
+  // Bitcasts are always zero cost.
+  return true;
+}
+
+bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) {
+  // Propagate constants through ptrtoint.
+  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
+  if (!COp)
+    COp = SimplifiedValues.lookup(I.getOperand(0));
+  if (COp)
+    if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) {
+      SimplifiedValues[&I] = C;
+      return true;
+    }
+
+  // Track base/offset pairs when converted to a plain integer provided the
+  // integer is large enough to represent the pointer.
+  unsigned IntegerSize = I.getType()->getScalarSizeInBits();
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  if (IntegerSize >= DL.getPointerSizeInBits()) {
+    std::pair<Value *, APInt> BaseAndOffset
+      = ConstantOffsetPtrs.lookup(I.getOperand(0));
+    if (BaseAndOffset.first)
+      ConstantOffsetPtrs[&I] = BaseAndOffset;
+  }
+
+  // This is really weird. Technically, ptrtoint will disable SROA. However,
+  // unless that ptrtoint is *used* somewhere in the live basic blocks after
+  // inlining, it will be nuked, and SROA should proceed. All of the uses which
+  // would block SROA would also block SROA if applied directly to a pointer,
+  // and so we can just add the integer in here. The only places where SROA is
+  // preserved either cannot fire on an integer, or won't in-and-of themselves
+  // disable SROA (ext) w/o some later use that we would see and disable.
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt))
+    SROAArgValues[&I] = SROAArg;
+
+  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
+}
+
+bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) {
+  // Propagate constants through ptrtoint.
+  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
+  if (!COp)
+    COp = SimplifiedValues.lookup(I.getOperand(0));
+  if (COp)
+    if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) {
+      SimplifiedValues[&I] = C;
+      return true;
+    }
+
+  // Track base/offset pairs when round-tripped through a pointer without
+  // modifications provided the integer is not too large.
+  Value *Op = I.getOperand(0);
+  unsigned IntegerSize = Op->getType()->getScalarSizeInBits();
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  if (IntegerSize <= DL.getPointerSizeInBits()) {
+    std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op);
+    if (BaseAndOffset.first)
+      ConstantOffsetPtrs[&I] = BaseAndOffset;
+  }
+
+  // "Propagate" SROA here in the same manner as we do for ptrtoint above.
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  if (lookupSROAArgAndCost(Op, SROAArg, CostIt))
+    SROAArgValues[&I] = SROAArg;
+
+  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
+}
+
+bool CallAnalyzer::visitCastInst(CastInst &I) {
+  // Propagate constants through ptrtoint.
+  Constant *COp = dyn_cast<Constant>(I.getOperand(0));
+  if (!COp)
+    COp = SimplifiedValues.lookup(I.getOperand(0));
+  if (COp)
+    if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) {
+      SimplifiedValues[&I] = C;
+      return true;
+    }
+
+  // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere.
+  disableSROA(I.getOperand(0));
+
+  return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I);
+}
+
+bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) {
+  Value *Operand = I.getOperand(0);
+  Constant *COp = dyn_cast<Constant>(Operand);
+  if (!COp)
+    COp = SimplifiedValues.lookup(Operand);
+  if (COp) {
+    const DataLayout &DL = F.getParent()->getDataLayout();
+    if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(),
+                                               COp, DL)) {
+      SimplifiedValues[&I] = C;
+      return true;
+    }
+  }
+
+  // Disable any SROA on the argument to arbitrary unary operators.
+  disableSROA(Operand);
+
+  return false;
+}
+
+bool CallAnalyzer::paramHasAttr(Argument *A, Attribute::AttrKind Attr) {
+  unsigned ArgNo = A->getArgNo();
+  return CandidateCS.paramHasAttr(ArgNo+1, Attr);
+}
+
+bool CallAnalyzer::isKnownNonNullInCallee(Value *V) {
+  // Does the *call site* have the NonNull attribute set on an argument?  We
+  // use the attribute on the call site to memoize any analysis done in the
+  // caller. This will also trip if the callee function has a non-null
+  // parameter attribute, but that's a less interesting case because hopefully
+  // the callee would already have been simplified based on that.
+  if (Argument *A = dyn_cast<Argument>(V))
+    if (paramHasAttr(A, Attribute::NonNull))
+      return true;
+  
+  // Is this an alloca in the caller?  This is distinct from the attribute case
+  // above because attributes aren't updated within the inliner itself and we
+  // always want to catch the alloca derived case.
+  if (isAllocaDerivedArg(V))
+    // We can actually predict the result of comparisons between an
+    // alloca-derived value and null. Note that this fires regardless of
+    // SROA firing.
+    return true;
+  
+  return false;
+}
+
+bool CallAnalyzer::visitCmpInst(CmpInst &I) {
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+  // First try to handle simplified comparisons.
+  if (!isa<Constant>(LHS))
+    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
+      LHS = SimpleLHS;
+  if (!isa<Constant>(RHS))
+    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
+      RHS = SimpleRHS;
+  if (Constant *CLHS = dyn_cast<Constant>(LHS)) {
+    if (Constant *CRHS = dyn_cast<Constant>(RHS))
+      if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) {
+        SimplifiedValues[&I] = C;
+        return true;
+      }
+  }
+
+  if (I.getOpcode() == Instruction::FCmp)
+    return false;
+
+  // Otherwise look for a comparison between constant offset pointers with
+  // a common base.
+  Value *LHSBase, *RHSBase;
+  APInt LHSOffset, RHSOffset;
+  std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
+  if (LHSBase) {
+    std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
+    if (RHSBase && LHSBase == RHSBase) {
+      // We have common bases, fold the icmp to a constant based on the
+      // offsets.
+      Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
+      Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
+      if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) {
+        SimplifiedValues[&I] = C;
+        ++NumConstantPtrCmps;
+        return true;
+      }
+    }
+  }
+
+  // If the comparison is an equality comparison with null, we can simplify it
+  // if we know the value (argument) can't be null
+  if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1)) &&
+      isKnownNonNullInCallee(I.getOperand(0))) {
+    bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE;
+    SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType())
+                                      : ConstantInt::getFalse(I.getType());
+    return true;
+  }
+  // Finally check for SROA candidates in comparisons.
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
+    if (isa<ConstantPointerNull>(I.getOperand(1))) {
+      accumulateSROACost(CostIt, InlineConstants::InstrCost);
+      return true;
+    }
+
+    disableSROA(CostIt);
+  }
+
+  return false;
+}
+
+bool CallAnalyzer::visitSub(BinaryOperator &I) {
+  // Try to handle a special case: we can fold computing the difference of two
+  // constant-related pointers.
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+  Value *LHSBase, *RHSBase;
+  APInt LHSOffset, RHSOffset;
+  std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
+  if (LHSBase) {
+    std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS);
+    if (RHSBase && LHSBase == RHSBase) {
+      // We have common bases, fold the subtract to a constant based on the
+      // offsets.
+      Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset);
+      Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset);
+      if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) {
+        SimplifiedValues[&I] = C;
+        ++NumConstantPtrDiffs;
+        return true;
+      }
+    }
+  }
+
+  // Otherwise, fall back to the generic logic for simplifying and handling
+  // instructions.
+  return Base::visitSub(I);
+}
+
+bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  if (!isa<Constant>(LHS))
+    if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS))
+      LHS = SimpleLHS;
+  if (!isa<Constant>(RHS))
+    if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS))
+      RHS = SimpleRHS;
+  Value *SimpleV = nullptr;
+  if (auto FI = dyn_cast<FPMathOperator>(&I))
+    SimpleV =
+        SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL);
+  else
+    SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL);
+
+  if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) {
+    SimplifiedValues[&I] = C;
+    return true;
+  }
+
+  // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
+  disableSROA(LHS);
+  disableSROA(RHS);
+
+  return false;
+}
+
+bool CallAnalyzer::visitLoad(LoadInst &I) {
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
+    if (I.isSimple()) {
+      accumulateSROACost(CostIt, InlineConstants::InstrCost);
+      return true;
+    }
+
+    disableSROA(CostIt);
+  }
+
+  return false;
+}
+
+bool CallAnalyzer::visitStore(StoreInst &I) {
+  Value *SROAArg;
+  DenseMap<Value *, int>::iterator CostIt;
+  if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {
+    if (I.isSimple()) {
+      accumulateSROACost(CostIt, InlineConstants::InstrCost);
+      return true;
+    }
+
+    disableSROA(CostIt);
+  }
+
+  return false;
+}
+
+bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) {
+  // Constant folding for extract value is trivial.
+  Constant *C = dyn_cast<Constant>(I.getAggregateOperand());
+  if (!C)
+    C = SimplifiedValues.lookup(I.getAggregateOperand());
+  if (C) {
+    SimplifiedValues[&I] = ConstantExpr::getExtractValue(C, I.getIndices());
+    return true;
+  }
+
+  // SROA can look through these but give them a cost.
+  return false;
+}
+
+bool CallAnalyzer::visitInsertValue(InsertValueInst &I) {
+  // Constant folding for insert value is trivial.
+  Constant *AggC = dyn_cast<Constant>(I.getAggregateOperand());
+  if (!AggC)
+    AggC = SimplifiedValues.lookup(I.getAggregateOperand());
+  Constant *InsertedC = dyn_cast<Constant>(I.getInsertedValueOperand());
+  if (!InsertedC)
+    InsertedC = SimplifiedValues.lookup(I.getInsertedValueOperand());
+  if (AggC && InsertedC) {
+    SimplifiedValues[&I] = ConstantExpr::getInsertValue(AggC, InsertedC,
+                                                        I.getIndices());
+    return true;
+  }
+
+  // SROA can look through these but give them a cost.
+  return false;
+}
+
+/// \brief Try to simplify a call site.
+///
+/// Takes a concrete function and callsite and tries to actually simplify it by
+/// analyzing the arguments and call itself with instsimplify. Returns true if
+/// it has simplified the callsite to some other entity (a constant), making it
+/// free.
+bool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) {
+  // FIXME: Using the instsimplify logic directly for this is inefficient
+  // because we have to continually rebuild the argument list even when no
+  // simplifications can be performed. Until that is fixed with remapping
+  // inside of instsimplify, directly constant fold calls here.
+  if (!canConstantFoldCallTo(F))
+    return false;
+
+  // Try to re-map the arguments to constants.
+  SmallVector<Constant *, 4> ConstantArgs;
+  ConstantArgs.reserve(CS.arg_size());
+  for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end();
+       I != E; ++I) {
+    Constant *C = dyn_cast<Constant>(*I);
+    if (!C)
+      C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I));
+    if (!C)
+      return false; // This argument doesn't map to a constant.
+
+    ConstantArgs.push_back(C);
+  }
+  if (Constant *C = ConstantFoldCall(F, ConstantArgs)) {
+    SimplifiedValues[CS.getInstruction()] = C;
+    return true;
+  }
+
+  return false;
+}
+
+bool CallAnalyzer::visitCallSite(CallSite CS) {
+  if (CS.hasFnAttr(Attribute::ReturnsTwice) &&
+      !F.hasFnAttribute(Attribute::ReturnsTwice)) {
+    // This aborts the entire analysis.
+    ExposesReturnsTwice = true;
+    return false;
+  }
+  if (CS.isCall() &&
+      cast<CallInst>(CS.getInstruction())->cannotDuplicate())
+    ContainsNoDuplicateCall = true;
+
+  if (Function *F = CS.getCalledFunction()) {
+    // When we have a concrete function, first try to simplify it directly.
+    if (simplifyCallSite(F, CS))
+      return true;
+
+    // Next check if it is an intrinsic we know about.
+    // FIXME: Lift this into part of the InstVisitor.
+    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
+      switch (II->getIntrinsicID()) {
+      default:
+        return Base::visitCallSite(CS);
+
+      case Intrinsic::memset:
+      case Intrinsic::memcpy:
+      case Intrinsic::memmove:
+        // SROA can usually chew through these intrinsics, but they aren't free.
+        return false;
+      case Intrinsic::localescape:
+        HasFrameEscape = true;
+        return false;
+      }
+    }
+
+    if (F == CS.getInstruction()->getParent()->getParent()) {
+      // This flag will fully abort the analysis, so don't bother with anything
+      // else.
+      IsRecursiveCall = true;
+      return false;
+    }
+
+    if (TTI.isLoweredToCall(F)) {
+      // We account for the average 1 instruction per call argument setup
+      // here.
+      Cost += CS.arg_size() * InlineConstants::InstrCost;
+
+      // Everything other than inline ASM will also have a significant cost
+      // merely from making the call.
+      if (!isa<InlineAsm>(CS.getCalledValue()))
+        Cost += InlineConstants::CallPenalty;
+    }
+
+    return Base::visitCallSite(CS);
+  }
+
+  // Otherwise we're in a very special case -- an indirect function call. See
+  // if we can be particularly clever about this.
+  Value *Callee = CS.getCalledValue();
+
+  // First, pay the price of the argument setup. We account for the average
+  // 1 instruction per call argument setup here.
+  Cost += CS.arg_size() * InlineConstants::InstrCost;
+
+  // Next, check if this happens to be an indirect function call to a known
+  // function in this inline context. If not, we've done all we can.
+  Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee));
+  if (!F)
+    return Base::visitCallSite(CS);
+
+  // If we have a constant that we are calling as a function, we can peer
+  // through it and see the function target. This happens not infrequently
+  // during devirtualization and so we want to give it a hefty bonus for
+  // inlining, but cap that bonus in the event that inlining wouldn't pan
+  // out. Pretend to inline the function, with a custom threshold.
+  CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold, CS);
+  if (CA.analyzeCall(CS)) {
+    // We were able to inline the indirect call! Subtract the cost from the
+    // bonus we want to apply, but don't go below zero.
+    Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost());
+  }
+
+  return Base::visitCallSite(CS);
+}
+
+bool CallAnalyzer::visitReturnInst(ReturnInst &RI) {
+  // At least one return instruction will be free after inlining.
+  bool Free = !HasReturn;
+  HasReturn = true;
+  return Free;
+}
+
+bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
+  // We model unconditional branches as essentially free -- they really
+  // shouldn't exist at all, but handling them makes the behavior of the
+  // inliner more regular and predictable. Interestingly, conditional branches
+  // which will fold away are also free.
+  return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
+         dyn_cast_or_null<ConstantInt>(
+             SimplifiedValues.lookup(BI.getCondition()));
+}
+
+bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
+  // We model unconditional switches as free, see the comments on handling
+  // branches.
+  if (isa<ConstantInt>(SI.getCondition()))
+    return true;
+  if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
+    if (isa<ConstantInt>(V))
+      return true;
+
+  // Otherwise, we need to accumulate a cost proportional to the number of
+  // distinct successor blocks. This fan-out in the CFG cannot be represented
+  // for free even if we can represent the core switch as a jumptable that
+  // takes a single instruction.
+  //
+  // NB: We convert large switches which are just used to initialize large phi
+  // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent
+  // inlining those. It will prevent inlining in cases where the optimization
+  // does not (yet) fire.
+  SmallPtrSet<BasicBlock *, 8> SuccessorBlocks;
+  SuccessorBlocks.insert(SI.getDefaultDest());
+  for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I)
+    SuccessorBlocks.insert(I.getCaseSuccessor());
+  // Add cost corresponding to the number of distinct destinations. The first
+  // we model as free because of fallthrough.
+  Cost += (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost;
+  return false;
+}
+
+bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) {
+  // We never want to inline functions that contain an indirectbr.  This is
+  // incorrect because all the blockaddress's (in static global initializers
+  // for example) would be referring to the original function, and this
+  // indirect jump would jump from the inlined copy of the function into the
+  // original function which is extremely undefined behavior.
+  // FIXME: This logic isn't really right; we can safely inline functions with
+  // indirectbr's as long as no other function or global references the
+  // blockaddress of a block within the current function.
+  HasIndirectBr = true;
+  return false;
+}
+
+bool CallAnalyzer::visitResumeInst(ResumeInst &RI) {
+  // FIXME: It's not clear that a single instruction is an accurate model for
+  // the inline cost of a resume instruction.
+  return false;
+}
+
+bool CallAnalyzer::visitCleanupReturnInst(CleanupReturnInst &CRI) {
+  // FIXME: It's not clear that a single instruction is an accurate model for
+  // the inline cost of a cleanupret instruction.
+  return false;
+}
+
+bool CallAnalyzer::visitCatchReturnInst(CatchReturnInst &CRI) {
+  // FIXME: It's not clear that a single instruction is an accurate model for
+  // the inline cost of a cleanupret instruction.
+  return false;
+}
+
+bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) {
+  // FIXME: It might be reasonably to discount the cost of instructions leading
+  // to unreachable as they have the lowest possible impact on both runtime and
+  // code size.
+  return true; // No actual code is needed for unreachable.
+}
+
+bool CallAnalyzer::visitInstruction(Instruction &I) {
+  // Some instructions are free. All of the free intrinsics can also be
+  // handled by SROA, etc.
+  if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I))
+    return true;
+
+  // We found something we don't understand or can't handle. Mark any SROA-able
+  // values in the operand list as no longer viable.
+  for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI)
+    disableSROA(*OI);
+
+  return false;
+}
+
+
+/// \brief Analyze a basic block for its contribution to the inline cost.
+///
+/// This method walks the analyzer over every instruction in the given basic
+/// block and accounts for their cost during inlining at this callsite. It
+/// aborts early if the threshold has been exceeded or an impossible to inline
+/// construct has been detected. It returns false if inlining is no longer
+/// viable, and true if inlining remains viable.
+bool CallAnalyzer::analyzeBlock(BasicBlock *BB,
+                                SmallPtrSetImpl<const Value *> &EphValues) {
+  for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
+    // FIXME: Currently, the number of instructions in a function regardless of
+    // our ability to simplify them during inline to constants or dead code,
+    // are actually used by the vector bonus heuristic. As long as that's true,
+    // we have to special case debug intrinsics here to prevent differences in
+    // inlining due to debug symbols. Eventually, the number of unsimplified
+    // instructions shouldn't factor into the cost computation, but until then,
+    // hack around it here.
+    if (isa<DbgInfoIntrinsic>(I))
+      continue;
+
+    // Skip ephemeral values.
+    if (EphValues.count(I))
+      continue;
+
+    ++NumInstructions;
+    if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy())
+      ++NumVectorInstructions;
+
+    // If the instruction is floating point, and the target says this operation is
+    // expensive or the function has the "use-soft-float" attribute, this may
+    // eventually become a library call.  Treat the cost as such.
+    if (I->getType()->isFloatingPointTy()) {
+      bool hasSoftFloatAttr = false;
+
+      // If the function has the "use-soft-float" attribute, mark it as expensive.
+      if (F.hasFnAttribute("use-soft-float")) {
+        Attribute Attr = F.getFnAttribute("use-soft-float");
+        StringRef Val = Attr.getValueAsString();
+        if (Val == "true")
+          hasSoftFloatAttr = true;
+      }
+
+      if (TTI.getFPOpCost(I->getType()) == TargetTransformInfo::TCC_Expensive ||
+          hasSoftFloatAttr)
+        Cost += InlineConstants::CallPenalty;
+    }
+
+    // If the instruction simplified to a constant, there is no cost to this
+    // instruction. Visit the instructions using our InstVisitor to account for
+    // all of the per-instruction logic. The visit tree returns true if we
+    // consumed the instruction in any way, and false if the instruction's base
+    // cost should count against inlining.
+    if (Base::visit(I))
+      ++NumInstructionsSimplified;
+    else
+      Cost += InlineConstants::InstrCost;
+
+    // If the visit this instruction detected an uninlinable pattern, abort.
+    if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
+        HasIndirectBr || HasFrameEscape)
+      return false;
+
+    // If the caller is a recursive function then we don't want to inline
+    // functions which allocate a lot of stack space because it would increase
+    // the caller stack usage dramatically.
+    if (IsCallerRecursive &&
+        AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
+      return false;
+
+    // Check if we've past the maximum possible threshold so we don't spin in
+    // huge basic blocks that will never inline.
+    if (Cost > Threshold)
+      return false;
+  }
+
+  return true;
+}
+
+/// \brief Compute the base pointer and cumulative constant offsets for V.
+///
+/// This strips all constant offsets off of V, leaving it the base pointer, and
+/// accumulates the total constant offset applied in the returned constant. It
+/// returns 0 if V is not a pointer, and returns the constant '0' if there are
+/// no constant offsets applied.
+ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) {
+  if (!V->getType()->isPointerTy())
+    return nullptr;
+
+  const DataLayout &DL = F.getParent()->getDataLayout();
+  unsigned IntPtrWidth = DL.getPointerSizeInBits();
+  APInt Offset = APInt::getNullValue(IntPtrWidth);
+
+  // Even though we don't look through PHI nodes, we could be called on an
+  // instruction in an unreachable block, which may be on a cycle.
+  SmallPtrSet<Value *, 4> Visited;
+  Visited.insert(V);
+  do {
+    if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
+      if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset))
+        return nullptr;
+      V = GEP->getPointerOperand();
+    } else if (Operator::getOpcode(V) == Instruction::BitCast) {
+      V = cast<Operator>(V)->getOperand(0);
+    } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
+      if (GA->mayBeOverridden())
+        break;
+      V = GA->getAliasee();
+    } else {
+      break;
+    }
+    assert(V->getType()->isPointerTy() && "Unexpected operand type!");
+  } while (Visited.insert(V).second);
+
+  Type *IntPtrTy = DL.getIntPtrType(V->getContext());
+  return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset));
+}
+
+/// \brief Analyze a call site for potential inlining.
+///
+/// Returns true if inlining this call is viable, and false if it is not
+/// viable. It computes the cost and adjusts the threshold based on numerous
+/// factors and heuristics. If this method returns false but the computed cost
+/// is below the computed threshold, then inlining was forcibly disabled by
+/// some artifact of the routine.
+bool CallAnalyzer::analyzeCall(CallSite CS) {
+  ++NumCallsAnalyzed;
+
+  // Perform some tweaks to the cost and threshold based on the direct
+  // callsite information.
+
+  // We want to more aggressively inline vector-dense kernels, so up the
+  // threshold, and we'll lower it if the % of vector instructions gets too
+  // low. Note that these bonuses are some what arbitrary and evolved over time
+  // by accident as much as because they are principled bonuses.
+  //
+  // FIXME: It would be nice to remove all such bonuses. At least it would be
+  // nice to base the bonus values on something more scientific.
+  assert(NumInstructions == 0);
+  assert(NumVectorInstructions == 0);
+  FiftyPercentVectorBonus = 3 * Threshold / 2;
+  TenPercentVectorBonus = 3 * Threshold / 4;
+  const DataLayout &DL = F.getParent()->getDataLayout();
+
+  // Track whether the post-inlining function would have more than one basic
+  // block. A single basic block is often intended for inlining. Balloon the
+  // threshold by 50% until we pass the single-BB phase.
+  bool SingleBB = true;
+  int SingleBBBonus = Threshold / 2;
+
+  // Speculatively apply all possible bonuses to Threshold. If cost exceeds
+  // this Threshold any time, and cost cannot decrease, we can stop processing
+  // the rest of the function body.
+  Threshold += (SingleBBBonus + FiftyPercentVectorBonus);
+
+  // Give out bonuses per argument, as the instructions setting them up will
+  // be gone after inlining.
+  for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) {
+    if (CS.isByValArgument(I)) {
+      // We approximate the number of loads and stores needed by dividing the
+      // size of the byval type by the target's pointer size.
+      PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType());
+      unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType());
+      unsigned PointerSize = DL.getPointerSizeInBits();
+      // Ceiling division.
+      unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize;
+
+      // If it generates more than 8 stores it is likely to be expanded as an
+      // inline memcpy so we take that as an upper bound. Otherwise we assume
+      // one load and one store per word copied.
+      // FIXME: The maxStoresPerMemcpy setting from the target should be used
+      // here instead of a magic number of 8, but it's not available via
+      // DataLayout.
+      NumStores = std::min(NumStores, 8U);
+
+      Cost -= 2 * NumStores * InlineConstants::InstrCost;
+    } else {
+      // For non-byval arguments subtract off one instruction per call
+      // argument.
+      Cost -= InlineConstants::InstrCost;
+    }
+  }
+
+  // If there is only one call of the function, and it has internal linkage,
+  // the cost of inlining it drops dramatically.
+  bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() &&
+    &F == CS.getCalledFunction();
+  if (OnlyOneCallAndLocalLinkage)
+    Cost += InlineConstants::LastCallToStaticBonus;
+
+  // If the instruction after the call, or if the normal destination of the
+  // invoke is an unreachable instruction, the function is noreturn. As such,
+  // there is little point in inlining this unless there is literally zero
+  // cost.
+  Instruction *Instr = CS.getInstruction();
+  if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) {
+    if (isa<UnreachableInst>(II->getNormalDest()->begin()))
+      Threshold = 0;
+  } else if (isa<UnreachableInst>(++BasicBlock::iterator(Instr)))
+    Threshold = 0;
+
+  // If this function uses the coldcc calling convention, prefer not to inline
+  // it.
+  if (F.getCallingConv() == CallingConv::Cold)
+    Cost += InlineConstants::ColdccPenalty;
+
+  // Check if we're done. This can happen due to bonuses and penalties.
+  if (Cost > Threshold)
+    return false;
+
+  if (F.empty())
+    return true;
+
+  Function *Caller = CS.getInstruction()->getParent()->getParent();
+  // Check if the caller function is recursive itself.
+  for (User *U : Caller->users()) {
+    CallSite Site(U);
+    if (!Site)
+      continue;
+    Instruction *I = Site.getInstruction();
+    if (I->getParent()->getParent() == Caller) {
+      IsCallerRecursive = true;
+      break;
+    }
+  }
+
+  // Populate our simplified values by mapping from function arguments to call
+  // arguments with known important simplifications.
+  CallSite::arg_iterator CAI = CS.arg_begin();
+  for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end();
+       FAI != FAE; ++FAI, ++CAI) {
+    assert(CAI != CS.arg_end());
+    if (Constant *C = dyn_cast<Constant>(CAI))
+      SimplifiedValues[FAI] = C;
+
+    Value *PtrArg = *CAI;
+    if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) {
+      ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue());
+
+      // We can SROA any pointer arguments derived from alloca instructions.
+      if (isa<AllocaInst>(PtrArg)) {
+        SROAArgValues[FAI] = PtrArg;
+        SROAArgCosts[PtrArg] = 0;
+      }
+    }
+  }
+  NumConstantArgs = SimplifiedValues.size();
+  NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size();
+  NumAllocaArgs = SROAArgValues.size();
+
+  // FIXME: If a caller has multiple calls to a callee, we end up recomputing
+  // the ephemeral values multiple times (and they're completely determined by
+  // the callee, so this is purely duplicate work).
+  SmallPtrSet<const Value *, 32> EphValues;
+  CodeMetrics::collectEphemeralValues(&F, &ACT->getAssumptionCache(F), EphValues);
+
+  // The worklist of live basic blocks in the callee *after* inlining. We avoid
+  // adding basic blocks of the callee which can be proven to be dead for this
+  // particular call site in order to get more accurate cost estimates. This
+  // requires a somewhat heavyweight iteration pattern: we need to walk the
+  // basic blocks in a breadth-first order as we insert live successors. To
+  // accomplish this, prioritizing for small iterations because we exit after
+  // crossing our threshold, we use a small-size optimized SetVector.
+  typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>,
+                                  SmallPtrSet<BasicBlock *, 16> > BBSetVector;
+  BBSetVector BBWorklist;
+  BBWorklist.insert(&F.getEntryBlock());
+  // Note that we *must not* cache the size, this loop grows the worklist.
+  for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) {
+    // Bail out the moment we cross the threshold. This means we'll under-count
+    // the cost, but only when undercounting doesn't matter.
+    if (Cost > Threshold)
+      break;
+
+    BasicBlock *BB = BBWorklist[Idx];
+    if (BB->empty())
+      continue;
+
+    // Disallow inlining a blockaddress. A blockaddress only has defined
+    // behavior for an indirect branch in the same function, and we do not
+    // currently support inlining indirect branches. But, the inliner may not
+    // see an indirect branch that ends up being dead code at a particular call
+    // site. If the blockaddress escapes the function, e.g., via a global
+    // variable, inlining may lead to an invalid cross-function reference.
+    if (BB->hasAddressTaken())
+      return false;
+
+    // Analyze the cost of this block. If we blow through the threshold, this
+    // returns false, and we can bail on out.
+    if (!analyzeBlock(BB, EphValues)) {
+      if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca ||
+          HasIndirectBr || HasFrameEscape)
+        return false;
+
+      // If the caller is a recursive function then we don't want to inline
+      // functions which allocate a lot of stack space because it would increase
+      // the caller stack usage dramatically.
+      if (IsCallerRecursive &&
+          AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller)
+        return false;
+
+      break;
+    }
+
+    TerminatorInst *TI = BB->getTerminator();
+
+    // Add in the live successors by first checking whether we have terminator
+    // that may be simplified based on the values simplified by this call.
+    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+      if (BI->isConditional()) {
+        Value *Cond = BI->getCondition();
+        if (ConstantInt *SimpleCond
+              = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
+          BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0));
+          continue;
+        }
+      }
+    } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
+      Value *Cond = SI->getCondition();
+      if (ConstantInt *SimpleCond
+            = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) {
+        BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor());
+        continue;
+      }
+    }
+
+    // If we're unable to select a particular successor, just count all of
+    // them.
+    for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize;
+         ++TIdx)
+      BBWorklist.insert(TI->getSuccessor(TIdx));
+
+    // If we had any successors at this point, than post-inlining is likely to
+    // have them as well. Note that we assume any basic blocks which existed
+    // due to branches or switches which folded above will also fold after
+    // inlining.
+    if (SingleBB && TI->getNumSuccessors() > 1) {
+      // Take off the bonus we applied to the threshold.
+      Threshold -= SingleBBBonus;
+      SingleBB = false;
+    }
+  }
+
+  // If this is a noduplicate call, we can still inline as long as
+  // inlining this would cause the removal of the caller (so the instruction
+  // is not actually duplicated, just moved).
+  if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall)
+    return false;
+
+  // We applied the maximum possible vector bonus at the beginning. Now,
+  // subtract the excess bonus, if any, from the Threshold before
+  // comparing against Cost.
+  if (NumVectorInstructions <= NumInstructions / 10)
+    Threshold -= FiftyPercentVectorBonus;
+  else if (NumVectorInstructions <= NumInstructions / 2)
+    Threshold -= (FiftyPercentVectorBonus - TenPercentVectorBonus);
+
+  return Cost < Threshold;
+}
+
+#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
+/// \brief Dump stats about this call's analysis.
+void CallAnalyzer::dump() {
+#define DEBUG_PRINT_STAT(x) dbgs() << "      " #x ": " << x << "\n"
+  DEBUG_PRINT_STAT(NumConstantArgs);
+  DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs);
+  DEBUG_PRINT_STAT(NumAllocaArgs);
+  DEBUG_PRINT_STAT(NumConstantPtrCmps);
+  DEBUG_PRINT_STAT(NumConstantPtrDiffs);
+  DEBUG_PRINT_STAT(NumInstructionsSimplified);
+  DEBUG_PRINT_STAT(NumInstructions);
+  DEBUG_PRINT_STAT(SROACostSavings);
+  DEBUG_PRINT_STAT(SROACostSavingsLost);
+  DEBUG_PRINT_STAT(ContainsNoDuplicateCall);
+  DEBUG_PRINT_STAT(Cost);
+  DEBUG_PRINT_STAT(Threshold);
+#undef DEBUG_PRINT_STAT
+}
+#endif
+
+INITIALIZE_PASS_BEGIN(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
+                      true, true)
+INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_END(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis",
+                    true, true)
+
+char InlineCostAnalysis::ID = 0;
+
+InlineCostAnalysis::InlineCostAnalysis() : CallGraphSCCPass(ID) {}
+
+InlineCostAnalysis::~InlineCostAnalysis() {}
+
+void InlineCostAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.setPreservesAll();
+  AU.addRequired<AssumptionCacheTracker>();
+  AU.addRequired<TargetTransformInfoWrapperPass>();
+  CallGraphSCCPass::getAnalysisUsage(AU);
+}
+
+bool InlineCostAnalysis::runOnSCC(CallGraphSCC &SCC) {
+  TTIWP = &getAnalysis<TargetTransformInfoWrapperPass>();
+  ACT = &getAnalysis<AssumptionCacheTracker>();
+  return false;
+}
+
+InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, int Threshold) {
+  return getInlineCost(CS, CS.getCalledFunction(), Threshold);
+}
+
+/// \brief Test that two functions either have or have not the given attribute
+///        at the same time.
+template<typename AttrKind>
+static bool attributeMatches(Function *F1, Function *F2, AttrKind Attr) {
+  return F1->getFnAttribute(Attr) == F2->getFnAttribute(Attr);
+}
+
+/// \brief Test that there are no attribute conflicts between Caller and Callee
+///        that prevent inlining.
+static bool functionsHaveCompatibleAttributes(Function *Caller,
+                                              Function *Callee,
+                                              TargetTransformInfo &TTI) {
+  return TTI.areInlineCompatible(Caller, Callee) &&
+         attributeMatches(Caller, Callee, Attribute::SanitizeAddress) &&
+         attributeMatches(Caller, Callee, Attribute::SanitizeMemory) &&
+         attributeMatches(Caller, Callee, Attribute::SanitizeThread);
+}
+
+InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee,
+                                             int Threshold) {
+  // Cannot inline indirect calls.
+  if (!Callee)
+    return llvm::InlineCost::getNever();
+
+  // Calls to functions with always-inline attributes should be inlined
+  // whenever possible.
+  if (CS.hasFnAttr(Attribute::AlwaysInline)) {
+    if (isInlineViable(*Callee))
+      return llvm::InlineCost::getAlways();
+    return llvm::InlineCost::getNever();
+  }
+
+  // Never inline functions with conflicting attributes (unless callee has
+  // always-inline attribute).
+  if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee,
+                                         TTIWP->getTTI(*Callee)))
+    return llvm::InlineCost::getNever();
+
+  // Don't inline this call if the caller has the optnone attribute.
+  if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone))
+    return llvm::InlineCost::getNever();
+
+  // Don't inline functions which can be redefined at link-time to mean
+  // something else.  Don't inline functions marked noinline or call sites
+  // marked noinline.
+  if (Callee->mayBeOverridden() ||
+      Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline())
+    return llvm::InlineCost::getNever();
+
+  DEBUG(llvm::dbgs() << "      Analyzing call of " << Callee->getName()
+        << "...\n");
+
+  CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold, CS);
+  bool ShouldInline = CA.analyzeCall(CS);
+
+  DEBUG(CA.dump());
+
+  // Check if there was a reason to force inlining or no inlining.
+  if (!ShouldInline && CA.getCost() < CA.getThreshold())
+    return InlineCost::getNever();
+  if (ShouldInline && CA.getCost() >= CA.getThreshold())
+    return InlineCost::getAlways();
+
+  return llvm::InlineCost::get(CA.getCost(), CA.getThreshold());
+}
+
+bool InlineCostAnalysis::isInlineViable(Function &F) {
+  bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice);
+  for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) {
+    // Disallow inlining of functions which contain indirect branches or
+    // blockaddresses.
+    if (isa<IndirectBrInst>(BI->getTerminator()) || BI->hasAddressTaken())
+      return false;
+
+    for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE;
+         ++II) {
+      CallSite CS(II);
+      if (!CS)
+        continue;
+
+      // Disallow recursive calls.
+      if (&F == CS.getCalledFunction())
+        return false;
+
+      // Disallow calls which expose returns-twice to a function not previously
+      // attributed as such.
+      if (!ReturnsTwice && CS.isCall() &&
+          cast<CallInst>(CS.getInstruction())->canReturnTwice())
+        return false;
+
+      // Disallow inlining functions that call @llvm.localescape. Doing this
+      // correctly would require major changes to the inliner.
+      if (CS.getCalledFunction() &&
+          CS.getCalledFunction()->getIntrinsicID() ==
+              llvm::Intrinsic::localescape)
+        return false;
+    }
+  }
+
+  return true;
+}
Index: llvm/trunk/lib/Analysis/LLVMBuild.txt
===================================================================
--- llvm/trunk/lib/Analysis/LLVMBuild.txt
+++ llvm/trunk/lib/Analysis/LLVMBuild.txt
@@ -15,9 +15,6 @@
 ;
 ;===------------------------------------------------------------------------===;
 
-[common]
-subdirectories = IPA
-
 [component_0]
 type = Library
 name = Analysis
Index: llvm/trunk/lib/Analysis/Makefile
===================================================================
--- llvm/trunk/lib/Analysis/Makefile
+++ llvm/trunk/lib/Analysis/Makefile
@@ -9,7 +9,6 @@
 
 LEVEL = ../..
 LIBRARYNAME = LLVMAnalysis
-DIRS = IPA
 BUILD_ARCHIVE = 1
 
 include $(LEVEL)/Makefile.common
Index: llvm/trunk/lib/LTO/LLVMBuild.txt
===================================================================
--- llvm/trunk/lib/LTO/LLVMBuild.txt
+++ llvm/trunk/lib/LTO/LLVMBuild.txt
@@ -25,7 +25,6 @@
  BitWriter
  CodeGen
  Core
- IPA
  IPO
  InstCombine
  Linker
Index: llvm/trunk/lib/Passes/LLVMBuild.txt
===================================================================
--- llvm/trunk/lib/Passes/LLVMBuild.txt
+++ llvm/trunk/lib/Passes/LLVMBuild.txt
@@ -19,4 +19,4 @@
 type = Library
 name = Passes
 parent = Libraries
-required_libraries = Analysis Core IPA IPO InstCombine Scalar Support TransformUtils Vectorize
+required_libraries = Analysis Core IPO InstCombine Scalar Support TransformUtils Vectorize
Index: llvm/trunk/lib/Transforms/IPO/LLVMBuild.txt
===================================================================
--- llvm/trunk/lib/Transforms/IPO/LLVMBuild.txt
+++ llvm/trunk/lib/Transforms/IPO/LLVMBuild.txt
@@ -20,4 +20,4 @@
 name = IPO
 parent = Transforms
 library_name = ipo
-required_libraries = Analysis Core IPA InstCombine Scalar Support TransformUtils Vectorize
+required_libraries = Analysis Core InstCombine Scalar Support TransformUtils Vectorize
Index: llvm/trunk/lib/Transforms/Utils/LLVMBuild.txt
===================================================================
--- llvm/trunk/lib/Transforms/Utils/LLVMBuild.txt
+++ llvm/trunk/lib/Transforms/Utils/LLVMBuild.txt
@@ -19,4 +19,4 @@
 type = Library
 name = TransformUtils
 parent = Transforms
-required_libraries = Analysis Core IPA Support
+required_libraries = Analysis Core Support
Index: llvm/trunk/tools/bugpoint/CMakeLists.txt
===================================================================
--- llvm/trunk/tools/bugpoint/CMakeLists.txt
+++ llvm/trunk/tools/bugpoint/CMakeLists.txt
@@ -3,7 +3,6 @@
   BitWriter
   CodeGen
   Core
-  IPA
   IPO
   IRReader
   InstCombine
Index: llvm/trunk/tools/bugpoint/bugpoint.cpp
===================================================================
--- llvm/trunk/tools/bugpoint/bugpoint.cpp
+++ llvm/trunk/tools/bugpoint/bugpoint.cpp
@@ -126,7 +126,6 @@
   initializeVectorization(Registry);
   initializeIPO(Registry);
   initializeAnalysis(Registry);
-  initializeIPA(Registry);
   initializeTransformUtils(Registry);
   initializeInstCombine(Registry);
   initializeInstrumentation(Registry);
Index: llvm/trunk/tools/llvm-shlib/CMakeLists.txt
===================================================================
--- llvm/trunk/tools/llvm-shlib/CMakeLists.txt
+++ llvm/trunk/tools/llvm-shlib/CMakeLists.txt
@@ -18,7 +18,6 @@
     DebugInfoDWARF
     DebugInfoPDB
     ExecutionEngine
-    IPA
     IPO
     IRReader
     InstCombine
Index: llvm/trunk/tools/llvm-stress/CMakeLists.txt
===================================================================
--- llvm/trunk/tools/llvm-stress/CMakeLists.txt
+++ llvm/trunk/tools/llvm-stress/CMakeLists.txt
@@ -1,6 +1,6 @@
 set(LLVM_LINK_COMPONENTS
+  Analysis
   Core
-  IPA
   Support
   )
 
Index: llvm/trunk/tools/opt/CMakeLists.txt
===================================================================
--- llvm/trunk/tools/opt/CMakeLists.txt
+++ llvm/trunk/tools/opt/CMakeLists.txt
@@ -4,7 +4,6 @@
   BitWriter
   CodeGen
   Core
-  IPA
   IPO
   IRReader
   InstCombine
Index: llvm/trunk/tools/opt/opt.cpp
===================================================================
--- llvm/trunk/tools/opt/opt.cpp
+++ llvm/trunk/tools/opt/opt.cpp
@@ -312,7 +312,6 @@
   initializeVectorization(Registry);
   initializeIPO(Registry);
   initializeAnalysis(Registry);
-  initializeIPA(Registry);
   initializeTransformUtils(Registry);
   initializeInstCombine(Registry);
   initializeInstrumentation(Registry);
Index: llvm/trunk/unittests/Analysis/CMakeLists.txt
===================================================================
--- llvm/trunk/unittests/Analysis/CMakeLists.txt
+++ llvm/trunk/unittests/Analysis/CMakeLists.txt
@@ -1,5 +1,4 @@
 set(LLVM_LINK_COMPONENTS
-  IPA
   Analysis
   AsmParser
   Core
Index: llvm/trunk/unittests/Analysis/Makefile
===================================================================
--- llvm/trunk/unittests/Analysis/Makefile
+++ llvm/trunk/unittests/Analysis/Makefile
@@ -9,7 +9,7 @@
 
 LEVEL = ../..
 TESTNAME = Analysis
-LINK_COMPONENTS := ipa analysis asmparser
+LINK_COMPONENTS := analysis asmparser
 
 include $(LEVEL)/Makefile.config
 include $(LLVM_SRC_ROOT)/unittests/Makefile.unittest
Index: llvm/trunk/unittests/IR/CMakeLists.txt
===================================================================
--- llvm/trunk/unittests/IR/CMakeLists.txt
+++ llvm/trunk/unittests/IR/CMakeLists.txt
@@ -2,7 +2,6 @@
   Analysis
   AsmParser
   Core
-  IPA
   Support
   )
 
Index: llvm/trunk/unittests/IR/Makefile
===================================================================
--- llvm/trunk/unittests/IR/Makefile
+++ llvm/trunk/unittests/IR/Makefile
@@ -9,7 +9,7 @@
 
 LEVEL = ../..
 TESTNAME = IR
-LINK_COMPONENTS := core ipa asmparser
+LINK_COMPONENTS := core analysis asmparser
 
 include $(LEVEL)/Makefile.config
 include $(LLVM_SRC_ROOT)/unittests/Makefile.unittest