diff --git a/llvm/include/llvm/ADT/IntEqClasses.h b/llvm/include/llvm/ADT/IntEqClasses.h
--- a/llvm/include/llvm/ADT/IntEqClasses.h
+++ b/llvm/include/llvm/ADT/IntEqClasses.h
@@ -31,7 +31,7 @@
   /// itself.
   ///
   /// When compressed, EC[i] is the equivalence class of i.
-  SmallVector<unsigned, 8> EC;
+  mutable SmallVector<unsigned, 8> EC;
 
   /// NumClasses - The number of equivalence classes when compressed, or 0 when
   /// uncompressed.
diff --git a/llvm/lib/Support/IntEqClasses.cpp b/llvm/lib/Support/IntEqClasses.cpp
--- a/llvm/lib/Support/IntEqClasses.cpp
+++ b/llvm/lib/Support/IntEqClasses.cpp
@@ -47,13 +47,19 @@
       eca = EC[a];
     }
 
+  // Make sure that eca is actually the leader of the equivalence class (this
+  // can happen if a and b were already in the same equivalence class).
+  eca = findLeader(eca);
   return eca;
 }
 
 unsigned IntEqClasses::findLeader(unsigned a) const {
   assert(NumClasses == 0 && "findLeader() called after compress().");
-  while (a != EC[a])
-    a = EC[a];
+  while (a != EC[a]) {
+    unsigned eca = EC[a];
+    EC[a] = EC[eca];
+    a = eca;
+  }
   return a;
 }
 
diff --git a/llvm/unittests/ADT/IntEqClassesTest.cpp b/llvm/unittests/ADT/IntEqClassesTest.cpp
--- a/llvm/unittests/ADT/IntEqClassesTest.cpp
+++ b/llvm/unittests/ADT/IntEqClassesTest.cpp
@@ -103,4 +103,46 @@
   EXPECT_EQ(0u, ec.findLeader(9));
 }
 
+TEST(IntEqClasses, JoinReturnsLeader) {
+  IntEqClasses ec(10);
+  EXPECT_EQ(1u, ec.join(1, 2));
+  EXPECT_EQ(1u, ec.join(1, 3));
+  EXPECT_EQ(0u, ec.join(0, 1));
+  EXPECT_EQ(0u, ec.findLeader(1));
+  // At this point, EC[2] = EC[3] = 1, but EC[1] = 0. Be sure that trying to
+  // join EC[2] and EC[3] returns the correct leader, 0, and not their common
+  // node 1.
+  EXPECT_EQ(0u, ec.join(2, 3));
+  EXPECT_EQ(0u, ec.findLeader(2));
+}
+
+TEST(IntEqClasses, FindLeader) {
+  IntEqClasses ec(10);
+
+  // Join all the elements in such a way that most nodes will not point to the
+  // root immediately.
+  ec.join(8, 9);
+  ec.join(7, 8);
+  ec.join(6, 7);
+  ec.join(5, 6);
+  ec.join(4, 5);
+  ec.join(3, 4);
+  ec.join(2, 3);
+  ec.join(1, 2);
+  ec.join(0, 1);
+
+  // Ensure that any path compression that happens doesn't mess up the results
+  // of finding the leader.
+  EXPECT_EQ(0u, ec.findLeader(9));
+  EXPECT_EQ(0u, ec.findLeader(8));
+  EXPECT_EQ(0u, ec.findLeader(7));
+  EXPECT_EQ(0u, ec.findLeader(6));
+  EXPECT_EQ(0u, ec.findLeader(5));
+  EXPECT_EQ(0u, ec.findLeader(4));
+  EXPECT_EQ(0u, ec.findLeader(3));
+  EXPECT_EQ(0u, ec.findLeader(2));
+  EXPECT_EQ(0u, ec.findLeader(1));
+  EXPECT_EQ(0u, ec.findLeader(0));
+}
+
 } // end anonymous namespace