diff --git a/llvm/lib/Analysis/InlineOrder.cpp b/llvm/lib/Analysis/InlineOrder.cpp
--- a/llvm/lib/Analysis/InlineOrder.cpp
+++ b/llvm/lib/Analysis/InlineOrder.cpp
@@ -43,6 +43,63 @@
 
 namespace {
 
+struct MLInlineOrderMetrics {
+  enum class ObjectState { Empty, Tombstone, Valid } State = ObjectState::Empty;
+  int Cost = 0;
+
+  static MLInlineOrderMetrics makeEmptyKey() {
+    MLInlineOrderMetrics M;
+    M.State = ObjectState::Empty;
+    return M;
+  }
+
+  static MLInlineOrderMetrics makeTombstone() {
+    MLInlineOrderMetrics M;
+    M.State = ObjectState::Tombstone;
+    return M;
+  }
+
+  static MLInlineOrderMetrics makeValid(int Cost) {
+    MLInlineOrderMetrics M;
+    M.State = ObjectState::Valid;
+    M.Cost = Cost;
+    return M;
+  }
+
+  bool isValid() const {
+    return State == ObjectState::Valid;
+  }
+  bool operator==(const MLInlineOrderMetrics &R) const {
+    const MLInlineOrderMetrics &L = *this;
+    return L.State == R.State && L.Cost == R.Cost;
+  }
+};
+
+}  // namespace
+
+namespace llvm {
+template <> struct DenseMapInfo<MLInlineOrderMetrics> {
+  static inline MLInlineOrderMetrics getEmptyKey() {
+    return MLInlineOrderMetrics::makeEmptyKey();
+  }
+
+  static inline MLInlineOrderMetrics getTombstoneKey() {
+    return MLInlineOrderMetrics::makeTombstone();
+  }
+
+  static unsigned getHashValue(const MLInlineOrderMetrics &M) {
+    assert(M.isValid() && "Must be in a valid state for hasing");
+    return static_cast<unsigned>(M.Cost);
+  }
+
+  static bool isEqual(const MLInlineOrderMetrics &A, const MLInlineOrderMetrics &B) {
+    return A == B;
+  }
+};
+}
+
+namespace {
+
 llvm::InlineCost getInlineCostWrapper(CallBase &CB,
                                       FunctionAnalysisManager &FAM,
                                       const InlineParams &Params) {
@@ -183,20 +240,42 @@
   MLPriority(const CallBase *CB, FunctionAnalysisManager &FAM,
              const InlineParams &Params) {
     auto IC = getInlineCostWrapper(const_cast<CallBase &>(*CB), FAM, Params);
+    int Cost;
     if (IC.isVariable())
       Cost = IC.getCost();
     else
       Cost = IC.isNever() ? INT_MAX : INT_MIN;
+    Priority = computePriority(MLInlineOrderMetrics::makeValid(Cost));
   }
 
   static bool isMoreDesirable(const MLPriority &P1, const MLPriority &P2) {
-    return P1.Cost < P2.Cost;
+    return P1.Priority < P2.Priority;
   }
 
 private:
-  int Cost = INT_MAX;
+  int computePriority(const MLInlineOrderMetrics &M) {
+    auto It = MetricsToPriority->find(M);
+    if (It != MetricsToPriority->end()) {
+      return It->second;
+    }
+
+    // Compute the order.  This is to be replaced with ML.  Use the identify
+    // function for now.
+    int Priority = M.Cost;
+
+    // Cache the order.
+    (*MetricsToPriority)[M] = Priority;
+
+    return Priority;
+  }
+
+  static ManagedStatic<DenseMap<MLInlineOrderMetrics, int>> MetricsToPriority;
+
+  int Priority = INT_MAX;
 };
 
+ManagedStatic<DenseMap<MLInlineOrderMetrics, int>> MLPriority::MetricsToPriority;
+
 template <typename PriorityT>
 class PriorityInlineOrder : public InlineOrder<std::pair<CallBase *, int>> {
   using T = std::pair<CallBase *, int>;