BasicBlockUtils: Add a new way for CreateControlFlowHub()

[bcahoon]

Summary

The existing way of creating the predicate in the guard blocks is using
a boolean value per outgoing block. This would be increase the number of
live booleans as we are having more outgoing blocks. The new way added in
this change is to store one integer to represent the outgoing block we
want to branch to, then at each guard block, an integer equality check
will be performed to decide which a specific outgoing block will be
taken.

[bcahoon]

I'd like to try to move this patch by Ruiling forward. Using integer values instead of
boolean values for regions with many outgoing blocks is beneficial by reducing
register pressure. Using boolean vlaues requires a live value for each outgoing block,
but using an integer requires one only. In loops with lot of outgoing blocks, we see
a significant reduction in register pressure and faster compile-time.

Added a test case when using integers. Existing test changes are needed because
Phis are added in a different order now. Another change is that a comand-line
option may be used to specify when to use boolean or integer values.

[sameerds]

LGTM, with a minor issue in the option name and description.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

60–64

The option name and its description does not really say which utility it's meant for in this file. I would suggest a name such as "MaxBooleansInControlFlowHub" along with a mention of the control flow hub in the description.

[foad]

Why do we still need the "old way"? Does the "new way" generate worse code in some cases?

[bcahoon]

In D127831#3887582, @foad wrote:

Why do we still need the "old way"? Does the "new way" generate worse code in some cases?

Good question. The new way does require an additional compare instruction to test where control continues after the loop. One for each output edge. But, yes, there is a tradeoff here. I think it's worth assessing if the "new way" can replace the "old way" at some point. My thinking here is to be conservative and keep the "old way" for now as I'm a little hesitant to replace it without more performance data.

[ruiling]

In D127831#3887582, @foad wrote:

Why do we still need the "old way"? Does the "new way" generate worse code in some cases?

The "old way" uses one boolean value to record whether an outgoing block would be taken, we need N boolean values when we have N outgoing blocks. But the "new way" just needs one 32bits variable to record the outgoing target, meanwhile it needs some additional compare instructions to generate the block prediction. So, this is a tradeoff between the register usage and number of instructions.

[arsenm]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

60–64

Given this is a utility function I would expect this to be a parameter instead

[foad]

In D127831#3890092, @bcahoon wrote:

In D127831#3887582, @foad wrote:

Why do we still need the "old way"? Does the "new way" generate worse code in some cases?

Good question. The new way does require an additional compare instruction to test where control continues after the loop. One for each output edge. But, yes, there is a tradeoff here. I think it's worth assessing if the "new way" can replace the "old way" at some point. My thinking here is to be conservative and keep the "old way" for now as I'm a little hesitant to replace it without more performance data.

Right, I understand that using an i32 instead of an i1 means that you need extra icmp instructions in the IR, but does it actually cause more instructions in the final generated code (for AMDGPU)? If the i1 was stored in a general purpose register then you would need a cmp anyway to use it to control a conditional branch.

[bcahoon]

Based upon reviewer feedback, this update changes the name of the command-line option, and passes the command-line value as a parameter to CreateControlFlowHub

[bcahoon]

In D127831#3891852, @foad wrote:

In D127831#3890092, @bcahoon wrote:

In D127831#3887582, @foad wrote:

Why do we still need the "old way"? Does the "new way" generate worse code in some cases?

Good question. The new way does require an additional compare instruction to test where control continues after the loop. One for each output edge. But, yes, there is a tradeoff here. I think it's worth assessing if the "new way" can replace the "old way" at some point. My thinking here is to be conservative and keep the "old way" for now as I'm a little hesitant to replace it without more performance data.

Right, I understand that using an i32 instead of an i1 means that you need extra icmp instructions in the IR, but does it actually cause more instructions in the final generated code (for AMDGPU)? If the i1 was stored in a general purpose register then you would need a cmp anyway to use it to control a conditional branch.

Only a handful of code gen LIT tests fail if I enable the new way, with an integer value for all cases. I was surprised it was so few. The code differences in the tests are not significant. When boolean values are used, the compiler generates and instructions, and when the integer value is used the compiler generate cmp instructions instead. Some other minor differences in one of the tests, e.g., moving a constant to an sgpr. I can try to find and run some other tests and check the generated code.

[sameerds]

In D127831#3891852, @foad wrote:

Right, I understand that using an i32 instead of an i1 means that you need extra icmp instructions in the IR, but does it actually cause more instructions in the final generated code (for AMDGPU)? If the i1 was stored in a general purpose register then you would need a cmp anyway to use it to control a conditional branch.

I would expect that the i1 values get packed into an sreg, and then used in cbranch_vccz? That wouldn't need a cmp to actually compare the i1 value.

[sameerds]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

1807

This is more curiosity than comment ... what is the advantage of using an Optional here? How does it compare to just using ~0 as the (maximum) default value?

[foad]

In D127831#3893757, @sameerds wrote:

In D127831#3891852, @foad wrote:

Right, I understand that using an i32 instead of an i1 means that you need extra icmp instructions in the IR, but does it actually cause more instructions in the final generated code (for AMDGPU)? If the i1 was stored in a general purpose register then you would need a cmp anyway to use it to control a conditional branch.

I would expect that the i1 values get packed into an sreg, and then used in cbranch_vccz? That wouldn't need a cmp to actually compare the i1 value.

OK, if they are divergent and get packed into an SGPR with one bit per lane then that does sound much better than using one VGPR per value. And the threshold of 32 makes some sense, since it's roughly equal to the wavefront size.

[bcahoon]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

1807

My first instinct was to use ~0U since I'm used to that. But, then I ended up using Optional since it makes it explicit that the value may not be set and the code doesn't rely on a sentinel value.

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

 ///    hub is introduced, there is a new path through the hub along which Use is
 ///    reachable from entry without passing through Def, and SSA is no longer
 ///    valid. To fix this, we need to look at all the blocks post-dominated by
 ///    the hub on the one hand, and dominated by Out2 on the other. This is left
 ///    for the caller to accomplish, since each specific use of this function
 ///    may have additional information which simplifies this fixup. For example,
 ///    see restoreSSA() in the UnifyLoopExits pass.
 BasicBlock *CreateControlFlowHub(DomTreeUpdater *DTU,
-                                 SmallVectorImpl<BasicBlock *> &GuardBlocks,
-                                 const SetVector<BasicBlock *> &Predecessors,
-                                 const SetVector<BasicBlock *> &Successors,
-                                 const StringRef Prefix);
+    const StringRef Prefix,
+    Optional<unsigned> MaxControlFlowBooleans = None);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 #define DEBUG_TYPE "basicblock-utils"
 
 static cl::opt<unsigned> MaxDeoptOrUnreachableSuccessorCheckDepth(
     "max-deopt-or-unreachable-succ-check-depth", cl::init(8), cl::Hidden,
     cl::desc("Set the maximum path length when checking whether a basic block "
              "is followed by a block that either has a terminating "
              "deoptimizing call or is terminated with an unreachable"));
 
 void llvm::detachDeadBlocks(
     ArrayRef<BasicBlock *> BBs,
     SmallVectorImpl<DominatorTree::UpdateType> *Updates,
     bool KeepOneInputPHIs) {
   for (auto *BB : BBs) {
     // Loop through all of our successors and make sure they know that one
     // of their predecessors is going away.
     SmallPtrSet<BasicBlock *, 4> UniqueSuccessors;
     for (BasicBlock *Succ : successors(BB)) {
       Succ->removePredecessor(BB, KeepOneInputPHIs);
       if (Updates && UniqueSuccessors.insert(Succ).second)
         Updates->push_back({DominatorTree::Delete, BB, Succ});
     }

 static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,
                           const SetVector<BasicBlock *> &Incoming,
                           BasicBlock *FirstGuardBlock) {
   auto I = Out->begin();
   while (I != Out->end() && isa<PHINode>(I)) {
     auto Phi = cast<PHINode>(I);
     auto NewPhi =
         PHINode::Create(Phi->getType(), Incoming.size(),
-                        Phi->getName() + ".moved", &FirstGuardBlock->back());
+                        Phi->getName() + ".moved", &FirstGuardBlock->front());
     for (auto *In : Incoming) {
       Value *V = UndefValue::get(Phi->getType());
       if (In == Out) {
         V = NewPhi;
       } else if (Phi->getBasicBlockIndex(In) != -1) {
         V = Phi->removeIncomingValue(In, false);
       }
       NewPhi->addIncoming(V, In);
     }
     assert(NewPhi->getNumIncomingValues() == Incoming.size());
     if (Phi->getNumOperands() == 0) {
       Phi->replaceAllUsesWith(NewPhi);
       I = Phi->eraseFromParent();
       continue;
     }
     Phi->addIncoming(NewPhi, GuardBlock);
     ++I;
   }
 }
 
-using BBPredicates = DenseMap<BasicBlock *, PHINode *>;
+using BBPredicates = DenseMap<BasicBlock *, Instruction *>;
 using BBSetVector = SetVector<BasicBlock *>;
 
 // Redirects the terminator of the incoming block to the first guard
 // block in the hub. The condition of the original terminator (if it
 // was conditional) and its original successors are returned as a
 // tuple <condition, succ0, succ1>. The function additionally filters
 // out successors that are not in the set of outgoing blocks.
 //
for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
     BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
                        GuardBlocks[i]);
   }
 
   // Remove the last block from the guard list.
   GuardBlocks.pop_back();
 }
 
-// Capture the existing control flow as guard predicates, and redirect
-// control flow from \p Incoming block through the \p GuardBlocks to the
-// \p Outgoing blocks.
-//
-// There is one guard predicate for each outgoing block OutBB. The
-// predicate represents whether the hub should transfer control flow
-// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates
-// them in the same order as the Outgoing set-vector, and control
-// branches to the first outgoing block whose predicate evaluates to true.
-static void
-convertToGuardPredicates(SmallVectorImpl<BasicBlock *> &GuardBlocks,
-                         SmallVectorImpl<WeakVH> &DeletionCandidates,
-                         const BBSetVector &Incoming,
-                         const BBSetVector &Outgoing, const StringRef Prefix) {
-  BBPredicates GuardPredicates;
-  auto F = Incoming.front()->getParent();
+/// We are using one integer to represent the block we are branching to. Then at
+/// each guard block, the predicate was calcuated using a simple `icmp eq`.
+static void calcPredicateUsingInteger(
+    const BBSetVector &Incoming, const BBSetVector &Outgoing,
+    SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates) {
   auto &Context = Incoming.front()->getContext();
-  auto BoolTrue = ConstantInt::getTrue(Context);
-  auto BoolFalse = ConstantInt::getFalse(Context);
+  auto FirstGuardBlock = GuardBlocks.front();
 
-  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i)
-    GuardBlocks.push_back(
-        BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
+  auto Phi = PHINode::Create(Type::getInt32Ty(Context), Incoming.size(),
+                             "merged.bb.idx", FirstGuardBlock);
+
+  for (auto In : Incoming) {
+    Value *Condition;
+    BasicBlock *Succ0;
+    BasicBlock *Succ1;
+    std::tie(Condition, Succ0, Succ1) =
+        redirectToHub(In, FirstGuardBlock, Outgoing);
+    Value *IncomingId = nullptr;
+    if (Succ0 && Succ1) {
+      // target_bb_index = Condition ? index_of_succ0 : index_of_succ1.
+      auto Succ0Iter = find(Outgoing, Succ0);
+      auto Succ1Iter = find(Outgoing, Succ1);
+      Value *Id0 = ConstantInt::get(Type::getInt32Ty(Context),
+                                    std::distance(Outgoing.begin(), Succ0Iter));
+      Value *Id1 = ConstantInt::get(Type::getInt32Ty(Context),
+                                    std::distance(Outgoing.begin(), Succ1Iter));
+      IncomingId = SelectInst::Create(Condition, Id0, Id1, "target.bb.idx",
+                                      In->getTerminator());
+    } else {
+      // Get the index of the non-null successor.
+      auto SuccIter = Succ0 ? find(Outgoing, Succ0) : find(Outgoing, Succ1);
+      IncomingId = ConstantInt::get(Type::getInt32Ty(Context),
+                                    std::distance(Outgoing.begin(), SuccIter));
+    }
+    Phi->addIncoming(IncomingId, In);
+  }
+
+  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
+    auto Out = Outgoing[i];
+    auto Cmp = ICmpInst::Create(Instruction::ICmp, ICmpInst::ICMP_EQ, Phi,
+                                ConstantInt::get(Type::getInt32Ty(Context), i),
+                                Out->getName() + ".predicate", GuardBlocks[i]);
+    GuardPredicates[Out] = Cmp;
+  }
+}
 
+/// We record the predicate of each outgoing block using a phi of boolean.
+static void calcPredicateUsingBooleans(
+    const BBSetVector &Incoming, const BBSetVector &Outgoing,
+    SmallVectorImpl<BasicBlock *> &GuardBlocks, BBPredicates &GuardPredicates,
+    SmallVectorImpl<WeakVH> &DeletionCandidates) {
+  auto &Context = Incoming.front()->getContext();
+  auto BoolTrue = ConstantInt::getTrue(Context);
+  auto BoolFalse = ConstantInt::getFalse(Context);
   auto FirstGuardBlock = GuardBlocks.front();
 
   // The predicate for the last outgoing is trivially true, and so we
   // process only the first N-1 successors.
   for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
     auto Out = Outgoing[i];
     LLVM_DEBUG(dbgs() << "Creating guard for " << Out->getName() << "\n");
 
for (auto *In : Incoming) {
     // for Succ0 and Succ1 complement each other. If Succ0 is visited
     // first in the loop below, control will branch to Succ0 using the
     // corresponding predicate. But if that branch is not taken, then
     // control must reach Succ1, which means that the incoming value of
     // the predicate from `In` is true for Succ1.
     bool OneSuccessorDone = false;
     for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
       auto Out = Outgoing[i];
-      auto Phi = GuardPredicates[Out];
+      PHINode *Phi = cast<PHINode>(GuardPredicates[Out]);
       if (Out != Succ0 && Out != Succ1) {
         Phi->addIncoming(BoolFalse, In);
       } else if (!Succ0 || !Succ1 || OneSuccessorDone) {
         // Optimization: When only one successor is an outgoing block,
         // the incoming predicate from `In` is always true.
         Phi->addIncoming(BoolTrue, In);
       } else {
         assert(Succ0 && Succ1);
         if (Out == Succ0) {
           Phi->addIncoming(Condition, In);
         } else {
           auto Inverted = invertCondition(Condition);
           DeletionCandidates.push_back(Condition);
           Phi->addIncoming(Inverted, In);
         }
         OneSuccessorDone = true;
       }
     }
   }
+}
+
+// Capture the existing control flow as guard predicates, and redirect
+// control flow from \p Incoming block through the \p GuardBlocks to the
+// \p Outgoing blocks.
+//
+// There is one guard predicate for each outgoing block OutBB. The
+// predicate represents whether the hub should transfer control flow
+// to OutBB. These predicates are NOT ORTHOGONAL. The Hub evaluates
+// them in the same order as the Outgoing set-vector, and control
+// branches to the first outgoing block whose predicate evaluates to true.
+static void
+convertToGuardPredicates(SmallVectorImpl<BasicBlock *> &GuardBlocks,
+                         SmallVectorImpl<WeakVH> &DeletionCandidates,
+                         const BBSetVector &Incoming,
+                         const BBSetVector &Outgoing, const StringRef Prefix,
+                         Optional<unsigned> MaxControlFlowBooleans) {
+  BBPredicates GuardPredicates;
+  auto F = Incoming.front()->getParent();
+
+  for (int i = 0, e = Outgoing.size() - 1; i != e; ++i)
+    GuardBlocks.push_back(
+        BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
+
+  // When we are using an integer to record which target block to jump to, we
+  // are creating less live values, actually we are using one single integer to
+  // store the index of the target block. When we are using booleans to store
+  // the branching information, we need (N-1) boolean values, where N is the
+  // number of outgoing block.
+  if (!MaxControlFlowBooleans || Outgoing.size() <= *MaxControlFlowBooleans)
+    calcPredicateUsingBooleans(Incoming, Outgoing, GuardBlocks, GuardPredicates,
+                               DeletionCandidates);
+  else
+    calcPredicateUsingInteger(Incoming, Outgoing, GuardBlocks, GuardPredicates);
+
   setupBranchForGuard(GuardBlocks, Outgoing, GuardPredicates);
 }
 
 BasicBlock *llvm::CreateControlFlowHub(
     DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
     const BBSetVector &Incoming, const BBSetVector &Outgoing,
-    const StringRef Prefix) {
+    const StringRef Prefix, Optional<unsigned> MaxControlFlowBooleans) {
   if (Outgoing.size() < 2)
     return Outgoing.front();
 
   SmallVector<DominatorTree::UpdateType, 16> Updates;
   if (DTU) {
     for (auto *In : Incoming) {
       for (auto Succ : successors(In))
         if (Outgoing.count(Succ))
           Updates.push_back({DominatorTree::Delete, In, Succ});
     }
   }
 
   SmallVector<WeakVH, 8> DeletionCandidates;
   convertToGuardPredicates(GuardBlocks, DeletionCandidates, Incoming, Outgoing,
-                           Prefix);
+                           Prefix, MaxControlFlowBooleans);
   auto FirstGuardBlock = GuardBlocks.front();
   
   // Update the PHINodes in each outgoing block to match the new control flow.
   for (int i = 0, e = GuardBlocks.size(); i != e; ++i)
     reconnectPhis(Outgoing[i], GuardBlocks[i], Incoming, FirstGuardBlock);
 
   reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock);
 

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

 
 #include "llvm/Transforms/Utils/UnifyLoopExits.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 #define DEBUG_TYPE "unify-loop-exits"
 
 using namespace llvm;
 
+static cl::opt<unsigned> MaxBooleansInControlFlowHub(
+    "max-booleans-in-control-flow-hub", cl::init(32), cl::Hidden,
+    cl::desc("Set the maximum number of outgoing blocks for using a boolean "
+             "value to record the exiting block in CreateControlFlowHub."));
+
 namespace {
 struct UnifyLoopExitsLegacyPass : public FunctionPass {
   static char ID;
   UnifyLoopExitsLegacyPass() : FunctionPass(ID) {
     initializeUnifyLoopExitsLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
static void restoreSSA(const DominatorTree &DT, const Loop *L,
 
   for (auto II : ExternalUsers) {
     // For each Def used outside the loop, create NewPhi in
     // LoopExitBlock. NewPhi receives Def only along exiting blocks that
     // dominate it, while the remaining values are undefined since those paths
     // didn't exist in the original CFG.
     auto Def = II.first;
     LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
-    auto NewPhi = PHINode::Create(Def->getType(), Incoming.size(),
-                                  Def->getName() + ".moved",
-                                  LoopExitBlock->getTerminator());
+    auto NewPhi =
+        PHINode::Create(Def->getType(), Incoming.size(),
+                        Def->getName() + ".moved", &LoopExitBlock->front());
     for (auto *In : Incoming) {
       LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
       if (Def->getParent() == In || DT.dominates(Def, In)) {
         LLVM_DEBUG(dbgs() << "dominated\n");
         NewPhi->addIncoming(Def, In);
       } else {
         LLVM_DEBUG(dbgs() << "not dominated\n");
         NewPhi->addIncoming(UndefValue::get(Def->getType()), In);
static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
 
   if (Exits.size() <= 1) {
     LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
     return false;
   }
 
   SmallVector<BasicBlock *, 8> GuardBlocks;
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
-  auto LoopExitBlock = CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks,
-                                            Exits, "loop.exit");
+  auto LoopExitBlock =
+      CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks, Exits, "loop.exit",
+                           MaxBooleansInControlFlowHub.getValue());
 
   restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
 
 #if defined(EXPENSIVE_CHECKS)
   assert(DT.verify(DominatorTree::VerificationLevel::Full));
 #else
   assert(DT.verify(DominatorTree::VerificationLevel::Fast));
 #endif // EXPENSIVE_CHECKS

llvm/test/CodeGen/AMDGPU/si-annotate-cf.ll

 ; SI-NEXT:    s_and_b64 s[0:1], exec, s[4:5]
 ; SI-NEXT:    s_and_b64 s[2:3], exec, s[2:3]
 ; SI-NEXT:    s_and_b64 s[4:5], exec, s[6:7]
 ; SI-NEXT:    s_mov_b32 s7, 0xf000
 ; SI-NEXT:    s_mov_b32 s6, -1
 ; SI-NEXT:    v_mov_b32_e32 v0, 3
 ; SI-NEXT:    s_branch .LBB3_3
 ; SI-NEXT:  .LBB3_1: ; in Loop: Header=BB3_3 Depth=1
-; SI-NEXT:    s_mov_b64 s[10:11], -1
 ; SI-NEXT:    s_mov_b64 s[8:9], 0
+; SI-NEXT:    s_mov_b64 s[10:11], -1
 ; SI-NEXT:    s_mov_b64 s[12:13], -1
 ; SI-NEXT:  .LBB3_2: ; %Flow
 ; SI-NEXT:    ; in Loop: Header=BB3_3 Depth=1
 ; SI-NEXT:    s_and_b64 vcc, exec, s[12:13]
 ; SI-NEXT:    s_cbranch_vccnz .LBB3_8
 ; SI-NEXT:  .LBB3_3: ; %while.cond
 ; SI-NEXT:    ; =>This Inner Loop Header: Depth=1
-; SI-NEXT:    s_mov_b64 s[8:9], -1
 ; SI-NEXT:    s_mov_b64 s[10:11], -1
+; SI-NEXT:    s_mov_b64 s[8:9], -1
 ; SI-NEXT:    s_mov_b64 s[12:13], -1
 ; SI-NEXT:    s_mov_b64 vcc, s[0:1]
 ; SI-NEXT:    s_cbranch_vccz .LBB3_2
 ; SI-NEXT:  ; %bb.4: ; %convex.exit
 ; SI-NEXT:    ; in Loop: Header=BB3_3 Depth=1
 ; SI-NEXT:    s_mov_b64 vcc, s[2:3]
 ; SI-NEXT:    s_cbranch_vccz .LBB3_1
 ; SI-NEXT:  ; %bb.5: ; %if.end

 ; FLAT-NEXT:    s_and_b64 s[0:1], exec, s[4:5]
 ; FLAT-NEXT:    s_and_b64 s[2:3], exec, s[2:3]
 ; FLAT-NEXT:    s_and_b64 s[4:5], exec, s[6:7]
 ; FLAT-NEXT:    s_mov_b32 s7, 0xf000
 ; FLAT-NEXT:    s_mov_b32 s6, -1
 ; FLAT-NEXT:    v_mov_b32_e32 v0, 3
 ; FLAT-NEXT:    s_branch .LBB3_3
 ; FLAT-NEXT:  .LBB3_1: ; in Loop: Header=BB3_3 Depth=1
-; FLAT-NEXT:    s_mov_b64 s[10:11], -1
 ; FLAT-NEXT:    s_mov_b64 s[8:9], 0
+; FLAT-NEXT:    s_mov_b64 s[10:11], -1
 ; FLAT-NEXT:    s_mov_b64 s[12:13], -1
 ; FLAT-NEXT:  .LBB3_2: ; %Flow
 ; FLAT-NEXT:    ; in Loop: Header=BB3_3 Depth=1
 ; FLAT-NEXT:    s_and_b64 vcc, exec, s[12:13]
 ; FLAT-NEXT:    s_cbranch_vccnz .LBB3_8
 ; FLAT-NEXT:  .LBB3_3: ; %while.cond
 ; FLAT-NEXT:    ; =>This Inner Loop Header: Depth=1
-; FLAT-NEXT:    s_mov_b64 s[8:9], -1
 ; FLAT-NEXT:    s_mov_b64 s[10:11], -1
+; FLAT-NEXT:    s_mov_b64 s[8:9], -1
 ; FLAT-NEXT:    s_mov_b64 s[12:13], -1
 ; FLAT-NEXT:    s_mov_b64 vcc, s[0:1]
 ; FLAT-NEXT:    s_cbranch_vccz .LBB3_2
 ; FLAT-NEXT:  ; %bb.4: ; %convex.exit
 ; FLAT-NEXT:    ; in Loop: Header=BB3_3 Depth=1
 ; FLAT-NEXT:    s_mov_b64 vcc, s[2:3]
 ; FLAT-NEXT:    s_cbranch_vccz .LBB3_1
 ; FLAT-NEXT:  ; %bb.5: ; %if.end

llvm/test/Transforms/FixIrreducible/basic.ll

 ; CHECK-NEXT:    [[L:%.*]] = add i32 [[L_PHI_MOVED:%.*]], 1
 ; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ; CHECK:       irr.guard:
-; CHECK-NEXT:    [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ]
+; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY:%.*]] ], [ [[L]], [[LEFT]] ]
 ; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
-; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L]], [[LEFT]] ]
+; CHECK-NEXT:    [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY]] ], [ false, [[LEFT]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]]
 ;
 entry:
   br i1 %PredEntry, label %left, label %right
 
 left:
   %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
   %L = add i32 %L.phi, 1

 ; CHECK:       left:
 ; CHECK-NEXT:    br i1 [[PREDLEFT:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
 ; CHECK:       right:
 ; CHECK-NEXT:    br i1 [[PREDRIGHT:%.*]], label [[IRR_GUARD]], label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[Z:%.*]] = phi i32 [ [[L_PHI_MOVED:%.*]], [[LEFT:%.*]] ], [ [[R_PHI_MOVED:%.*]], [[RIGHT:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ; CHECK:       irr.guard:
-; CHECK-NEXT:    [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEFT]] ]
+; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY:%.*]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
 ; CHECK-NEXT:    [[L_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
-; CHECK-NEXT:    [[R_PHI_MOVED]] = phi i32 [ [[R_PHI_MOVED]], [[RIGHT]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[L_PHI_MOVED]], [[LEFT]] ]
+; CHECK-NEXT:    [[GUARD_LEFT:%.*]] = phi i1 [ true, [[RIGHT]] ], [ [[PREDENTRY:%.*]], [[ENTRY]] ], [ false, [[LEFT]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_LEFT]], label [[LEFT]], label [[RIGHT]]
 ;
 entry:
   br i1 %PredEntry, label %left, label %right
 
 left:
   %L.phi = phi i32 [%X, %entry], [%R.phi, %right]
   br i1 %PredLeft, label %right, label %exit

 ; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
 ; CHECK:       D:
 ; CHECK-NEXT:    [[D_INC:%.*]] = add i32 [[D_PHI_MOVED:%.*]], 1
 ; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_INC]], [[D:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ; CHECK:       irr.guard:
+; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[A_INC]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
+; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y]], [[B]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
 ; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ [[PREDB_INV]], [[B]] ], [ [[PREDA:%.*]], [[A]] ], [ false, [[C]] ]
-; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[Y:%.*]], [[B]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
-; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ [[Y]], [[B]] ], [ [[A_INC]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
 ;
 entry:
   br i1 %PredEntry, label %A, label %B
 
 A:
   %A.inc = add i32 %X, 1
   br i1 %PredA, label %C, label %D

 ; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
 ; CHECK:       D:
 ; CHECK-NEXT:    [[D_INC:%.*]] = add i32 [[D_PHI_MOVED:%.*]], 1
 ; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT]], label [[IRR_GUARD]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[RET:%.*]] = phi i32 [ [[C_PHI_MOVED:%.*]], [[C:%.*]] ], [ [[D_INC]], [[D:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ; CHECK:       irr.guard:
-; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ true, [[A]] ], [ false, [[C]] ], [ false, [[B]] ]
-; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ undef, [[B]] ]
 ; CHECK-NEXT:    [[D_PHI_MOVED]] = phi i32 [ [[D_PHI_MOVED]], [[D]] ], [ undef, [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ [[Y:%.*]], [[B]] ]
+; CHECK-NEXT:    [[C_PHI_MOVED]] = phi i32 [ [[D_INC]], [[D]] ], [ [[X]], [[A]] ], [ [[C_PHI_MOVED]], [[C]] ], [ undef, [[B]] ]
+; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[D]] ], [ true, [[A]] ], [ false, [[C]] ], [ false, [[B]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
 ;
 entry:
   br i1 %PredEntry, label %A, label %B
 
 A:
   %A.inc = add i32 %X, 1
   br label %C

 ; CHECK-NEXT:    br label [[D:%.*]]
 ; CHECK:       D:
 ; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[E:%.*]]
 ; CHECK:       E:
 ; CHECK-NEXT:    br label [[IRR_GUARD]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 [[B_PHI_MOVED]]
 ; CHECK:       irr.guard:
-; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ true, [[E]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[A:%.*]] ]
+; CHECK-NEXT:    [[B_PHI_MOVED]] = phi i32 [ undef, [[E]] ], [ [[Y:%.*]], [[ENTRY:%.*]] ], [ [[A_INC]], [[A:%.*]] ]
 ; CHECK-NEXT:    [[A_PHI_MOVED]] = phi i32 [ [[C_INC]], [[E]] ], [ [[X:%.*]], [[ENTRY]] ], [ [[A_PHI_MOVED]], [[A]] ]
-; CHECK-NEXT:    [[B_PHI_MOVED]] = phi i32 [ undef, [[E]] ], [ [[Y:%.*]], [[ENTRY]] ], [ [[A_INC]], [[A]] ]
+; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ true, [[E]] ], [ [[PREDENTRY:%.*]], [[ENTRY]] ], [ false, [[A]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[B:%.*]]
 ;
 entry:
   br i1 %PredEntry, label %A, label %B
 
 A:
   %A.phi = phi i32 [%X, %entry], [%C.inc, %E]
   %A.inc = add i32 %A.phi, 1

llvm/test/Transforms/StructurizeCFG/workarounds/needs-fr-ule.ll

 ; CHECK-NEXT:    [[TMP7:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ [[TMP3]], [[FLOW7:%.*]] ]
 ; CHECK-NEXT:    [[TMP8:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ [[TMP4]], [[FLOW7]] ]
 ; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ [[PRED4_INV]], [[COND_TRUE49]] ], [ [[TMP5]], [[FLOW7]] ]
 ; CHECK-NEXT:    br i1 [[TMP9]], label [[WHILE_BODY63:%.*]], label [[FLOW9:%.*]]
 ; CHECK:       while.body63:
 ; CHECK-NEXT:    br i1 [[PRED5_INV]], label [[WHILE_COND47:%.*]], label [[FLOW10:%.*]]
 ; CHECK:       Flow9:
 ; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ [[TMP22:%.*]], [[FLOW10]] ], [ undef, [[FLOW8]] ]
-; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ false, [[FLOW10]] ], [ undef, [[FLOW8]] ]
-; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ true, [[FLOW10]] ], [ [[TMP7]], [[FLOW8]] ]
-; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP8]], [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ true, [[FLOW10]] ], [ [[TMP7]], [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP8]], [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ false, [[FLOW10]] ], [ undef, [[FLOW8]] ]
 ; CHECK-NEXT:    [[TMP14:%.*]] = phi i1 [ [[TMP23:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ]
-; CHECK-NEXT:    [[DOTINV11:%.*]] = xor i1 [[TMP12]], true
-; CHECK-NEXT:    [[DOTINV:%.*]] = xor i1 [[TMP13]], true
+; CHECK-NEXT:    [[DOTINV11:%.*]] = xor i1 [[TMP11]], true
+; CHECK-NEXT:    [[DOTINV:%.*]] = xor i1 [[TMP12]], true
 ; CHECK-NEXT:    br i1 [[TMP14]], label [[LOOP_EXIT_GUARD1:%.*]], label [[IRR_GUARD]]
 ; CHECK:       while.cond47:
 ; CHECK-NEXT:    br label [[FLOW10]]
 ; CHECK:       cond.end61:
 ; CHECK-NEXT:    br label [[FLOW7]]
 ; CHECK:       Flow14:
 ; CHECK-NEXT:    [[TMP15:%.*]] = phi i1 [ [[TMP20:%.*]], [[FLOW15:%.*]] ], [ undef, [[LOOP_EXIT_GUARD1]] ]
 ; CHECK-NEXT:    [[TMP16:%.*]] = phi i1 [ [[TMP21:%.*]], [[FLOW15]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD1]] ]

 ; CHECK-NEXT:    [[TMP18:%.*]] = phi i1 [ false, [[LOR_RHS]] ], [ true, [[WHILE_COND]] ]
 ; CHECK-NEXT:    [[TMP19:%.*]] = phi i1 [ [[PRED9:%.*]], [[LOR_RHS]] ], [ [[PRED3]], [[WHILE_COND]] ]
 ; CHECK-NEXT:    br i1 [[TMP19]], label [[IRR_GUARD]], label [[FLOW13]]
 ; CHECK:       irr.guard:
 ; CHECK-NEXT:    [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[TMP10]], [[FLOW9]] ], [ [[TMP18]], [[FLOW12]] ]
 ; CHECK-NEXT:    [[GUARD_COND_TRUE49_INV:%.*]] = xor i1 [[GUARD_COND_TRUE49]], true
 ; CHECK-NEXT:    br i1 [[GUARD_COND_TRUE49_INV]], label [[COND_END61]], label [[FLOW7]]
 ; CHECK:       Flow15:
-; CHECK-NEXT:    [[TMP20]] = phi i1 [ false, [[IF_THEN69:%.*]] ], [ [[TMP11]], [[LOOP_EXIT_GUARD2:%.*]] ]
+; CHECK-NEXT:    [[TMP20]] = phi i1 [ false, [[IF_THEN69:%.*]] ], [ [[TMP13]], [[LOOP_EXIT_GUARD2:%.*]] ]
 ; CHECK-NEXT:    [[TMP21]] = phi i1 [ [[PRED8:%.*]], [[IF_THEN69]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD2]] ]
 ; CHECK-NEXT:    br label [[FLOW14:%.*]]
 ; CHECK:       loop.exit.guard:
 ; CHECK-NEXT:    br i1 [[TMP24:%.*]], label [[WHILE_END76:%.*]], label [[FLOW6]]
 ; CHECK:       Flow10:
 ; CHECK-NEXT:    [[TMP22]] = phi i1 [ [[PRED6:%.*]], [[WHILE_COND47]] ], [ undef, [[WHILE_BODY63]] ]
 ; CHECK-NEXT:    [[TMP23]] = phi i1 [ false, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ]
 ; CHECK-NEXT:    br label [[FLOW9]]

llvm/test/Transforms/StructurizeCFG/workarounds/needs-unified-loop-exits.ll

 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ true, [[B1]] ], [ undef, [[H1]] ]
 ; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[PREDB1:%.*]], [[B1]] ], [ [[PREDH1]], [[H1]] ]
 ; CHECK-NEXT:    br i1 [[TMP1]], label [[H2:%.*]], label [[FLOW4:%.*]]
 ; CHECK:       H2:
 ; CHECK-NEXT:    br i1 [[PREDH2:%.*]], label [[B2:%.*]], label [[FLOW:%.*]]
 ; CHECK:       B2:
 ; CHECK-NEXT:    br i1 [[PREDB2_INV]], label [[L2:%.*]], label [[FLOW2:%.*]]
 ; CHECK:       Flow:
-; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ false, [[FLOW2]] ], [ undef, [[H2]] ]
-; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ false, [[FLOW2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ false, [[FLOW2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ false, [[FLOW2]] ], [ undef, [[H2]] ]
 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW2]] ], [ true, [[H2]] ]
 ; CHECK-NEXT:    br i1 [[TMP4]], label [[LOOP_EXIT_GUARD1:%.*]], label [[H2]]
 ; CHECK:       L2:
 ; CHECK-NEXT:    br label [[FLOW2]]
 ; CHECK:       L1:
 ; CHECK-NEXT:    br label [[FLOW5:%.*]]
 ; CHECK:       B1:
 ; CHECK-NEXT:    br label [[FLOW3]]
 ; CHECK:       C:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       Flow5:
-; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ undef, [[L1:%.*]] ], [ [[TMP2]], [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ undef, [[L1:%.*]] ], [ [[TMP3]], [[LOOP_EXIT_GUARD1]] ]
 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ false, [[L1]] ], [ true, [[LOOP_EXIT_GUARD1]] ]
 ; CHECK-NEXT:    br label [[FLOW4]]
 ; CHECK:       loop.exit.guard:
 ; CHECK-NEXT:    br i1 [[TMP8:%.*]], label [[C:%.*]], label [[EXIT]]
 ; CHECK:       Flow2:
 ; CHECK-NEXT:    [[TMP7]] = phi i1 [ false, [[L2]] ], [ true, [[B2]] ]
 ; CHECK-NEXT:    br label [[FLOW]]
 ; CHECK:       Flow4:
 ; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP5]], [[FLOW5]] ], [ [[TMP0]], [[FLOW3]] ]
 ; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ [[TMP6]], [[FLOW5]] ], [ true, [[FLOW3]] ]
 ; CHECK-NEXT:    br i1 [[TMP9]], label [[LOOP_EXIT_GUARD:%.*]], label [[H1]]
 ; CHECK:       loop.exit.guard1:
-; CHECK-NEXT:    br i1 [[TMP3]], label [[L1]], label [[FLOW5]]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[L1]], label [[FLOW5]]
 ;
 entry:
   br label %H1
 
 H1:                                               ; preds = %L1, %entry
   br i1 %PredH1, label %H2, label %B1
 
 H2:                                               ; preds = %B1, %L2, %H1

 ; CHECK:       H2:
 ; CHECK-NEXT:    br i1 [[PREDH2_INV]], label [[H3:%.*]], label [[FLOW4:%.*]]
 ; CHECK:       H3:
 ; CHECK-NEXT:    br i1 [[PREDH3_INV]], label [[L2:%.*]], label [[FLOW:%.*]]
 ; CHECK:       L2:
 ; CHECK-NEXT:    br i1 [[PREDL2_INV]], label [[L13:%.*]], label [[FLOW3:%.*]]
 ; CHECK:       Flow:
 ; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
-; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP7]], [[FLOW3]] ], [ false, [[H3]] ]
-; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP8:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP8:%.*]], [[FLOW3]] ], [ false, [[H3]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP8]], [[FLOW3]] ], [ true, [[H3]] ]
 ; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP9:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[LOOP_EXIT_GUARD2:%.*]], label [[H3]]
 ; CHECK:       L13:
 ; CHECK-NEXT:    br label [[FLOW3]]
 ; CHECK:       Flow5:
 ; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP10:%.*]], [[LOOP_EXIT_GUARD1:%.*]] ], [ true, [[LOOP_EXIT_GUARD:%.*]] ]
 ; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD1]] ], [ true, [[LOOP_EXIT_GUARD]] ]
 ; CHECK-NEXT:    br i1 [[TMP5]], label [[L1:%.*]], label [[FLOW6:%.*]]
 ; CHECK:       L1:
 ; CHECK-NEXT:    br label [[FLOW6]]
 ; CHECK:       Flow6:
 ; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ [[PREDL1:%.*]], [[L1]] ], [ [[TMP4]], [[FLOW5:%.*]] ]
 ; CHECK-NEXT:    br i1 [[TMP6]], label [[EXIT:%.*]], label [[H1]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       loop.exit.guard:
 ; CHECK-NEXT:    br i1 [[DOTINV:%.*]], label [[LOOP_EXIT_GUARD1]], label [[FLOW5]]
 ; CHECK:       loop.exit.guard1:
 ; CHECK-NEXT:    br label [[FLOW5]]
 ; CHECK:       Flow3:
-; CHECK-NEXT:    [[TMP7]] = phi i1 [ false, [[L13]] ], [ undef, [[L2]] ]
-; CHECK-NEXT:    [[TMP8]] = phi i1 [ true, [[L13]] ], [ false, [[L2]] ]
+; CHECK-NEXT:    [[TMP7]] = phi i1 [ true, [[L13]] ], [ false, [[L2]] ]
+; CHECK-NEXT:    [[TMP8]] = phi i1 [ false, [[L13]] ], [ undef, [[L2]] ]
 ; CHECK-NEXT:    [[TMP9]] = phi i1 [ [[PREDL13_INV]], [[L13]] ], [ true, [[L2]] ]
 ; CHECK-NEXT:    br label [[FLOW]]
 ; CHECK:       Flow4:
-; CHECK-NEXT:    [[TMP10]] = phi i1 [ [[TMP0]], [[LOOP_EXIT_GUARD2]] ], [ false, [[H2]] ]
+; CHECK-NEXT:    [[TMP10]] = phi i1 [ [[TMP2]], [[LOOP_EXIT_GUARD2]] ], [ false, [[H2]] ]
 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ [[TMP1]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
-; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ [[TMP2]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ [[TMP0]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
 ; CHECK-NEXT:    [[DOTINV]] = xor i1 [[TMP11]], true
 ; CHECK-NEXT:    br i1 [[TMP12]], label [[LOOP_EXIT_GUARD]], label [[H2]]
 ; CHECK:       loop.exit.guard2:
 ; CHECK-NEXT:    br label [[FLOW4]]
 ;
 {
 entry:
   br label %H1

llvm/test/Transforms/UnifyLoopExits/integer_guards.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=unify-loop-exits -max-booleans-in-control-flow-hub=1 -S | FileCheck %s
+; RUN: opt < %s -passes=unify-loop-exits -S | FileCheck --check-prefix=BOOLEAN %s
+
+; A loop with multiple exit blocks.
+
+define void @loop_two_exits(i1 %PredEntry, i1 %PredA) {
+; CHECK-LABEL: @loop_two_exits(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[E:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[C:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    br label [[D:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[INC2]] = add i32 [[INC1]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
+; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       D:
+; CHECK-NEXT:    unreachable
+; CHECK:       E:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[MERGED_BB_IDX:%.*]] = phi i32 [ 0, [[A]] ], [ 1, [[C]] ]
+; CHECK-NEXT:    [[B_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 0
+; CHECK-NEXT:    br i1 [[B_PREDICATE]], label [[B:%.*]], label [[E]]
+;
+; BOOLEAN-LABEL: @loop_two_exits(
+; BOOLEAN-NEXT:  entry:
+; BOOLEAN-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[E:%.*]]
+; BOOLEAN:       A:
+; BOOLEAN-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[C:%.*]] ]
+; BOOLEAN-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C]]
+; BOOLEAN:       B:
+; BOOLEAN-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0:[0-9]+]]
+; BOOLEAN-NEXT:    br label [[D:%.*]]
+; BOOLEAN:       C:
+; BOOLEAN-NEXT:    [[INC2]] = add i32 [[INC1]], 1
+; BOOLEAN-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
+; BOOLEAN-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; BOOLEAN:       D:
+; BOOLEAN-NEXT:    unreachable
+; BOOLEAN:       E:
+; BOOLEAN-NEXT:    ret void
+; BOOLEAN:       loop.exit.guard:
+; BOOLEAN-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
+; BOOLEAN-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[E]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %E
+
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %C ]
+  br i1 %PredA, label %B, label %C
+
+B:
+  tail call fastcc void @check(i32 1) #0
+  br label %D
+
+C:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %E
+
+D:
+  unreachable
+
+E:
+  ret void
+}
+
+; The loop exit blocks appear in an inner loop.
+
+define void @inner_loop(i1 %PredEntry, i1 %PredA, i1 %PredB) {
+; CHECK-LABEL: @inner_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[I:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[OUTER1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER2:%.*]], [[G:%.*]] ]
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[INNER1:%.*]] = phi i32 [ 0, [[A]] ], [ [[INNER2:%.*]], [[F:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; CHECK-NEXT:    br label [[H:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD2]], label [[F]]
+; CHECK:       E:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[H]]
+; CHECK:       F:
+; CHECK-NEXT:    [[INNER2]] = add i32 [[INNER1]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[INNER2]], 20
+; CHECK-NEXT:    br i1 [[CMP1]], label [[B]], label [[LOOP_EXIT_GUARD2]]
+; CHECK:       G:
+; CHECK-NEXT:    [[OUTER2]] = add i32 [[OUTER1]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[OUTER2]], 10
+; CHECK-NEXT:    br i1 [[CMP2]], label [[A]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       H:
+; CHECK-NEXT:    unreachable
+; CHECK:       I:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[MERGED_BB_IDX:%.*]] = phi i32 [ 2, [[G]] ], [ [[MERGED_BB_IDX_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
+; CHECK-NEXT:    [[C_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 0
+; CHECK-NEXT:    br i1 [[C_PREDICATE]], label [[C:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    [[E_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 1
+; CHECK-NEXT:    br i1 [[E_PREDICATE]], label [[E:%.*]], label [[I]]
+; CHECK:       loop.exit.guard2:
+; CHECK-NEXT:    [[MERGED_BB_IDX_MOVED]] = phi i32 [ 0, [[B]] ], [ 1, [[D]] ], [ undef, [[F]] ]
+; CHECK-NEXT:    [[MERGED_BB_IDX3:%.*]] = phi i32 [ 0, [[B]] ], [ 0, [[D]] ], [ 1, [[F]] ]
+; CHECK-NEXT:    [[LOOP_EXIT_GUARD_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX3]], 0
+; CHECK-NEXT:    br i1 [[LOOP_EXIT_GUARD_PREDICATE]], label [[LOOP_EXIT_GUARD]], label [[G]]
+;
+; BOOLEAN-LABEL: @inner_loop(
+; BOOLEAN-NEXT:  entry:
+; BOOLEAN-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[I:%.*]]
+; BOOLEAN:       A:
+; BOOLEAN-NEXT:    [[OUTER1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[OUTER2:%.*]], [[G:%.*]] ]
+; BOOLEAN-NEXT:    br label [[B:%.*]]
+; BOOLEAN:       B:
+; BOOLEAN-NEXT:    [[INNER1:%.*]] = phi i32 [ 0, [[A]] ], [ [[INNER2:%.*]], [[F:%.*]] ]
+; BOOLEAN-NEXT:    br i1 [[PREDA:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
+; BOOLEAN:       C:
+; BOOLEAN-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; BOOLEAN-NEXT:    br label [[H:%.*]]
+; BOOLEAN:       D:
+; BOOLEAN-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD2]], label [[F]]
+; BOOLEAN:       E:
+; BOOLEAN-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; BOOLEAN-NEXT:    br label [[H]]
+; BOOLEAN:       F:
+; BOOLEAN-NEXT:    [[INNER2]] = add i32 [[INNER1]], 1
+; BOOLEAN-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[INNER2]], 20
+; BOOLEAN-NEXT:    br i1 [[CMP1]], label [[B]], label [[LOOP_EXIT_GUARD2]]
+; BOOLEAN:       G:
+; BOOLEAN-NEXT:    [[OUTER2]] = add i32 [[OUTER1]], 1
+; BOOLEAN-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[OUTER2]], 10
+; BOOLEAN-NEXT:    br i1 [[CMP2]], label [[A]], label [[LOOP_EXIT_GUARD:%.*]]
+; BOOLEAN:       H:
+; BOOLEAN-NEXT:    unreachable
+; BOOLEAN:       I:
+; BOOLEAN-NEXT:    ret void
+; BOOLEAN:       loop.exit.guard:
+; BOOLEAN-NEXT:    [[GUARD_C:%.*]] = phi i1 [ false, [[G]] ], [ [[GUARD_C_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
+; BOOLEAN-NEXT:    [[GUARD_E:%.*]] = phi i1 [ false, [[G]] ], [ [[GUARD_E_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
+; BOOLEAN-NEXT:    br i1 [[GUARD_C]], label [[C:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
+; BOOLEAN:       loop.exit.guard1:
+; BOOLEAN-NEXT:    br i1 [[GUARD_E]], label [[E:%.*]], label [[I]]
+; BOOLEAN:       loop.exit.guard2:
+; BOOLEAN-NEXT:    [[GUARD_E_MOVED]] = phi i1 [ false, [[B]] ], [ true, [[D]] ], [ undef, [[F]] ]
+; BOOLEAN-NEXT:    [[GUARD_C_MOVED]] = phi i1 [ true, [[B]] ], [ false, [[D]] ], [ undef, [[F]] ]
+; BOOLEAN-NEXT:    [[GUARD_LOOP_EXIT_GUARD:%.*]] = phi i1 [ true, [[B]] ], [ true, [[D]] ], [ false, [[F]] ]
+; BOOLEAN-NEXT:    br i1 [[GUARD_LOOP_EXIT_GUARD]], label [[LOOP_EXIT_GUARD]], label [[G]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %I
+
+A:
+  %outer1 = phi i32 [ 0, %entry ], [ %outer2, %G ]
+  br label %B
+
+B:
+  %inner1 = phi i32 [ 0, %A ], [ %inner2, %F ]
+  br i1 %PredA, label %D, label %C
+
+C:
+  tail call fastcc void @check(i32 1) #0
+  br label %H
+
+D:
+  br i1 %PredB, label %E, label %F
+
+E:
+  tail call fastcc void @check(i32 2) #0
+  br label %H
+
+F:
+  %inner2 = add i32 %inner1, 1
+  %cmp1 = icmp ult i32 %inner2, 20
+  br i1 %cmp1, label %B, label %G
+
+G:
+  %outer2 = add i32 %outer1, 1
+  %cmp2 = icmp ult i32 %outer2, 10
+  br i1 %cmp2, label %A, label %I
+
+H:
+  unreachable
+
+I:
+  ret void
+}
+
+; A loop with more exit blocks.
+
+define void @loop_five_exits(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD) {
+; CHECK-LABEL: @loop_five_exits(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[L:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[I:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; CHECK-NEXT:    br label [[J:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD]], label [[E:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[J]]
+; CHECK:       E:
+; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[LOOP_EXIT_GUARD]], label [[G:%.*]]
+; CHECK:       F:
+; CHECK-NEXT:    tail call fastcc void @check(i32 3) #[[ATTR0]]
+; CHECK-NEXT:    br label [[K:%.*]]
+; CHECK:       G:
+; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[LOOP_EXIT_GUARD]], label [[I]]
+; CHECK:       H:
+; CHECK-NEXT:    tail call fastcc void @check(i32 4) #[[ATTR0]]
+; CHECK-NEXT:    br label [[K]]
+; CHECK:       I:
+; CHECK-NEXT:    [[INC2]] = add i32 [[INC1]], 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
+; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       J:
+; CHECK-NEXT:    br label [[L]]
+; CHECK:       K:
+; CHECK-NEXT:    br label [[L]]
+; CHECK:       L:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[MERGED_BB_IDX:%.*]] = phi i32 [ 0, [[A]] ], [ 1, [[C]] ], [ 2, [[E]] ], [ 3, [[G]] ], [ 4, [[I]] ]
+; CHECK-NEXT:    [[B_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 0
+; CHECK-NEXT:    br i1 [[B_PREDICATE]], label [[B:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    [[D_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 1
+; CHECK-NEXT:    br i1 [[D_PREDICATE]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
+; CHECK:       loop.exit.guard2:
+; CHECK-NEXT:    [[F_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 2
+; CHECK-NEXT:    br i1 [[F_PREDICATE]], label [[F:%.*]], label [[LOOP_EXIT_GUARD3:%.*]]
+; CHECK:       loop.exit.guard3:
+; CHECK-NEXT:    [[H_PREDICATE:%.*]] = icmp eq i32 [[MERGED_BB_IDX]], 3
+; CHECK-NEXT:    br i1 [[H_PREDICATE]], label [[H:%.*]], label [[L]]
+;
+; BOOLEAN-LABEL: @loop_five_exits(
+; BOOLEAN-NEXT:  entry:
+; BOOLEAN-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[L:%.*]]
+; BOOLEAN:       A:
+; BOOLEAN-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[I:%.*]] ]
+; BOOLEAN-NEXT:    br i1 [[PREDA:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[C:%.*]]
+; BOOLEAN:       B:
+; BOOLEAN-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; BOOLEAN-NEXT:    br label [[J:%.*]]
+; BOOLEAN:       C:
+; BOOLEAN-NEXT:    br i1 [[PREDB:%.*]], label [[LOOP_EXIT_GUARD]], label [[E:%.*]]
+; BOOLEAN:       D:
+; BOOLEAN-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; BOOLEAN-NEXT:    br label [[J]]
+; BOOLEAN:       E:
+; BOOLEAN-NEXT:    br i1 [[PREDC:%.*]], label [[LOOP_EXIT_GUARD]], label [[G:%.*]]
+; BOOLEAN:       F:
+; BOOLEAN-NEXT:    tail call fastcc void @check(i32 3) #[[ATTR0]]
+; BOOLEAN-NEXT:    br label [[K:%.*]]
+; BOOLEAN:       G:
+; BOOLEAN-NEXT:    br i1 [[PREDD:%.*]], label [[LOOP_EXIT_GUARD]], label [[I]]
+; BOOLEAN:       H:
+; BOOLEAN-NEXT:    tail call fastcc void @check(i32 4) #[[ATTR0]]
+; BOOLEAN-NEXT:    br label [[K]]
+; BOOLEAN:       I:
+; BOOLEAN-NEXT:    [[INC2]] = add i32 [[INC1]], 1
+; BOOLEAN-NEXT:    [[CMP:%.*]] = icmp ult i32 [[INC2]], 10
+; BOOLEAN-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; BOOLEAN:       J:
+; BOOLEAN-NEXT:    br label [[L]]
+; BOOLEAN:       K:
+; BOOLEAN-NEXT:    br label [[L]]
+; BOOLEAN:       L:
+; BOOLEAN-NEXT:    ret void
+; BOOLEAN:       loop.exit.guard:
+; BOOLEAN-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ], [ false, [[E]] ], [ false, [[G]] ], [ false, [[I]] ]
+; BOOLEAN-NEXT:    [[GUARD_D:%.*]] = phi i1 [ false, [[A]] ], [ true, [[C]] ], [ false, [[E]] ], [ false, [[G]] ], [ false, [[I]] ]
+; BOOLEAN-NEXT:    [[GUARD_F:%.*]] = phi i1 [ false, [[A]] ], [ false, [[C]] ], [ true, [[E]] ], [ false, [[G]] ], [ false, [[I]] ]
+; BOOLEAN-NEXT:    [[GUARD_H:%.*]] = phi i1 [ false, [[A]] ], [ false, [[C]] ], [ false, [[E]] ], [ true, [[G]] ], [ false, [[I]] ]
+; BOOLEAN-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
+; BOOLEAN:       loop.exit.guard1:
+; BOOLEAN-NEXT:    br i1 [[GUARD_D]], label [[D:%.*]], label [[LOOP_EXIT_GUARD2:%.*]]
+; BOOLEAN:       loop.exit.guard2:
+; BOOLEAN-NEXT:    br i1 [[GUARD_F]], label [[F:%.*]], label [[LOOP_EXIT_GUARD3:%.*]]
+; BOOLEAN:       loop.exit.guard3:
+; BOOLEAN-NEXT:    br i1 [[GUARD_H]], label [[H:%.*]], label [[L]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %L
+
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %I ]
+  br i1 %PredA, label %B, label %C
+
+B:
+  tail call fastcc void @check(i32 1) #0
+  br label %J
+
+C:
+  br i1 %PredB, label %D, label %E
+
+D:
+  tail call fastcc void @check(i32 2) #0
+  br label %J
+
+E:
+  br i1 %PredC, label %F, label %G
+
+F:
+  tail call fastcc void @check(i32 3) #0
+  br label %K
+
+G:
+  br i1 %PredD, label %H, label %I
+
+H:
+  tail call fastcc void @check(i32 4) #0
+  br label %K
+
+I:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %L
+
+J:
+  br label %L
+
+K:
+  br label %L
+
+L:
+  ret void
+}
+
+
+declare void @check(i32 noundef %i) #0
+
+attributes #0 = { noreturn nounwind }
+

llvm/test/Transforms/UnifyLoopExits/nested.ll

 ; CHECK:       A5:
 ; CHECK-NEXT:    br i1 [[PREDA3:%.*]], label [[LOOP_EXIT_GUARD]], label [[A1]]
 ; CHECK:       C:
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[EXIT_PHI:%.*]] = phi i32 [ [[Z:%.*]], [[C:%.*]] ], [ [[EXIT_PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
 ; CHECK-NEXT:    ret void
 ; CHECK:       loop.exit.guard:
-; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[A4]] ], [ false, [[A5]] ]
 ; CHECK-NEXT:    [[EXIT_PHI_MOVED]] = phi i32 [ undef, [[A4]] ], [ [[A4_PHI]], [[A5]] ]
+; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[A4]] ], [ false, [[A5]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[EXIT]]
 ; CHECK:       loop.exit.guard1:
-; CHECK-NEXT:    [[GUARD_A3:%.*]] = phi i1 [ true, [[B3]] ], [ false, [[B4]] ]
 ; CHECK-NEXT:    [[X_INC_MOVED]] = phi i32 [ [[X_INC]], [[B3]] ], [ [[X_INC]], [[B4]] ]
+; CHECK-NEXT:    [[GUARD_A3:%.*]] = phi i1 [ true, [[B3]] ], [ false, [[B4]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_A3]], label [[A3]], label [[A2]]
 ;
 entry:
   br label %A1
 
 A1:
   br label %B1
 

llvm/test/Transforms/UnifyLoopExits/restore-ssa.ll

 ; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
 ; CHECK:       C:
 ; CHECK-NEXT:    [[INC:%.*]] = add i32 [[MYTMP41_MOVED:%.*]], 1
 ; CHECK-NEXT:    br label [[RETURN:%.*]]
 ; CHECK:       return:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[INC]], [[C:%.*]] ], [ [[PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
 ; CHECK-NEXT:    ret i32 [[PHI]]
 ; CHECK:       loop.exit.guard:
-; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[B]] ]
-; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP42]], [[A]] ], [ undef, [[B]] ]
 ; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[B]] ]
+; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP42]], [[A]] ], [ undef, [[B]] ]
+; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[B]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[C]]
 ;
 entry:
   br label %A
 
 A:
   %mytmp42 = load i32, i32* %arg1, align 4
   %cmp1 = icmp slt i32 %mytmp42, 0

 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
 ; CHECK:       D:
 ; CHECK-NEXT:    [[INC:%.*]] = add i32 [[MYTMP41_MOVED:%.*]], 1
 ; CHECK-NEXT:    br label [[RETURN:%.*]]
 ; CHECK:       return:
 ; CHECK-NEXT:    ret i32 0
 ; CHECK:       loop.exit.guard:
-; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
 ; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
+; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[D:%.*]]
 ;
 entry:
   %mytmp42 = load i32, i32* %arg1, align 4
   br label %A
 
 A:
   %cmp1 = icmp slt i32 %mytmp42, 0

 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
 ; CHECK:       D:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[MYTMP41_MOVED:%.*]], [[D:%.*]] ], [ [[MYTMP42]], [[ENTRY:%.*]] ], [ [[PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
 ; CHECK-NEXT:    ret i32 [[PHI]]
 ; CHECK:       loop.exit.guard:
-; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
-; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP43]], [[A]] ], [ undef, [[C]] ]
 ; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
+; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP43]], [[A]] ], [ undef, [[C]] ]
+; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[D]]
 ;
 entry:
   %mytmp42 = load i32, i32* %arg1, align 4
   %cmp2 = icmp slt i32 %mytmp42, 0
   br i1 %cmp2, label %A, label %return
 
 A:

 ; CHECK:       D:
 ; CHECK-NEXT:    br label [[RETURN:%.*]]
 ; CHECK:       E:
 ; CHECK-NEXT:    br label [[RETURN]]
 ; CHECK:       return:
 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[MYTMP41_MOVED:%.*]], [[D:%.*]] ], [ [[MYTMP42]], [[E:%.*]] ]
 ; CHECK-NEXT:    ret i32 [[PHI]]
 ; CHECK:       loop.exit.guard:
-; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
 ; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
+; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
 ; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E]], label [[D]]
 ;
 entry:
   %mytmp42 = load i32, i32* %arg1, align 4
   br label %A
 
 A:
   %cmp1 = icmp slt i32 %mytmp42, 0