Index: llvm/lib/Transforms/Utils/SSAUpdater.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SSAUpdater.cpp
+++ llvm/lib/Transforms/Utils/SSAUpdater.cpp
@@ -64,7 +64,13 @@
 }
 
 Value *SSAUpdater::FindValueForBlock(BasicBlock *BB) const {
-  AvailableValsTy::iterator AVI = getAvailableVals(AV).find(BB);
+  auto &AvailableVals = getAvailableVals(AV);
+  // If there is only a single available value, this value dominates all users,
+  // so we can just use it here.
+  if (AvailableVals.size() == 1)
+    return AvailableVals.begin()->second;
+
+  AvailableValsTy::iterator AVI = AvailableVals.find(BB);
   return (AVI != getAvailableVals(AV).end()) ? AVI->second : nullptr;
 }
 
@@ -322,6 +328,12 @@
 /// placement of PHIs and then inserting new PHIs where needed.
 Value *SSAUpdater::GetValueAtEndOfBlockInternal(BasicBlock *BB) {
   AvailableValsTy &AvailableVals = getAvailableVals(AV);
+
+  // If there is only a single available value, this value dominates all users,
+  // so we can just use it here.
+  if (AvailableVals.size() == 1)
+    return AvailableVals.begin()->second;
+
   if (Value *V = AvailableVals[BB])
     return V;