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,58 @@
 };
 ///}
 
+/// 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 *new InternalizeCost(F, Cost, Threshold);
+  }
+  static InternalizeCost &getNever(Function &F) {
+    return *new InternalizeCost(F, NeverInternalizeCost, 0);
+  }
+  static InternalizeCost &getAlways(Function &F) {
+    return *new InternalizeCost(F, AlwaysInternalizeCost, 0);
+  }
+
+  /// Test whether the internalize cost is low enough for internalizing
+  explicit operator bool() const { return Cost < Threshold; }
+  bool shouldInternalize() 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:
@@ -1123,6 +1185,9 @@
   /// various places.
   void identifyDefaultAbstractAttributes(Function &F);
 
+  /// Determine whether the function \p F can be internalized
+  bool shouldInternalizeFunction(Function &F);
+
   /// Determine whether the function \p F is IPO amendable
   ///
   /// If a function is exactly defined or it has alwaysinline attribute
@@ -1507,6 +1572,9 @@
   /// A set to remember the functions we already assume to be live and visited.
   DenseSet<const Function *> VisitedFunctions;
 
+  /// A map for caching results of queries for getInternalizeCost
+  DenseMap<const Function *, InternalizeCost *> InternalizationMap;
+
   /// Uses we replace with a new value after manifest is done. We will remove
   /// then trivially dead instructions as well.
   DenseMap<Use *, Value *> ToBeChangedUses;
Index: llvm/lib/Transforms/IPO/Attributor.cpp
===================================================================
--- llvm/lib/Transforms/IPO/Attributor.cpp
+++ llvm/lib/Transforms/IPO/Attributor.cpp
@@ -173,6 +173,20 @@
   llvm_unreachable("Expected enum or string attribute!");
 }
 
+/// Calculate the cost of internalizing the function \p F and determine whether
+/// internalizing such function could be beneficial.
+static InternalizeCost &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.isDeclaration() || F.hasExactDefinition() || !F.getNumUses() ||
+      F.getLinkage() == GlobalValue::LinkOnceAnyLinkage ||
+      F.getLinkage() == GlobalValue::WeakAnyLinkage) {
+    return InternalizeCost::getNever(F);
+  }
+
+  return InternalizeCost::getAlways(F);
+}
+
 Argument *IRPosition::getAssociatedArgument() const {
   if (getPositionKind() == IRP_ARGUMENT)
     return cast<Argument>(&getAnchorValue());
@@ -2073,6 +2087,15 @@
   assert(Success && "Expected the check call to be successful!");
 }
 
+bool Attributor::shouldInternalizeFunction(Function &F) {
+  if (auto *IC = InternalizationMap[&F])
+    return IC->shouldInternalize();
+  else {
+    InternalizationMap[&F] = &getInternalizeCost(F);
+    return InternalizationMap[&F]->shouldInternalize();
+  }
+}
+
 /// Helpers to ease debugging through output streams and print calls.
 ///
 ///{
@@ -2186,9 +2209,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.shouldInternalizeFunction(*F)) {
         Function *NewF = internalizeFunction(*F);
         Functions.insert(NewF);