diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp
--- a/llvm/lib/Transforms/IPO/Inliner.cpp
+++ b/llvm/lib/Transforms/IPO/Inliner.cpp
@@ -16,6 +16,7 @@
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/PriorityQueue.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SetVector.h"
@@ -682,7 +683,7 @@
 
   virtual void pop() = 0;
 
-  virtual reference front() = 0;
+  virtual T front() = 0;
 
   virtual void erase_if(function_ref<bool(T)> Pred) = 0;
 
@@ -703,7 +704,7 @@
     FirstIndex++;
   }
 
-  reference front() override {
+  T front() override {
     assert(size() > 0);
     return Calls[FirstIndex];
   }
@@ -718,6 +719,64 @@
   size_t FirstIndex = 0;
 };
 
+class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
+  using T = std::pair<CallBase *, int>;
+  using reference = T &;
+
+  struct Compare {
+    bool operator()(const T &P1, const T &P2) { return P1.second > P2.second; }
+  };
+
+  int evaluate(CallBase *CB) {
+    Function *Callee = CB->getCalledFunction();
+    return (int)Callee->getInstructionCount();
+  }
+
+public:
+  size_t size() override { return PQ.size(); }
+
+  void push(const T &Elt) override {
+    CallBase *CB = Elt.first;
+    const int InlineHistoryID = Elt.second;
+    const int Goodness = evaluate(CB);
+
+    PQ.push({CB, Goodness});
+    InlineHistoryMap[CB] = InlineHistoryID;
+  }
+
+  void pop() override {
+    assert(size() > 0);
+
+    auto &Elt = PQ.top();
+    CallBase *CB = Elt.first;
+    InlineHistoryMap.erase(CB);
+    PQ.pop();
+  }
+
+  T front() override {
+    assert(size() > 0);
+    CallBase *CB = PQ.top().first;
+    return std::make_pair(CB, InlineHistoryMap[CB]);
+  }
+
+  void erase_if(function_ref<bool(T)> Pred) override {
+    PriorityQueue<T, std::vector<T>, Compare> TempPQ;
+    while (!PQ.empty()) {
+      auto P = PQ.top();
+      PQ.pop();
+      if (Pred({P.first, 0}))
+        InlineHistoryMap.erase(P.first);
+      else
+        TempPQ.push(P);
+    }
+    PQ = std::move(TempPQ);
+  }
+
+private:
+  PriorityQueue<T, std::vector<T>, Compare> PQ;
+  DenseMap<CallBase *, int> InlineHistoryMap;
+};
+
 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
                                    CGSCCAnalysisManager &AM, LazyCallGraph &CG,
                                    CGSCCUpdateResult &UR) {
@@ -762,7 +821,7 @@
   // this model, but it is uniformly spread across all the functions in the SCC
   // and eventually they all become too large to inline, rather than
   // incrementally maknig a single function grow in a super linear fashion.
-  DefaultInlineOrder<std::pair<CallBase *, int>> Calls;
+  PriorityInlineOrder Calls;
 
   // Populate the initial list of calls in this SCC.
   for (auto &N : InitialC) {
@@ -838,7 +897,7 @@
     // call graph and prepare the context of that new caller.
     bool DidInline = false;
     while (!Calls.empty() && Calls.front().first->getCaller() == &F) {
-      auto &P = Calls.front();
+      auto P = Calls.front();
       Calls.pop();
       CallBase *CB = P.first;
       const int InlineHistoryID = P.second;