diff --git a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
--- a/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
+++ b/llvm/lib/Transforms/InstCombine/InstCombineInternal.h
@@ -172,7 +172,7 @@
   Instruction *visitLandingPadInst(LandingPadInst &LI);
   Instruction *visitVAEndInst(VAEndInst &I);
   Value *pushFreezeToPreventPoisonFromPropagating(FreezeInst &FI);
-  bool freezeDominatedUses(FreezeInst &FI);
+  bool freezeOtherUses(FreezeInst &FI);
   Instruction *visitFreeze(FreezeInst &I);
 
   /// Specify what to return for unhandled instructions.
diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
--- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -3807,13 +3807,40 @@
   return OrigOp;
 }
 
-bool InstCombinerImpl::freezeDominatedUses(FreezeInst &FI) {
+bool InstCombinerImpl::freezeOtherUses(FreezeInst &FI) {
   Value *Op = FI.getOperand(0);
 
-  if (isa<Constant>(Op))
+  if (isa<Constant>(Op) || Op->hasOneUse())
     return false;
 
+  // Move the freeze directly after the definition of its operand, so that
+  // it dominates the maximum number of uses. Note that it may not dominate
+  // *all* uses if the operand is an invoke/callbr and the use is in a phi on
+  // the normal/default destination. This is why the domination check in the
+  // replacement below is still necessary.
+  Instruction *MoveBefore = nullptr;
+  if (isa<Argument>(Op)) {
+    MoveBefore = &FI.getFunction()->getEntryBlock().front();
+    while (isa<AllocaInst>(MoveBefore))
+      MoveBefore = MoveBefore->getNextNode();
+  } else if (auto *PN = dyn_cast<PHINode>(Op)) {
+    MoveBefore = PN->getParent()->getFirstNonPHI();
+  } else if (auto *II = dyn_cast<InvokeInst>(Op)) {
+    MoveBefore = II->getNormalDest()->getFirstNonPHI();
+  } else if (auto *CB = dyn_cast<CallBrInst>(Op)) {
+    MoveBefore = CB->getDefaultDest()->getFirstNonPHI();
+  } else {
+    auto *I = cast<Instruction>(Op);
+    assert(!I->isTerminator() && "Cannot be a terminator");
+    MoveBefore = I->getNextNode();
+  }
+
   bool Changed = false;
+  if (&FI != MoveBefore) {
+    FI.moveBefore(MoveBefore);
+    Changed = true;
+  }
+
   Op->replaceUsesWithIf(&FI, [&](Use &U) -> bool {
     bool Dominates = DT.dominates(&FI, U);
     Changed |= Dominates;
@@ -3879,8 +3906,8 @@
     return replaceInstUsesWith(I, Constant::replaceUndefsWith(C, ReplaceC));
   }
 
-  // Replace all dominated uses of Op to freeze(Op).
-  if (freezeDominatedUses(I))
+  // Replace uses of Op with freeze(Op).
+  if (freezeOtherUses(I))
     return &I;
 
   return nullptr;
diff --git a/llvm/test/Transforms/InstCombine/freeze.ll b/llvm/test/Transforms/InstCombine/freeze.ll
--- a/llvm/test/Transforms/InstCombine/freeze.ll
+++ b/llvm/test/Transforms/InstCombine/freeze.ll
@@ -162,17 +162,17 @@
 ; CHECK-LABEL: @freeze_dominated_uses_test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[A:%.*]] = alloca i32, align 4
+; CHECK-NEXT:    [[V_FR:%.*]] = freeze i32 [[V:%.*]]
 ; CHECK-NEXT:    call void @use_p32(i32* nonnull [[A]])
-; CHECK-NEXT:    call void @use_i32(i32 [[V:%.*]])
-; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[V]], 0
+; CHECK-NEXT:    call void @use_i32(i32 [[V_FR]])
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[V_FR]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB0:%.*]], label [[BB1:%.*]]
 ; CHECK:       bb0:
-; CHECK-NEXT:    [[V_FR:%.*]] = freeze i32 [[V]]
 ; CHECK-NEXT:    call void @use_i32(i32 [[V_FR]])
 ; CHECK-NEXT:    call void @use_i32(i32 [[V_FR]])
 ; CHECK-NEXT:    br label [[END:%.*]]
 ; CHECK:       bb1:
-; CHECK-NEXT:    call void @use_i32(i32 [[V]])
+; CHECK-NEXT:    call void @use_i32(i32 [[V_FR]])
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
 ; CHECK-NEXT:    ret void
@@ -239,14 +239,14 @@
 ; CHECK-LABEL: @freeze_use_in_different_branches(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @get_i32()
+; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
 ; CHECK-NEXT:    call void @use_i32(i32 0)
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
-; CHECK-NEXT:    call void @use_i32(i32 [[X]])
+; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       else:
-; CHECK-NEXT:    call void @use_i32(i32 [[X]])
-; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
+; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    ret i32 1
 ;
@@ -270,13 +270,13 @@
 ; CHECK-LABEL: @freeze_phi_use(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @get_i32()
+; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
 ; CHECK-NEXT:    call void @use_i32(i32 0)
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[JOIN:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    br label [[JOIN]]
 ; CHECK:       join:
-; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[X]], [[IF]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[FR]], [[IF]] ], [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    ret i32 [[PHI]]
 ;
@@ -304,9 +304,9 @@
 ; CHECK:       join:
 ; CHECK-NEXT:    [[X:%.*]] = phi i32 [ [[Y:%.*]], [[IF]] ], [ [[Z:%.*]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[Z]], [[IF]] ], [ [[Y]], [[ENTRY]] ]
-; CHECK-NEXT:    call void @use_i32(i32 [[X]])
 ; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
 ; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
+; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    ret i32 [[PHI]]
 ;
 entry:
@@ -363,9 +363,9 @@
 ; CHECK-NEXT:    to label [[INVOKE_CONT:%.*]] unwind label [[INVOKE_UNWIND:%.*]]
 ; CHECK:       invoke.cont:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ 0, [[INVOKE_CONT]] ]
-; CHECK-NEXT:    call void @use_i32(i32 [[X]])
 ; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
 ; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
+; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    call void @use_i32(i32 [[PHI]])
 ; CHECK-NEXT:    br label [[INVOKE_CONT]]
 ; CHECK:       invoke.unwind:
@@ -397,9 +397,9 @@
 ; CHECK-NEXT:    to label [[CALLBR_CONT:%.*]] []
 ; CHECK:       callbr.cont:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[X]], [[ENTRY:%.*]] ], [ 0, [[CALLBR_CONT]] ]
-; CHECK-NEXT:    call void @use_i32(i32 [[X]])
 ; CHECK-NEXT:    [[FR:%.*]] = freeze i32 [[X]]
 ; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
+; CHECK-NEXT:    call void @use_i32(i32 [[FR]])
 ; CHECK-NEXT:    call void @use_i32(i32 [[PHI]])
 ; CHECK-NEXT:    br label [[CALLBR_CONT]]
 ;
@@ -418,13 +418,10 @@
 
 define i1 @combine_and_after_freezing_uses(i32 %x) {
 ; CHECK-LABEL: @combine_and_after_freezing_uses(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[X:%.*]], 4
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp ne i32 [[AND1]], 0
-; CHECK-NEXT:    [[X_FR:%.*]] = freeze i32 [[X]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[X_FR]], 11
-; CHECK-NEXT:    [[CMP2:%.*]] = icmp eq i32 [[AND2]], 11
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[CMP1]], [[CMP2]]
-; CHECK-NEXT:    ret i1 [[AND]]
+; CHECK-NEXT:    [[X_FR:%.*]] = freeze i32 [[X:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X_FR]], 15
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[TMP1]], 15
+; CHECK-NEXT:    ret i1 [[TMP2]]
 ;
   %and1 = and i32 %x, 4
   %cmp1 = icmp ne i32 %and1, 0
@@ -438,12 +435,12 @@
 declare i1 @mock_use(i64, i64)
 define i1 @fully_propagate_freeze(i32 %0, i32 noundef %1) {
 ; CHECK-LABEL: @fully_propagate_freeze(
-; CHECK-NEXT:    [[DR:%.*]] = lshr i32 [[TMP0:%.*]], 2
+; CHECK-NEXT:    [[DOTFR:%.*]] = freeze i32 [[TMP0:%.*]]
+; CHECK-NEXT:    [[DR:%.*]] = lshr i32 [[DOTFR]], 2
 ; CHECK-NEXT:    [[IDX1:%.*]] = zext i32 [[DR]] to i64
-; CHECK-NEXT:    [[DR_FR:%.*]] = freeze i32 [[DR]]
-; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[DR_FR]], 1
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[DR]], 1
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[ADD]], [[TMP1:%.*]]
-; CHECK-NEXT:    [[IDX2:%.*]] = zext i32 [[DR_FR]] to i64
+; CHECK-NEXT:    [[IDX2:%.*]] = zext i32 [[DR]] to i64
 ; CHECK-NEXT:    [[V:%.*]] = call i1 @mock_use(i64 [[IDX1]], i64 [[IDX2]])
 ; CHECK-NEXT:    [[RET:%.*]] = and i1 [[V]], [[CMP]]
 ; CHECK-NEXT:    ret i1 [[RET]]
diff --git a/llvm/test/Transforms/InstCombine/onehot_merge.ll b/llvm/test/Transforms/InstCombine/onehot_merge.ll
--- a/llvm/test/Transforms/InstCombine/onehot_merge.ll
+++ b/llvm/test/Transforms/InstCombine/onehot_merge.ll
@@ -775,8 +775,8 @@
 ; CHECK-LABEL: @foo1_and_extra_use_shl2_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 1, [[C2:%.*]]
-; CHECK-NEXT:    store i32 [[T1]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[T1]]
+; CHECK-NEXT:    store i32 [[TMP1]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[T0]], [[TMP1]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], [[K:%.*]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[TMP3]], [[TMP2]]
@@ -820,9 +820,9 @@
 ; CHECK-LABEL: @foo1_and_extra_use_and2_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 1, [[C2:%.*]]
-; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T1]], [[K:%.*]]
-; CHECK-NEXT:    store i32 [[T4]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[T1]]
+; CHECK-NEXT:    [[T4:%.*]] = and i32 [[TMP1]], [[K:%.*]]
+; CHECK-NEXT:    store i32 [[T4]], i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[T0]], [[TMP1]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], [[K]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[TMP3]], [[TMP2]]
@@ -867,10 +867,10 @@
 ; CHECK-LABEL: @foo1_and_extra_use_cmp2_logical(
 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 1, [[C1:%.*]]
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 1, [[C2:%.*]]
-; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T1]], [[K:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[T1]]
+; CHECK-NEXT:    [[T4:%.*]] = and i32 [[TMP1]], [[K:%.*]]
 ; CHECK-NEXT:    [[T5:%.*]] = icmp eq i32 [[T4]], 0
 ; CHECK-NEXT:    store i1 [[T5]], i1* [[P:%.*]], align 1
-; CHECK-NEXT:    [[TMP1:%.*]] = freeze i32 [[T1]]
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[T0]], [[TMP1]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], [[K]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i32 [[TMP3]], [[TMP2]]