Heavily refactor code:

  * Separate the policy decisions into a derived class [InlineSimple]
  * Move the inlining mechanics into a base class [Inliner]
  * Change the inliner to be an SCCPass, making it more structured and
    eventually pipelinable with other SCC passes


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@8257 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 198 insertions, 127 deletions

diff --git a/lib/Transforms/IPO/InlineSimple.cpp b/lib/Transforms/IPO/InlineSimple.cpp
index 64a210d30f..e62a8b1344 100644
--- a/lib/Transforms/IPO/InlineSimple.cpp
+++ b/lib/Transforms/IPO/InlineSimple.cpp
@@ -1,77 +1,47 @@
-//===- FunctionInlining.cpp - Code to perform function inlining -----------===//
+//===- InlineSimple.cpp - Code to perform simple function inlining --------===//
 //
 // This file implements bottom-up inlining of functions into callees.
 //
 //===----------------------------------------------------------------------===//
 
-#define DEBUG_TYPE "inline"
-#include "llvm/Transforms/IPO.h"
-#include "llvm/Module.h"
-#include "llvm/Pass.h"
-#include "llvm/iOther.h"
+#include "Inliner.h"
+#include "llvm/Function.h"
 #include "llvm/iMemory.h"
-#include "llvm/iTerminators.h"
 #include "llvm/Support/CallSite.h"
-#include "llvm/Transforms/Utils/Cloning.h"
-#include "Support/CommandLine.h"
-#include "Support/Debug.h"
-#include "Support/Statistic.h"
-#include <set>
+#include "llvm/Transforms/IPO.h"
 
 namespace {
-  Statistic<> NumInlined("inline", "Number of functions inlined");
-  Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found");
-  cl::opt<unsigned>             // FIXME: 200 is VERY conservative
-  InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
-              cl::desc("Control the amount of inlining to perform (default = 200)"));
-
-  struct FunctionInlining : public Pass {
-    virtual bool run(Module &M) {
-      bool Changed = false;
-      for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
-        Changed |= doInlining(I);
-      ProcessedFunctions.clear();
-      return Changed;
-    }
-
-  private:
-    std::set<Function*> ProcessedFunctions;  // Prevent infinite recursion
-    bool doInlining(Function *F);
+  struct SimpleInliner : public Inliner {
+    int getInlineCost(CallSite CS);
   };
-  RegisterOpt<FunctionInlining> X("inline", "Function Integration/Inlining");
+  RegisterOpt<SimpleInliner> X("inline", "Function Integration/Inlining");
 }
 
-Pass *createFunctionInliningPass() { return new FunctionInlining(); }
+Pass *createFunctionInliningPass() { return new SimpleInliner(); }
 
 
-// ShouldInlineFunction - The heuristic used to determine if we should inline
-// the function call or not.
+// getInlineCost - The heuristic used to determine if we should inline the
+// function call or not.
 //
-static inline bool ShouldInlineFunction(CallSite CS) {
+int SimpleInliner::getInlineCost(CallSite CS) {
   Instruction *TheCall = CS.getInstruction();
-  assert(TheCall->getParent() && TheCall->getParent()->getParent() && 
-	 "Call not embedded into a function!");
-
   const Function *Callee = CS.getCalledFunction();
-  if (Callee == 0 || Callee->isExternal())
-    return false;  // Cannot inline an indirect call... or external function.
-
-  // Don't inline a recursive call.
   const Function *Caller = TheCall->getParent()->getParent();
-  if (Caller == Callee) return false;
 
-  // InlineQuality - This value measures how good of an inline candidate this
-  // call site is to inline.  The initial value determines how aggressive the
-  // inliner is.  If this value is negative after the final computation,
-  // inlining is not performed.
+  // Don't inline a directly recursive call.
+  if (Caller == Callee) return 2000000000;
+
+  // InlineCost - This value measures how good of an inline candidate this call
+  // site is to inline.  A lower inline cost make is more likely for the call to
+  // be inlined.  This value may go negative.
   //
-  int InlineQuality = InlineLimit;
+  int InlineCost = 0;
 
   // If there is only one call of the function, and it has internal linkage,
   // make it almost guaranteed to be inlined.
   //
   if (Callee->use_size() == 1 && Callee->hasInternalLinkage())
-    InlineQuality += 30000;
+    InlineCost -= 30000;
 
   // Add to the inline quality for properties that make the call valueable to
   // inline.  This includes factors that indicate that the result of inlining
@@ -83,12 +53,12 @@ static inline bool ShouldInlineFunction(CallSite CS) {
     // Each argument passed in has a cost at both the caller and the callee
     // sides.  This favors functions that take many arguments over functions
     // that take few arguments.
-    InlineQuality += 20;
+    InlineCost -= 20;
 
     // If this is a function being passed in, it is very likely that we will be
     // able to turn an indirect function call into a direct function call.
     if (isa<Function>(I))
-      InlineQuality += 100;
+      InlineCost -= 100;
 
     // If a constant, global variable or alloca is passed in, inlining this
     // function is likely to allow significant future optimization possibilities
@@ -96,7 +66,7 @@ static inline bool ShouldInlineFunction(CallSite CS) {
     // the inlining of the function.
     //
     else if (isa<Constant>(I) || isa<GlobalVariable>(I) || isa<AllocaInst>(I))
-      InlineQuality += 60;
+      InlineCost -= 60;
   }
 
   // Now that we have considered all of the factors that make the call site more
@@ -106,84 +76,14 @@ static inline bool ShouldInlineFunction(CallSite CS) {
   // Look at the size of the callee.  Each basic block counts as 20 units, and
   // each instruction counts as 10.
   for (Function::const_iterator BB = Callee->begin(), E = Callee->end();
-       BB != E; ++BB) {
-    InlineQuality -= BB->size()*10 + 20;
-    if (InlineQuality < 0) return false;
-  }
+       BB != E; ++BB)
+    InlineCost += BB->size()*10 + 20;
 
   // Don't inline into something too big, which would make it bigger.  Here, we
   // count each basic block as a single unit.
   for (Function::const_iterator BB = Caller->begin(), E = Caller->end();
-       BB != E; ++BB) {
-    --InlineQuality;
-    if (InlineQuality < 0) return false;
-  }
+       BB != E; ++BB)
+    InlineCost++;
 
-  // If we get here, this call site is high enough "quality" to inline.
-  DEBUG(std::cerr << "Inlining in '" << Caller->getName()
-                  << "', quality = " << InlineQuality << ": " << *TheCall);
-  return true;
+  return InlineCost;
 }
-
-
-// doInlining - Use a heuristic based approach to inline functions that seem to
-// look good.
-//
-bool FunctionInlining::doInlining(Function *F) {
-  // If we have already processed this function (ie, it is recursive) don't
-  // revisit.
-  std::set<Function*>::iterator PFI = ProcessedFunctions.lower_bound(F);
-  if (PFI != ProcessedFunctions.end() && *PFI == F) return false;
-
-  // Insert the function in the set so it doesn't get revisited.
-  ProcessedFunctions.insert(PFI, F);
-
-  bool Changed = false;
-  for (Function::iterator BB = F->begin(); BB != F->end(); ++BB)
-    for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
-      bool ShouldInc = true;
-      // Found a call or invoke instruction?
-      if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
-        CallSite CS = CallSite::get(I);
-        if (Function *Callee = CS.getCalledFunction()) {
-          doInlining(Callee);  // Inline in callees before callers!
-
-          // Decide whether we should inline this function...
-          if (ShouldInlineFunction(CS)) {
-            // Save an iterator to the instruction before the call if it exists,
-            // otherwise get an iterator at the end of the block... because the
-            // call will be destroyed.
-            //
-            BasicBlock::iterator SI;
-            if (I != BB->begin()) {
-              SI = I; --SI;           // Instruction before the call...
-            } else {
-              SI = BB->end();
-            }
-            
-            // Attempt to inline the function...
-            if (InlineFunction(CS)) {
-              ++NumInlined;
-              Changed = true;
-              // Move to instruction before the call...
-              I = (SI == BB->end()) ? BB->begin() : SI;
-              ShouldInc = false;  // Don't increment iterator until next time
-              
-              // If we inlined the last possible call site to the function,
-              // delete the function body now.
-              if (Callee->use_empty() &&
-                  (Callee->hasInternalLinkage()||Callee->hasLinkOnceLinkage())){
-                F->getParent()->getFunctionList().erase(Callee);
-                ++NumDeleted;              
-                if (Callee == F) return true;
-              }
-            }
-          }
-        }
-      }
-      if (ShouldInc) ++I;
-    }
-
-  return Changed;
-}
-
diff --git a/lib/Transforms/IPO/Inliner.cpp b/lib/Transforms/IPO/Inliner.cpp
new file mode 100644
index 0000000000..7f75f1453f
--- /dev/null
+++ b/lib/Transforms/IPO/Inliner.cpp
@@ -0,0 +1,119 @@
+//===- InlineCommon.cpp - Code common to all inliners ---------------------===//
+//
+// This file implements the code shared between the LLVM inliners.  This
+// implements all of the boring mechanics of the bottom-up inlining.
+//
+//===----------------------------------------------------------------------===//
+
+#include "Inliner.h"
+#include "llvm/Module.h"
+#include "llvm/iOther.h"
+#include "llvm/iTerminators.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Support/CallSite.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "Support/CommandLine.h"
+#include "Support/Debug.h"
+#include "Support/Statistic.h"
+
+namespace {
+  Statistic<> NumInlined("inline", "Number of functions inlined");
+  Statistic<> NumDeleted("inline", "Number of functions deleted because all callers found");
+  cl::opt<unsigned>             // FIXME: 200 is VERY conservative
+  InlineLimit("inline-threshold", cl::Hidden, cl::init(200),
+              cl::desc("Control the amount of inlining to perform (default = 200)"));
+}
+
+Inliner::Inliner() : InlineThreshold(InlineLimit) {}
+
+int Inliner::getRecursiveInlineCost(CallSite CS) {
+  return getInlineCost(CS);
+}
+
+bool Inliner::runOnSCC(const std::vector<CallGraphNode*> &SCC) {
+  CallGraph &CG = getAnalysis<CallGraph>();
+
+  std::set<Function*> SCCFunctions;
+  DEBUG(std::cerr << "Inliner visiting SCC:");
+  for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
+    SCCFunctions.insert(SCC[i]->getFunction());
+    DEBUG(std::cerr << " " << (SCC[i]->getFunction() ?
+              SCC[i]->getFunction()->getName() : "INDIRECTNODE"));
+  }
+  DEBUG(std::cerr << "\n");
+
+  bool Changed = false;
+  for (std::set<Function*>::iterator SCCI = SCCFunctions.begin(),
+         E = SCCFunctions.end(); SCCI != E; ++SCCI) {
+    Function *F = *SCCI;
+    if (F == 0 || F->isExternal()) continue;
+    DEBUG(std::cerr << "  Inspecting function: " << F->getName() << "\n");
+
+    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
+      for (BasicBlock::iterator I = BB->begin(); I != BB->end(); ) {
+        bool ShouldInc = true;
+        // Found a call or invoke instruction?
+        if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
+          CallSite CS = CallSite::get(I);
+          if (Function *Callee = CS.getCalledFunction())
+            if (!Callee->isExternal()) {
+              // Determine whether this is a function IN the SCC...
+              bool inSCC = SCCFunctions.count(Callee);
+
+              // If the policy determines that we should inline this function,
+              // try to do so...
+              int InlineCost = inSCC ? getRecursiveInlineCost(CS) :
+                                       getInlineCost(CS);
+              if (InlineCost < (int)InlineThreshold) {
+                DEBUG(std::cerr << "    Inlining: cost=" << InlineCost
+                                << ", Call: " << *CS.getInstruction());
+
+                // Save an iterator to the instruction before the call if it
+                // exists, otherwise get an iterator at the end of the
+                // block... because the call will be destroyed.
+                //
+                BasicBlock::iterator SI;
+                if (I != BB->begin()) {
+                  SI = I; --SI;           // Instruction before the call...
+                } else {
+                  SI = BB->end();
+                }
+                
+                if (performInlining(CS, SCCFunctions)) {
+                  // Move to instruction before the call...
+                  I = (SI == BB->end()) ? BB->begin() : SI;
+                  ShouldInc = false; // Don't increment iterator until next time
+                  Changed = true;
+                }
+              }
+            }
+        }
+        if (ShouldInc) ++I;
+      }
+  }
+  return Changed;
+}
+
+bool Inliner::performInlining(CallSite CS, std::set<Function*> &SCC) {
+  Function *Callee = CS.getCalledFunction();
+  Function *Caller = CS.getInstruction()->getParent()->getParent();
+
+  // Attempt to inline the function...
+  if (!InlineFunction(CS)) return false;
+  ++NumInlined;
+              
+  // If we inlined the last possible call site to the function,
+  // delete the function body now.
+  if (Callee->use_empty() && Callee != Caller &&
+      (Callee->hasInternalLinkage() || Callee->hasLinkOnceLinkage())) {
+    DEBUG(std::cerr << "    -> Deleting dead function: "
+                    << Callee->getName() << "\n");
+    std::set<Function*>::iterator I = SCC.find(Callee);
+    if (I != SCC.end())       // Remove function from this SCC...
+      SCC.erase(I);
+
+    Callee->getParent()->getFunctionList().erase(Callee);
+    ++NumDeleted;
+  }
+  return true; 
+}
diff --git a/lib/Transforms/IPO/Inliner.h b/lib/Transforms/IPO/Inliner.h
new file mode 100644
index 0000000000..a6422951ce
--- /dev/null
+++ b/lib/Transforms/IPO/Inliner.h
@@ -0,0 +1,52 @@
+//===- InlineCommon.h - Code common to all inliners -------------*- C++ -*-===//
+//
+// This file defines a simple policy-based bottom-up inliner.  This file
+// implements all of the boring mechanics of the bottom-up inlining, while the
+// subclass determines WHAT to inline, which is the much more interesting
+// component.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef INLINER_H
+#define INLINER_H
+
+#define DEBUG_TYPE "inline"
+#include "llvm/CallGraphSCCPass.h"
+#include <set>
+class CallSite;
+
+/// Inliner - This class contains all of the helper code which is used to
+/// perform the inlining operations that does not depend on the policy.
+///
+struct Inliner : public CallGraphSCCPass {
+  Inliner();
+
+  // Main run interface method, this implements the interface required by the
+  // Pass class.
+  virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
+
+  /// This method returns the value specified by the -inline-threshold value,
+  /// specified on the command line.  This is typically not directly needed.
+  ///
+  unsigned getInlineThreshold() const { return InlineThreshold; }
+
+  /// getInlineCost - This method must be implemented by the subclass to
+  /// determine the cost of inlining the specified call site.  If the cost
+  /// returned is greater than the current inline threshold, the call site is
+  /// not inlined.
+  ///
+  virtual int getInlineCost(CallSite CS) = 0;
+  
+  /// getRecursiveInlineCost - This method can be implemented by subclasses if
+  /// it wants to treat calls to functions within the current SCC specially.  If
+  /// this method is not overloaded, it just chains to getInlineCost().
+  ///
+  virtual int getRecursiveInlineCost(CallSite CS);
+
+private:
+  unsigned InlineThreshold;
+  bool performInlining(CallSite CS, std::set<Function*> &SCC);
+};
+
+
+#endif