Index: lld/test/ELF/lto/cache.ll
===================================================================
--- lld/test/ELF/lto/cache.ll
+++ lld/test/ELF/lto/cache.ll
@@ -31,6 +31,20 @@
 ; RUN: ld.lld --thinlto-cache-dir=%t.cache --thinlto-cache-policy prune_after=0s:cache_size=0%:cache_size_files=1:prune_interval=0s -o %t3 %t2.o %t.o
 ; RUN: ls %t.cache | count 3
 
+; Check that we remove the least recently used file first.
+; RUN: rm -fr %t.cache
+; RUN: mkdir %t.cache
+; RUN: echo xyz > %t.cache/llvmcache-old
+; RUN: touch -t 198002011200 %t.cache/llvmcache-old
+; RUN: echo xyz > %t.cache/llvmcache-newer
+; RUN: touch -t 198002021200 %t.cache/llvmcache-newer
+; RUN: ld.lld --thinlto-cache-dir=%t.cache --thinlto-cache-policy prune_after=0s:cache_size=0%:cache_size_files=3:prune_interval=0s -o %t3 %t2.o %t.o
+; RUN: ls %t.cache | FileCheck %s
+
+; CHECK-NOT: llvmcache-old
+; CHECK: llvmcache-newer
+; CHECK-NOT: llvmcache-old
+
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
Index: llvm/lib/Support/CachePruning.cpp
===================================================================
--- llvm/lib/Support/CachePruning.cpp
+++ llvm/lib/Support/CachePruning.cpp
@@ -27,6 +27,28 @@
 
 using namespace llvm;
 
+namespace {
+struct FileInfo {
+  sys::TimePoint<> Time;
+  uint64_t Size;
+  std::string Path;
+
+  /// Used to determine which files to prune first. Also used to determine
+  /// set membership, so must take into account all fields.
+  bool operator<(const FileInfo &Other) const {
+    if (Time < Other.Time)
+      return true;
+    else if (Other.Time < Time)
+      return false;
+    if (Other.Size < Size)
+      return true;
+    else if (Size < Other.Size)
+      return false;
+    return Path < Other.Path;
+  }
+};
+} // anonymous namespace
+
 /// Write a new timestamp file with the given path. This is used for the pruning
 /// interval option.
 static void writeTimestampFile(StringRef TimestampFile) {
@@ -185,8 +207,9 @@
     writeTimestampFile(TimestampFile);
   }
 
-  // Keep track of space. Needs to be kept ordered by size for determinism.
-  std::set<std::pair<uint64_t, std::string>> FileSizes;
+  // Keep track of files to delete to get below the size limit.
+  // Order by time of last use so that recently used files are preserved.
+  std::set<FileInfo> FileInfos;
   uint64_t TotalSize = 0;
 
   // Walk the entire directory cache, looking for unused files.
@@ -224,22 +247,22 @@
 
     // Leave it here for now, but add it to the list of size-based pruning.
     TotalSize += StatusOrErr->getSize();
-    FileSizes.insert({StatusOrErr->getSize(), std::string(File->path())});
+    FileInfos.insert({FileAccessTime, StatusOrErr->getSize(), File->path()});
   }
 
-  auto FileAndSize = FileSizes.rbegin();
-  size_t NumFiles = FileSizes.size();
+  auto FileInfo = FileInfos.begin();
+  size_t NumFiles = FileInfos.size();
 
   auto RemoveCacheFile = [&]() {
     // Remove the file.
-    sys::fs::remove(FileAndSize->second);
+    sys::fs::remove(FileInfo->Path);
     // Update size
-    TotalSize -= FileAndSize->first;
+    TotalSize -= FileInfo->Size;
     NumFiles--;
-    LLVM_DEBUG(dbgs() << " - Remove " << FileAndSize->second << " (size "
-                      << FileAndSize->first << "), new occupancy is "
-                      << TotalSize << "%\n");
-    ++FileAndSize;
+    LLVM_DEBUG(dbgs() << " - Remove " << FileInfo->Path << " (size "
+                      << FileInfo->Size << "), new occupancy is " << TotalSize
+                      << "%\n");
+    ++FileInfo;
   };
 
   // Prune for number of files.
@@ -270,7 +293,7 @@
                       << Policy.MaxSizeBytes << " bytes\n");
 
     // Remove the oldest accessed files first, till we get below the threshold.
-    while (TotalSize > TotalSizeTarget && FileAndSize != FileSizes.rend())
+    while (TotalSize > TotalSizeTarget && FileInfo != FileInfos.end())
       RemoveCacheFile();
   }
   return true;