Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2104,10 +2104,11 @@
         !(HoistCondStores && (SpeculatedStoreValue = isSafeToSpeculateStore(
                                   I, BB, ThenBB, EndBB))))
       return false;
-    if (!SpeculatedStoreValue &&
-        ComputeSpeculationCost(I, TTI) >
-            PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic)
-      return false;
+    if (!SpeculatedStoreValue) {
+      BudgetRemaining -= ComputeSpeculationCost(I, TTI);
+      if (BudgetRemaining < 0)
+        return false;
+    }
 
     // Store the store speculation candidate.
     if (SpeculatedStoreValue)
@@ -2165,9 +2166,9 @@
       return false;
     unsigned OrigCost = OrigCE ? ComputeSpeculationCost(OrigCE, TTI) : 0;
     unsigned ThenCost = ThenCE ? ComputeSpeculationCost(ThenCE, TTI) : 0;
-    unsigned MaxCost =
-        2 * PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic;
-    if (OrigCost + ThenCost > MaxCost)
+
+    BudgetRemaining -= OrigCost - ThenCost;
+    if (BudgetRemaining < 0)
       return false;
 
     // Account for the cost of an unfolded ConstantExpr which could end up
Index: llvm/test/Transforms/SimplifyCFG/merge-cond-stores-2.ll
===================================================================
--- llvm/test/Transforms/SimplifyCFG/merge-cond-stores-2.ll
+++ llvm/test/Transforms/SimplifyCFG/merge-cond-stores-2.ll
@@ -19,127 +19,127 @@
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i32 [[AND1]], 0
 ; CHECK-NEXT:    [[OR4:%.*]] = or i32 [[TMP1]], 1073741824
-; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[TOBOOL2]], i32 [[TMP1]], i32 [[OR4]]
-; CHECK-NEXT:    [[TMP2:%.*]] = xor i1 [[TOBOOL]], true
-; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TOBOOL2]], true
-; CHECK-NEXT:    [[TMP4:%.*]] = or i1 [[TMP2]], [[TMP3]]
-; CHECK-NEXT:    [[AND6:%.*]] = and i32 [[SPEC_SELECT]], 4
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TOBOOL2]], i32 [[TMP1]], i32 [[OR4]]
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[TOBOOL]], true
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i1 [[TOBOOL2]], true
+; CHECK-NEXT:    [[TMP5:%.*]] = or i1 [[TMP3]], [[TMP4]]
+; CHECK-NEXT:    [[AND6:%.*]] = and i32 [[TMP2]], 4
 ; CHECK-NEXT:    [[TOBOOL7:%.*]] = icmp eq i32 [[AND6]], 0
-; CHECK-NEXT:    [[OR9:%.*]] = or i32 [[SPEC_SELECT]], 536870912
-; CHECK-NEXT:    [[SPEC_SELECT1:%.*]] = select i1 [[TOBOOL7]], i32 [[SPEC_SELECT]], i32 [[OR9]]
-; CHECK-NEXT:    [[TMP5:%.*]] = xor i1 [[TMP4]], true
-; CHECK-NEXT:    [[TMP6:%.*]] = xor i1 [[TOBOOL7]], true
+; CHECK-NEXT:    [[OR9:%.*]] = or i32 [[TMP2]], 536870912
+; CHECK-NEXT:    [[TMP6:%.*]] = select i1 [[TOBOOL7]], i32 [[TMP2]], i32 [[OR9]]
 ; CHECK-NEXT:    [[TMP7:%.*]] = xor i1 [[TMP5]], true
-; CHECK-NEXT:    [[TMP8:%.*]] = or i1 [[TMP7]], [[TMP6]]
-; CHECK-NEXT:    [[AND11:%.*]] = and i32 [[SPEC_SELECT1]], 8
+; CHECK-NEXT:    [[TMP8:%.*]] = xor i1 [[TOBOOL7]], true
+; CHECK-NEXT:    [[TMP9:%.*]] = xor i1 [[TMP7]], true
+; CHECK-NEXT:    [[TMP10:%.*]] = or i1 [[TMP9]], [[TMP8]]
+; CHECK-NEXT:    [[AND11:%.*]] = and i32 [[TMP6]], 8
 ; CHECK-NEXT:    [[TOBOOL12:%.*]] = icmp eq i32 [[AND11]], 0
-; CHECK-NEXT:    [[OR14:%.*]] = or i32 [[SPEC_SELECT1]], 268435456
-; CHECK-NEXT:    [[SPEC_SELECT2:%.*]] = select i1 [[TOBOOL12]], i32 [[SPEC_SELECT1]], i32 [[OR14]]
-; CHECK-NEXT:    [[TMP9:%.*]] = xor i1 [[TMP8]], true
-; CHECK-NEXT:    [[TMP10:%.*]] = xor i1 [[TOBOOL12]], true
-; CHECK-NEXT:    [[TMP11:%.*]] = xor i1 [[TMP9]], true
-; CHECK-NEXT:    [[TMP12:%.*]] = or i1 [[TMP11]], [[TMP10]]
-; CHECK-NEXT:    [[AND16:%.*]] = and i32 [[SPEC_SELECT2]], 16
+; CHECK-NEXT:    [[OR14:%.*]] = or i32 [[TMP6]], 268435456
+; CHECK-NEXT:    [[TMP11:%.*]] = select i1 [[TOBOOL12]], i32 [[TMP6]], i32 [[OR14]]
+; CHECK-NEXT:    [[TMP12:%.*]] = xor i1 [[TMP10]], true
+; CHECK-NEXT:    [[TMP13:%.*]] = xor i1 [[TOBOOL12]], true
+; CHECK-NEXT:    [[TMP14:%.*]] = xor i1 [[TMP12]], true
+; CHECK-NEXT:    [[TMP15:%.*]] = or i1 [[TMP14]], [[TMP13]]
+; CHECK-NEXT:    [[AND16:%.*]] = and i32 [[TMP11]], 16
 ; CHECK-NEXT:    [[TOBOOL17:%.*]] = icmp eq i32 [[AND16]], 0
-; CHECK-NEXT:    [[OR19:%.*]] = or i32 [[SPEC_SELECT2]], 134217728
-; CHECK-NEXT:    [[SPEC_SELECT3:%.*]] = select i1 [[TOBOOL17]], i32 [[SPEC_SELECT2]], i32 [[OR19]]
-; CHECK-NEXT:    [[TMP13:%.*]] = xor i1 [[TMP12]], true
-; CHECK-NEXT:    [[TMP14:%.*]] = xor i1 [[TOBOOL17]], true
-; CHECK-NEXT:    [[TMP15:%.*]] = xor i1 [[TMP13]], true
-; CHECK-NEXT:    [[TMP16:%.*]] = or i1 [[TMP15]], [[TMP14]]
-; CHECK-NEXT:    [[AND21:%.*]] = and i32 [[SPEC_SELECT3]], 32
-; CHECK-NEXT:    [[TOBOOL22:%.*]] = icmp eq i32 [[AND21]], 0
-; CHECK-NEXT:    [[OR24:%.*]] = or i32 [[SPEC_SELECT3]], 67108864
-; CHECK-NEXT:    [[SPEC_SELECT4:%.*]] = select i1 [[TOBOOL22]], i32 [[SPEC_SELECT3]], i32 [[OR24]]
-; CHECK-NEXT:    [[TMP17:%.*]] = xor i1 [[TMP16]], true
-; CHECK-NEXT:    [[TMP18:%.*]] = xor i1 [[TOBOOL22]], true
+; CHECK-NEXT:    [[OR19:%.*]] = or i32 [[TMP11]], 134217728
+; CHECK-NEXT:    [[TMP16:%.*]] = select i1 [[TOBOOL17]], i32 [[TMP11]], i32 [[OR19]]
+; CHECK-NEXT:    [[TMP17:%.*]] = xor i1 [[TMP15]], true
+; CHECK-NEXT:    [[TMP18:%.*]] = xor i1 [[TOBOOL17]], true
 ; CHECK-NEXT:    [[TMP19:%.*]] = xor i1 [[TMP17]], true
 ; CHECK-NEXT:    [[TMP20:%.*]] = or i1 [[TMP19]], [[TMP18]]
-; CHECK-NEXT:    [[AND26:%.*]] = and i32 [[SPEC_SELECT4]], 64
+; CHECK-NEXT:    [[AND21:%.*]] = and i32 [[TMP16]], 32
+; CHECK-NEXT:    [[TOBOOL22:%.*]] = icmp eq i32 [[AND21]], 0
+; CHECK-NEXT:    [[OR24:%.*]] = or i32 [[TMP16]], 67108864
+; CHECK-NEXT:    [[TMP21:%.*]] = select i1 [[TOBOOL22]], i32 [[TMP16]], i32 [[OR24]]
+; CHECK-NEXT:    [[TMP22:%.*]] = xor i1 [[TMP20]], true
+; CHECK-NEXT:    [[TMP23:%.*]] = xor i1 [[TOBOOL22]], true
+; CHECK-NEXT:    [[TMP24:%.*]] = xor i1 [[TMP22]], true
+; CHECK-NEXT:    [[TMP25:%.*]] = or i1 [[TMP24]], [[TMP23]]
+; CHECK-NEXT:    [[AND26:%.*]] = and i32 [[TMP21]], 64
 ; CHECK-NEXT:    [[TOBOOL27:%.*]] = icmp eq i32 [[AND26]], 0
-; CHECK-NEXT:    [[OR29:%.*]] = or i32 [[SPEC_SELECT4]], 33554432
-; CHECK-NEXT:    [[SPEC_SELECT5:%.*]] = select i1 [[TOBOOL27]], i32 [[SPEC_SELECT4]], i32 [[OR29]]
-; CHECK-NEXT:    [[TMP21:%.*]] = xor i1 [[TMP20]], true
-; CHECK-NEXT:    [[TMP22:%.*]] = xor i1 [[TOBOOL27]], true
-; CHECK-NEXT:    [[TMP23:%.*]] = xor i1 [[TMP21]], true
-; CHECK-NEXT:    [[TMP24:%.*]] = or i1 [[TMP23]], [[TMP22]]
-; CHECK-NEXT:    [[AND31:%.*]] = and i32 [[SPEC_SELECT5]], 256
-; CHECK-NEXT:    [[TOBOOL32:%.*]] = icmp eq i32 [[AND31]], 0
-; CHECK-NEXT:    [[OR34:%.*]] = or i32 [[SPEC_SELECT5]], 8388608
-; CHECK-NEXT:    [[SPEC_SELECT6:%.*]] = select i1 [[TOBOOL32]], i32 [[SPEC_SELECT5]], i32 [[OR34]]
-; CHECK-NEXT:    [[TMP25:%.*]] = xor i1 [[TMP24]], true
-; CHECK-NEXT:    [[TMP26:%.*]] = xor i1 [[TOBOOL32]], true
+; CHECK-NEXT:    [[OR29:%.*]] = or i32 [[TMP21]], 33554432
+; CHECK-NEXT:    [[TMP26:%.*]] = select i1 [[TOBOOL27]], i32 [[TMP21]], i32 [[OR29]]
 ; CHECK-NEXT:    [[TMP27:%.*]] = xor i1 [[TMP25]], true
-; CHECK-NEXT:    [[TMP28:%.*]] = or i1 [[TMP27]], [[TMP26]]
-; CHECK-NEXT:    [[AND36:%.*]] = and i32 [[SPEC_SELECT6]], 512
+; CHECK-NEXT:    [[TMP28:%.*]] = xor i1 [[TOBOOL27]], true
+; CHECK-NEXT:    [[TMP29:%.*]] = xor i1 [[TMP27]], true
+; CHECK-NEXT:    [[TMP30:%.*]] = or i1 [[TMP29]], [[TMP28]]
+; CHECK-NEXT:    [[AND31:%.*]] = and i32 [[TMP26]], 256
+; CHECK-NEXT:    [[TOBOOL32:%.*]] = icmp eq i32 [[AND31]], 0
+; CHECK-NEXT:    [[OR34:%.*]] = or i32 [[TMP26]], 8388608
+; CHECK-NEXT:    [[TMP31:%.*]] = select i1 [[TOBOOL32]], i32 [[TMP26]], i32 [[OR34]]
+; CHECK-NEXT:    [[TMP32:%.*]] = xor i1 [[TMP30]], true
+; CHECK-NEXT:    [[TMP33:%.*]] = xor i1 [[TOBOOL32]], true
+; CHECK-NEXT:    [[TMP34:%.*]] = xor i1 [[TMP32]], true
+; CHECK-NEXT:    [[TMP35:%.*]] = or i1 [[TMP34]], [[TMP33]]
+; CHECK-NEXT:    [[AND36:%.*]] = and i32 [[TMP31]], 512
 ; CHECK-NEXT:    [[TOBOOL37:%.*]] = icmp eq i32 [[AND36]], 0
-; CHECK-NEXT:    [[OR39:%.*]] = or i32 [[SPEC_SELECT6]], 4194304
-; CHECK-NEXT:    [[SPEC_SELECT7:%.*]] = select i1 [[TOBOOL37]], i32 [[SPEC_SELECT6]], i32 [[OR39]]
-; CHECK-NEXT:    [[TMP29:%.*]] = xor i1 [[TMP28]], true
-; CHECK-NEXT:    [[TMP30:%.*]] = xor i1 [[TOBOOL37]], true
-; CHECK-NEXT:    [[TMP31:%.*]] = xor i1 [[TMP29]], true
-; CHECK-NEXT:    [[TMP32:%.*]] = or i1 [[TMP31]], [[TMP30]]
-; CHECK-NEXT:    [[AND41:%.*]] = and i32 [[SPEC_SELECT7]], 1024
-; CHECK-NEXT:    [[TOBOOL42:%.*]] = icmp eq i32 [[AND41]], 0
-; CHECK-NEXT:    [[OR44:%.*]] = or i32 [[SPEC_SELECT7]], 2097152
-; CHECK-NEXT:    [[SPEC_SELECT8:%.*]] = select i1 [[TOBOOL42]], i32 [[SPEC_SELECT7]], i32 [[OR44]]
-; CHECK-NEXT:    [[TMP33:%.*]] = xor i1 [[TMP32]], true
-; CHECK-NEXT:    [[TMP34:%.*]] = xor i1 [[TOBOOL42]], true
-; CHECK-NEXT:    [[TMP35:%.*]] = xor i1 [[TMP33]], true
-; CHECK-NEXT:    [[TMP36:%.*]] = or i1 [[TMP35]], [[TMP34]]
-; CHECK-NEXT:    [[AND46:%.*]] = and i32 [[SPEC_SELECT8]], 2048
-; CHECK-NEXT:    [[TOBOOL47:%.*]] = icmp eq i32 [[AND46]], 0
-; CHECK-NEXT:    [[OR49:%.*]] = or i32 [[SPEC_SELECT8]], 1048576
-; CHECK-NEXT:    [[SPEC_SELECT9:%.*]] = select i1 [[TOBOOL47]], i32 [[SPEC_SELECT8]], i32 [[OR49]]
-; CHECK-NEXT:    [[TMP37:%.*]] = xor i1 [[TMP36]], true
-; CHECK-NEXT:    [[TMP38:%.*]] = xor i1 [[TOBOOL47]], true
+; CHECK-NEXT:    [[OR39:%.*]] = or i32 [[TMP31]], 4194304
+; CHECK-NEXT:    [[TMP36:%.*]] = select i1 [[TOBOOL37]], i32 [[TMP31]], i32 [[OR39]]
+; CHECK-NEXT:    [[TMP37:%.*]] = xor i1 [[TMP35]], true
+; CHECK-NEXT:    [[TMP38:%.*]] = xor i1 [[TOBOOL37]], true
 ; CHECK-NEXT:    [[TMP39:%.*]] = xor i1 [[TMP37]], true
 ; CHECK-NEXT:    [[TMP40:%.*]] = or i1 [[TMP39]], [[TMP38]]
-; CHECK-NEXT:    [[AND51:%.*]] = and i32 [[SPEC_SELECT9]], 4096
+; CHECK-NEXT:    [[AND41:%.*]] = and i32 [[TMP36]], 1024
+; CHECK-NEXT:    [[TOBOOL42:%.*]] = icmp eq i32 [[AND41]], 0
+; CHECK-NEXT:    [[OR44:%.*]] = or i32 [[TMP36]], 2097152
+; CHECK-NEXT:    [[TMP41:%.*]] = select i1 [[TOBOOL42]], i32 [[TMP36]], i32 [[OR44]]
+; CHECK-NEXT:    [[TMP42:%.*]] = xor i1 [[TMP40]], true
+; CHECK-NEXT:    [[TMP43:%.*]] = xor i1 [[TOBOOL42]], true
+; CHECK-NEXT:    [[TMP44:%.*]] = xor i1 [[TMP42]], true
+; CHECK-NEXT:    [[TMP45:%.*]] = or i1 [[TMP44]], [[TMP43]]
+; CHECK-NEXT:    [[AND46:%.*]] = and i32 [[TMP41]], 2048
+; CHECK-NEXT:    [[TOBOOL47:%.*]] = icmp eq i32 [[AND46]], 0
+; CHECK-NEXT:    [[OR49:%.*]] = or i32 [[TMP41]], 1048576
+; CHECK-NEXT:    [[TMP46:%.*]] = select i1 [[TOBOOL47]], i32 [[TMP41]], i32 [[OR49]]
+; CHECK-NEXT:    [[TMP47:%.*]] = xor i1 [[TMP45]], true
+; CHECK-NEXT:    [[TMP48:%.*]] = xor i1 [[TOBOOL47]], true
+; CHECK-NEXT:    [[TMP49:%.*]] = xor i1 [[TMP47]], true
+; CHECK-NEXT:    [[TMP50:%.*]] = or i1 [[TMP49]], [[TMP48]]
+; CHECK-NEXT:    [[AND51:%.*]] = and i32 [[TMP46]], 4096
 ; CHECK-NEXT:    [[TOBOOL52:%.*]] = icmp eq i32 [[AND51]], 0
-; CHECK-NEXT:    [[OR54:%.*]] = or i32 [[SPEC_SELECT9]], 524288
-; CHECK-NEXT:    [[SPEC_SELECT10:%.*]] = select i1 [[TOBOOL52]], i32 [[SPEC_SELECT9]], i32 [[OR54]]
-; CHECK-NEXT:    [[TMP41:%.*]] = xor i1 [[TMP40]], true
-; CHECK-NEXT:    [[TMP42:%.*]] = xor i1 [[TOBOOL52]], true
-; CHECK-NEXT:    [[TMP43:%.*]] = xor i1 [[TMP41]], true
-; CHECK-NEXT:    [[TMP44:%.*]] = or i1 [[TMP43]], [[TMP42]]
-; CHECK-NEXT:    [[AND56:%.*]] = and i32 [[SPEC_SELECT10]], 8192
+; CHECK-NEXT:    [[OR54:%.*]] = or i32 [[TMP46]], 524288
+; CHECK-NEXT:    [[TMP51:%.*]] = select i1 [[TOBOOL52]], i32 [[TMP46]], i32 [[OR54]]
+; CHECK-NEXT:    [[TMP52:%.*]] = xor i1 [[TMP50]], true
+; CHECK-NEXT:    [[TMP53:%.*]] = xor i1 [[TOBOOL52]], true
+; CHECK-NEXT:    [[TMP54:%.*]] = xor i1 [[TMP52]], true
+; CHECK-NEXT:    [[TMP55:%.*]] = or i1 [[TMP54]], [[TMP53]]
+; CHECK-NEXT:    [[AND56:%.*]] = and i32 [[TMP51]], 8192
 ; CHECK-NEXT:    [[TOBOOL57:%.*]] = icmp eq i32 [[AND56]], 0
-; CHECK-NEXT:    [[OR59:%.*]] = or i32 [[SPEC_SELECT10]], 262144
-; CHECK-NEXT:    [[SPEC_SELECT11:%.*]] = select i1 [[TOBOOL57]], i32 [[SPEC_SELECT10]], i32 [[OR59]]
-; CHECK-NEXT:    [[TMP45:%.*]] = xor i1 [[TMP44]], true
-; CHECK-NEXT:    [[TMP46:%.*]] = xor i1 [[TOBOOL57]], true
-; CHECK-NEXT:    [[TMP47:%.*]] = xor i1 [[TMP45]], true
-; CHECK-NEXT:    [[TMP48:%.*]] = or i1 [[TMP47]], [[TMP46]]
-; CHECK-NEXT:    [[AND61:%.*]] = and i32 [[SPEC_SELECT11]], 16384
+; CHECK-NEXT:    [[OR59:%.*]] = or i32 [[TMP51]], 262144
+; CHECK-NEXT:    [[TMP56:%.*]] = select i1 [[TOBOOL57]], i32 [[TMP51]], i32 [[OR59]]
+; CHECK-NEXT:    [[TMP57:%.*]] = xor i1 [[TMP55]], true
+; CHECK-NEXT:    [[TMP58:%.*]] = xor i1 [[TOBOOL57]], true
+; CHECK-NEXT:    [[TMP59:%.*]] = xor i1 [[TMP57]], true
+; CHECK-NEXT:    [[TMP60:%.*]] = or i1 [[TMP59]], [[TMP58]]
+; CHECK-NEXT:    [[AND61:%.*]] = and i32 [[TMP56]], 16384
 ; CHECK-NEXT:    [[TOBOOL62:%.*]] = icmp eq i32 [[AND61]], 0
-; CHECK-NEXT:    [[OR64:%.*]] = or i32 [[SPEC_SELECT11]], 131072
-; CHECK-NEXT:    [[SPEC_SELECT12:%.*]] = select i1 [[TOBOOL62]], i32 [[SPEC_SELECT11]], i32 [[OR64]]
-; CHECK-NEXT:    [[TMP49:%.*]] = xor i1 [[TMP48]], true
-; CHECK-NEXT:    [[TMP50:%.*]] = xor i1 [[TOBOOL62]], true
-; CHECK-NEXT:    [[TMP51:%.*]] = xor i1 [[TMP49]], true
-; CHECK-NEXT:    [[TMP52:%.*]] = or i1 [[TMP51]], [[TMP50]]
-; CHECK-NEXT:    [[AND66:%.*]] = and i32 [[SPEC_SELECT12]], 32768
+; CHECK-NEXT:    [[OR64:%.*]] = or i32 [[TMP56]], 131072
+; CHECK-NEXT:    [[TMP61:%.*]] = select i1 [[TOBOOL62]], i32 [[TMP56]], i32 [[OR64]]
+; CHECK-NEXT:    [[TMP62:%.*]] = xor i1 [[TMP60]], true
+; CHECK-NEXT:    [[TMP63:%.*]] = xor i1 [[TOBOOL62]], true
+; CHECK-NEXT:    [[TMP64:%.*]] = xor i1 [[TMP62]], true
+; CHECK-NEXT:    [[TMP65:%.*]] = or i1 [[TMP64]], [[TMP63]]
+; CHECK-NEXT:    [[AND66:%.*]] = and i32 [[TMP61]], 32768
 ; CHECK-NEXT:    [[TOBOOL67:%.*]] = icmp eq i32 [[AND66]], 0
-; CHECK-NEXT:    [[OR69:%.*]] = or i32 [[SPEC_SELECT12]], 65536
-; CHECK-NEXT:    [[SPEC_SELECT13:%.*]] = select i1 [[TOBOOL67]], i32 [[SPEC_SELECT12]], i32 [[OR69]]
-; CHECK-NEXT:    [[TMP53:%.*]] = xor i1 [[TMP52]], true
-; CHECK-NEXT:    [[TMP54:%.*]] = xor i1 [[TOBOOL67]], true
-; CHECK-NEXT:    [[TMP55:%.*]] = xor i1 [[TMP53]], true
-; CHECK-NEXT:    [[TMP56:%.*]] = or i1 [[TMP55]], [[TMP54]]
-; CHECK-NEXT:    [[AND71:%.*]] = and i32 [[SPEC_SELECT13]], 128
+; CHECK-NEXT:    [[OR69:%.*]] = or i32 [[TMP61]], 65536
+; CHECK-NEXT:    [[TMP66:%.*]] = select i1 [[TOBOOL67]], i32 [[TMP61]], i32 [[OR69]]
+; CHECK-NEXT:    [[TMP67:%.*]] = xor i1 [[TMP65]], true
+; CHECK-NEXT:    [[TMP68:%.*]] = xor i1 [[TOBOOL67]], true
+; CHECK-NEXT:    [[TMP69:%.*]] = xor i1 [[TMP67]], true
+; CHECK-NEXT:    [[TMP70:%.*]] = or i1 [[TMP69]], [[TMP68]]
+; CHECK-NEXT:    [[AND71:%.*]] = and i32 [[TMP66]], 128
 ; CHECK-NEXT:    [[TOBOOL72:%.*]] = icmp eq i32 [[AND71]], 0
-; CHECK-NEXT:    [[OR74:%.*]] = or i32 [[SPEC_SELECT13]], 16777216
-; CHECK-NEXT:    [[SPEC_SELECT14:%.*]] = select i1 [[TOBOOL72]], i32 [[SPEC_SELECT13]], i32 [[OR74]]
-; CHECK-NEXT:    [[TMP57:%.*]] = xor i1 [[TMP56]], true
-; CHECK-NEXT:    [[TMP58:%.*]] = xor i1 [[TOBOOL72]], true
-; CHECK-NEXT:    [[TMP59:%.*]] = xor i1 [[TMP57]], true
-; CHECK-NEXT:    [[TMP60:%.*]] = or i1 [[TMP59]], [[TMP58]]
-; CHECK-NEXT:    br i1 [[TMP60]], label [[TMP61:%.*]], label [[TMP62:%.*]]
-; CHECK:       61:
-; CHECK-NEXT:    store i32 [[SPEC_SELECT14]], i32* [[B]], align 4
-; CHECK-NEXT:    br label [[TMP62]]
-; CHECK:       62:
+; CHECK-NEXT:    [[OR74:%.*]] = or i32 [[TMP66]], 16777216
+; CHECK-NEXT:    [[SIMPLIFYCFG_MERGE:%.*]] = select i1 [[TOBOOL72]], i32 [[TMP66]], i32 [[OR74]]
+; CHECK-NEXT:    [[TMP71:%.*]] = xor i1 [[TMP70]], true
+; CHECK-NEXT:    [[TMP72:%.*]] = xor i1 [[TOBOOL72]], true
+; CHECK-NEXT:    [[TMP73:%.*]] = xor i1 [[TMP71]], true
+; CHECK-NEXT:    [[TMP74:%.*]] = or i1 [[TMP73]], [[TMP72]]
+; CHECK-NEXT:    br i1 [[TMP74]], label [[TMP75:%.*]], label [[TMP76:%.*]]
+; CHECK:       75:
+; CHECK-NEXT:    store i32 [[SIMPLIFYCFG_MERGE]], i32* [[B]], align 4
+; CHECK-NEXT:    br label [[TMP76]]
+; CHECK:       76:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
Index: llvm/test/Transforms/SimplifyCFG/multiple-phis.ll
===================================================================
--- llvm/test/Transforms/SimplifyCFG/multiple-phis.ll
+++ llvm/test/Transforms/SimplifyCFG/multiple-phis.ll
@@ -1,6 +1,7 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -simplifycfg -keep-loops=false -S < %s | FileCheck %s
 ; RUN: opt -passes='simplify-cfg<no-keep-loops>' -S < %s | FileCheck %s
+; RUN: opt -simplifycfg -keep-loops=false -S -phi-node-folding-threshold=3 < %s | FileCheck --check-prefix=FOLD-3 %s
 
 ; It's not worthwhile to if-convert one of the phi nodes and leave
 ; the other behind, because that still requires a branch. If
@@ -11,24 +12,46 @@
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
-; CHECK-NEXT:    [[HIGH_ADDR_0:%.*]] = phi i32 [ [[HIGH:%.*]], [[ENTRY:%.*]] ], [ [[DIV_HIGH_ADDR_0:%.*]], [[WHILE_BODY:%.*]] ]
-; CHECK-NEXT:    [[LOW_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[LOW_0_ADD2:%.*]], [[WHILE_BODY]] ]
+; CHECK-NEXT:    [[HIGH_ADDR_0:%.*]] = phi i32 [ [[HIGH:%.*]], [[ENTRY:%.*]] ], [ [[HIGH_ADDR_0]], [[IF_ELSE:%.*]] ], [ [[DIV:%.*]], [[WHILE_BODY:%.*]] ]
+; CHECK-NEXT:    [[LOW_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[ADD2:%.*]], [[IF_ELSE]] ], [ [[LOW_0]], [[WHILE_BODY]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[LOW_0]], [[HIGH_ADDR_0]]
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_BODY]], label [[WHILE_END:%.*]]
 ; CHECK:       while.body:
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[LOW_0]], [[HIGH_ADDR_0]]
-; CHECK-NEXT:    [[DIV:%.*]] = udiv i32 [[ADD]], 2
+; CHECK-NEXT:    [[DIV]] = udiv i32 [[ADD]], 2
 ; CHECK-NEXT:    [[IDXPROM:%.*]] = zext i32 [[DIV]] to i64
 ; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[R:%.*]], i64 [[IDXPROM]]
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]]
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
 ; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[K:%.*]], [[TMP0]]
-; CHECK-NEXT:    [[ADD2:%.*]] = add i32 [[DIV]], 1
-; CHECK-NEXT:    [[DIV_HIGH_ADDR_0]] = select i1 [[CMP1]], i32 [[DIV]], i32 [[HIGH_ADDR_0]]
-; CHECK-NEXT:    [[LOW_0_ADD2]] = select i1 [[CMP1]], i32 [[LOW_0]], i32 [[ADD2]]
+; CHECK-NEXT:    br i1 [[CMP1]], label [[WHILE_COND]], label [[IF_ELSE]]
+; CHECK:       if.else:
+; CHECK-NEXT:    [[ADD2]] = add i32 [[DIV]], 1
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
 ; CHECK-NEXT:    ret i32 [[LOW_0]]
 ;
+; FOLD-3-LABEL: @upper_bound(
+; FOLD-3-NEXT:  entry:
+; FOLD-3-NEXT:    br label [[WHILE_COND:%.*]]
+; FOLD-3:       while.cond:
+; FOLD-3-NEXT:    [[HIGH_ADDR_0:%.*]] = phi i32 [ [[HIGH:%.*]], [[ENTRY:%.*]] ], [ [[SPEC_SELECT:%.*]], [[WHILE_BODY:%.*]] ]
+; FOLD-3-NEXT:    [[LOW_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[SPEC_SELECT1:%.*]], [[WHILE_BODY]] ]
+; FOLD-3-NEXT:    [[CMP:%.*]] = icmp ult i32 [[LOW_0]], [[HIGH_ADDR_0]]
+; FOLD-3-NEXT:    br i1 [[CMP]], label [[WHILE_BODY]], label [[WHILE_END:%.*]]
+; FOLD-3:       while.body:
+; FOLD-3-NEXT:    [[ADD:%.*]] = add i32 [[LOW_0]], [[HIGH_ADDR_0]]
+; FOLD-3-NEXT:    [[DIV:%.*]] = udiv i32 [[ADD]], 2
+; FOLD-3-NEXT:    [[IDXPROM:%.*]] = zext i32 [[DIV]] to i64
+; FOLD-3-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i32, i32* [[R:%.*]], i64 [[IDXPROM]]
+; FOLD-3-NEXT:    [[TMP0:%.*]] = load i32, i32* [[ARRAYIDX]], align 4
+; FOLD-3-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[K:%.*]], [[TMP0]]
+; FOLD-3-NEXT:    [[ADD2:%.*]] = add i32 [[DIV]], 1
+; FOLD-3-NEXT:    [[SPEC_SELECT]] = select i1 [[CMP1]], i32 [[DIV]], i32 [[HIGH_ADDR_0]]
+; FOLD-3-NEXT:    [[SPEC_SELECT1]] = select i1 [[CMP1]], i32 [[LOW_0]], i32 [[ADD2]]
+; FOLD-3-NEXT:    br label [[WHILE_COND]]
+; FOLD-3:       while.end:
+; FOLD-3-NEXT:    ret i32 [[LOW_0]]
+;
 entry:
   br label %while.cond