Index: llvm/include/llvm/Transforms/IPO/Attributor.h
===================================================================
--- llvm/include/llvm/Transforms/IPO/Attributor.h
+++ llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -134,6 +134,16 @@
 
 class Function;
 
+namespace InternalizeConstants {
+/// Default threshold
+const int DefaultThreshold = 100;
+
+// Various magic constants used to adjust heuristics
+const int InstrCost = 5;
+const int DepBonus = 5;
+
+} // namespace InternalizeConstants
+
 /// Simple enum classes that forces properties to be spelled out explicitly.
 ///
 ///{
@@ -151,6 +161,57 @@
 };
 ///}
 
+/// Represents the cost of internalizing a function.
+///
+/// The cost represents a unitless amount; smaller values increase the
+/// likelihood of the function being internalized.
+class InternalizeCost {
+  enum SentinelValues {
+    AlwaysInternalizeCost = INT_MIN,
+    NeverInternalizeCost = INT_MAX
+  };
+
+  /// The function to be internalized
+  Function &F;
+
+  /// The estimated cost of internalizing a function
+  int Cost = 0;
+
+  /// The threshold against which this cost is computed.
+  int Threshold = 0;
+
+  /// Trivial constructor
+  InternalizeCost(Function &F, int Cost, int Threshold)
+      : F(F), Cost(Cost), Threshold(Threshold) {}
+
+public:
+  static InternalizeCost get(int Cost, int Threshold, Function &F) {
+    return InternalizeCost(F, Cost, Threshold);
+  }
+  static InternalizeCost getNever(Function &F) {
+    return InternalizeCost(F, NeverInternalizeCost, 0);
+  }
+  static InternalizeCost getAlways(Function &F) {
+    return InternalizeCost(F, AlwaysInternalizeCost, 0);
+  }
+
+  /// Test whether the internalize cost is low enough for internalizing
+  explicit operator bool() const { return Cost < Threshold; }
+
+  /// Get the function this cost corresponds to
+  Function &getFunction() const { return F; }
+
+  /// Get the internalize cost estimate.
+  int getCost() const { return Cost; }
+
+  /// Get the threshold against which the cost was computed.
+  int getThreshold() const { return Threshold; }
+
+  /// Get the cost delta from the threshold for internalizing.
+  /// Returns a negative value if the cost is too high to internalize
+  int getCostDelta() const { return Threshold - getCost(); }
+};
+
 /// The data structure for the nodes of a dependency graph
 struct AADepGraphNode {
 public:
@@ -1072,6 +1133,10 @@
   void recordDependence(const AbstractAttribute &FromAA,
                         const AbstractAttribute &ToAA, DepClassTy DepClass);
 
+  /// Calculate the cost of internalizing the function \p F and determine whether
+  /// internalizing such function could be beneficial.
+  InternalizeCost getInternalizeCost(Function &F);
+
   /// Introduce a new abstract attribute into the fixpoint analysis.
   ///
   /// Note that ownership of the attribute is given to the Attributor. It will
Index: llvm/lib/Transforms/IPO/Attributor.cpp
===================================================================
--- llvm/lib/Transforms/IPO/Attributor.cpp
+++ llvm/lib/Transforms/IPO/Attributor.cpp
@@ -1351,6 +1351,18 @@
   return CS;
 }
 
+InternalizeCost Attributor::getInternalizeCost(Function &F) {
+  /// TODO: for now we only rule out situations where the function cannot be
+  ///       internalized. The detailed algorithm will be implemented later.
+  if (F.hasExactDefinition() || !F.getNumUses() ||
+      F.getLinkage() == GlobalValue::LinkOnceAnyLinkage ||
+      F.getLinkage() == GlobalValue::WeakAnyLinkage) {
+    return InternalizeCost::getNever(F);
+  }
+
+  return InternalizeCost::getAlways(F);
+}
+
 /// Create a shallow wrapper for \p F such that \p F has internal linkage
 /// afterwards. It also sets the original \p F 's name to anonymous
 ///
@@ -2186,9 +2198,7 @@
   //       a function is "benefitial"
   if (AllowDeepWrapper)
     for (Function *F : Functions)
-      if (!F->hasExactDefinition() && F->getNumUses() &&
-          F->getLinkage() != llvm::GlobalValue::LinkOnceAnyLinkage &&
-          F->getLinkage() != llvm::GlobalValue::WeakAnyLinkage) {
+      if (A.getInternalizeCost(*F)) {
         Function *NewF = internalizeFunction(*F);
         Functions.insert(NewF);