Index: include/llvm/IR/Use.h
===================================================================
--- include/llvm/IR/Use.h
+++ include/llvm/IR/Use.h
@@ -125,6 +125,12 @@
   /// Return the operand # of this use in its User.
   unsigned getOperandNo() const;
 
+  /// Make this Use the first use of its Value.
+  ///
+  /// This could be used to keep frequently looked up users in the beginning (or
+  /// close to it) of the use list, reducing the amortized cost of such lookups.
+  inline void moveToFrontOfUseList();
+
   /// Initializes the waymarking tags on an array of Uses.
   ///
   /// This sets up the array of Uses such that getUser() can find the User from
Index: include/llvm/IR/Value.h
===================================================================
--- include/llvm/IR/Value.h
+++ include/llvm/IR/Value.h
@@ -673,6 +673,14 @@
   if (V) V->addUse(*this);
 }
 
+void Use::moveToFrontOfUseList() {
+  assert(Val && "Not in a Use List");
+  if (&*Val->use_begin() == this)
+    return;
+  removeFromList();
+  Val->addUse(*this);
+}
+
 Value *Use::operator=(Value *RHS) {
   set(RHS);
   return RHS;
Index: unittests/IR/UseTest.cpp
===================================================================
--- unittests/IR/UseTest.cpp
+++ unittests/IR/UseTest.cpp
@@ -8,6 +8,7 @@
 
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/User.h"
@@ -107,4 +108,62 @@
   ASSERT_EQ(8u, I);
 }
 
+TEST(UseTest, moveToFrontOfUseList) {
+  LLVMContext C;
+
+  const char *ModuleString = "define void @f(i32 %x) {\n"
+                             "entry:\n"
+                             "  %v0 = inttoptr i32 %x to i8*\n"
+                             "  ret void\n"
+                             "}\n";
+  SMDiagnostic Err;
+  std::unique_ptr<Module> M = parseAssemblyString(ModuleString, Err, C);
+  Function *F = M->getFunction("f");
+  ASSERT_TRUE(F);
+  ASSERT_TRUE(F->arg_begin() != F->arg_end());
+  Argument &X = *F->arg_begin();
+  ASSERT_EQ("x", X.getName());
+  ASSERT_TRUE(X.hasOneUse());
+  User *V0 = *X.user_begin();
+  ASSERT_TRUE(isa<IntToPtrInst>(V0));
+
+  Instruction *Ret = F->getEntryBlock().getTerminator();
+  constexpr unsigned Size = 20 * 1000;
+  for (unsigned I = 1; I <= Size; ++I) {
+    auto *Const = ConstantInt::get(X.getType(), I);
+    BinaryOperator::Create(Instruction::Add, &X, Const, "v" + Twine(I), Ret);
+  }
+  ASSERT_NE(V0, *X.user_begin());
+  unsigned I = 0;
+  unsigned V0UseIndex = ~0u;
+  for (User *U : X.users()) {
+    if (U == V0) {
+      V0UseIndex = I;
+      break;
+    }
+    ++I;
+  }
+  ASSERT_EQ(Size, V0UseIndex);
+  ASSERT_EQ(Size + 1, X.getNumUses());
+
+  unsigned FoundCounter = 0;
+  unsigned CheckCounter = 0;
+  constexpr unsigned NumRepetitions = 100;
+  for (unsigned J = 0; J < NumRepetitions; ++J)
+    for (Instruction &I : F->getEntryBlock())
+      if (isa<BinaryOperator>(I))
+        for (Use &U : I.getOperand(0)->uses()) {
+          ++CheckCounter;
+          if (isa<IntToPtrInst>(U.getUser())) {
+            ++FoundCounter;
+            U.moveToFrontOfUseList();
+            break;
+          }
+        }
+  ASSERT_EQ(Size * NumRepetitions, FoundCounter);
+  ASSERT_EQ(Size * NumRepetitions + Size, CheckCounter);
+  ASSERT_EQ(Size + 1, X.getNumUses());
+  ASSERT_EQ(V0, *X.user_begin());
+}
+
 } // end anonymous namespace