[UnifyLoopExits] Reduce number of guard blocks

[bcahoon]

Summary

UnifyLoopExits creates a single exit, a control flow hub, for
loops with multiple exits. There is an input to the block for
each loop exiting block and and output from the block for each
loop exit block. Multiple checks, or guard blocks, are needed
to branch to the correct exit block.

For large loops with lots of exit blocks, all the extra guard
blocks cause problems for StructurizeCFG and subsequent passes.
This patch reduces the number of guard blocks needed when the
exit blocks branch to a common block (e.g., an unreachable
block). The guard blocks are reduced by changing the inputs
and outputs of the control flow hub. The inputs are the exit
blocks and the outputs are the common block.

Reducing the guard blocks enables StructurizeCFG to reorder the
basic blocks in the CFG to reduce the values that exit a loop
with multiple exits. This reduces the compile-time of
StructurizeCFG and also reduces register pressure.

[sameerds]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

163–164

This can be rewritten as "if (auto *Succ = ...) "

184

Can you rephrase a bit? The join blocks are for what?

217

What does this do? We haven't done any updates yet, right?

227

Is it true that an exit block always has a single predecessor? This will return nullptr otherwise. Maybe a comment will help.

234–241

Scary stuff. Could you please add a comment? I think this is related to the test "unreachable_from_inner_loop" ... but an explanation in English will help a lot.

[bcahoon]

Changes based upon review comments.

[bcahoon]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

217

Thanks for catching this.

227

Great point. I've added a check when CommonSuccs is created that checks for a single predecessor. It's the common case to try to optimize, along with the changes needed to StructurzeCFG. It's possible to allow multiple predecessors though that could complicate the node ordering changes in StructurizeCFG.

234–241

Agreed. Please let me know if this requires additional clarification.

[sameerds]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

234–241

I am able to follow the test unreachable_from_inner_loop, but not seeing how the part about "if (PredLoop) remove pred" works. In the test, { B D F} is an inner loop, inside { A B D F G} and two guards are generated. But neither guard causes a node to move from a non-child loop to ParentLoop.

[bcahoon]

Added a test to show the case when we need to move the guard block predecessor from an outer loop to an inner loop. Three nested loops are needed for this. Initially, the guard block predecessor is added to the outer loop, but then need to change to the middle loop.

[bcahoon]

Messed up the last revision by including another patch. This hopefully fixes it. The only new change is an additional test case, three_loops, added to test/Transforms/UnifyLoopExits/reduce_guards.ll

[bcahoon]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

234–241

I've added a test case to show this condition. It requires at least 3 nested loops. A guard block predecessor is moved from the outermost loop to the middle loop.

[critson]

Unfortunately this can breaks reconvergence in some edge cases.
This occurs because exits in an inner loop may end up no longer reconvergencing with exits in an outer loop.
I am trying to clean up on a test case based on a Vulkan CTS test failure this causes.

I believe the solution is to test that all predecessors of the common successor are members of the set of exits.
If not then it indicates the common successor is part of a reconvergence structure shared by inner and outer loop exits and this optimization cannot be used.

e.g.

for (auto CS : CommonSuccs) {
    // ...

    if (!llvm::all_of(predecessors(CB), [Exits](auto Pred) {return Exits.contains(Pred);}))
      continue;
    
    // ...
  }

[bcahoon]

Hi @critson, thanks for pointing out the issue, and a potential fix. I'm looking at it now.

[critson]

@bcahoon Thanks! I have attached what I think is a semi-representative test for the issue.

In the test Exit2, Exit3 and Exit4 should all reconverged at the TrueExit.
However with this change Exit3 and Exit4 are reconverged with C, prior to control transfer to TrueExit or Loop2.preheader.
Again this test has been heavily cut down from an actual shader, and has lost some nuance in the process, so let me know if you want the original.

reduce-guards-maintain-reconvergence.ll1 KBDownload

[bcahoon]

Hi @critson. Thanks for reducing the test case. I don't see an error with the test case though, so I may be missing something. Or, perhaps I need to see the complete test case? Here's my understanding. With the patch, control flow still converges at TrueExit. It's just that the Exit3 and Exit4 blocks have moved in the CFG so that they appear prior to loop.exit.guard rather than after. Following the exit paths from F, G, and C. I think that should be ok?

Before patch:
F -> loop.exit.guard ->loop.exit.guard1 -> Exit3 -> TrueExit
G -> loop.exit.guard -> loop.exit.guard1 -> Exit4 -> TrueExit
C -> loop.exit.guard -> Loop2.preheader -> Loop2 -> Exit2 -> TrueExit

After patch:
F -> Exit3 -> loop.exit.guard -> TrueExit
G -> Exit4 -> loop.exit.guard => TrueExit
C -> loop.exit.guard -> Loop2 -> Exit2 -> TrueExit

The CFG structure (hopefully the formatting works)
Before patch:

              C   F   G
              \   |   /
          loop.exit.guard
            /         \  
Loop2PH/Loop2   loop.exit.guard1
     |               /      \
     \             Exit3 Exit4
      Exit2       /     /
           \     |     /
             TrueExit

After patch:

              F    G
              |    |
      C    Exit3 Exit4
        \     |     |
       loop.exit.guard
          /      \
Loop2PH/Loop2    |
          |      |
       Exit2     /
           \    /
          TrueExit

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

 static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
   // To unify the loop exits, we need a list of the exiting blocks as
   // well as exit blocks. The functions for locating these lists both
   // traverse the entire loop body. It is more efficient to first
   // locate the exiting blocks and then examine their successors to
   // locate the exit blocks.
   SetVector<BasicBlock *> ExitingBlocks;
   SetVector<BasicBlock *> Exits;
+  // Record the exit blocks that branch to the same block.
+  MapVector<BasicBlock *, SetVector<BasicBlock *> > CommonSuccs;
 
   // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
   SmallVector<BasicBlock *, 8> Temp;
   L->getExitingBlocks(Temp);
   for (auto BB : Temp) {
     ExitingBlocks.insert(BB);
     for (auto S : successors(BB)) {
       auto SL = LI.getLoopFor(S);
       // A successor is not an exit if it is directly or indirectly in the
       // current loop.
       if (SL == L || L->contains(SL))
         continue;
       Exits.insert(S);
+      // The typical case for reducing the number of guard blocks occurs when
+      // the exit block has a single predecessor and successor.
+      if (S->getSinglePredecessor())
+        if (auto *Succ = S->getSingleSuccessor())
+          CommonSuccs[Succ].insert(S);
     }
   }
 
   LLVM_DEBUG(
       dbgs() << "Found exit blocks:";
       for (auto Exit : Exits) {
         dbgs() << " " << Exit->getName();
       }
       dbgs() << "\n";
 
       dbgs() << "Found exiting blocks:";
       for (auto EB : ExitingBlocks) {
         dbgs() << " " << EB->getName();
       }
-      dbgs() << "\n";);
+      dbgs() << "\n";
+
+      dbgs() << "Exit blocks with a common successor:\n";
+      for (auto CS : CommonSuccs) {
+        dbgs() << "  Succ " << CS.first->getName() << ", exits:";
+        for (auto Exit : CS.second)
+          dbgs() << " " << Exit->getName();
+        dbgs() << "\n";
+      });
 
   if (Exits.size() <= 1) {
     LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
     return false;
   }
 
+  // When multiple exit blocks branch to the same block, change the control
+  // flow hub to after the exit blocks rather than before. This reduces the
+  // number of guard blocks needed after the loop.
+  for (auto CS : CommonSuccs) {
+    auto CB = CS.first;
+    auto Preds = CS.second;
+    if (Exits.contains(CB))
+      continue;
+    if (Preds.size() < 2 || Preds.size() == Exits.size())
+      continue;
+    for (auto Exit : Preds) {
+      Exits.remove(Exit);
+      ExitingBlocks.remove(Exit->getSinglePredecessor());
+      ExitingBlocks.insert(Exit);
+    }
+    Exits.insert(CB);
+  }
+
   SmallVector<BasicBlock *, 8> GuardBlocks;
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   auto LoopExitBlock = CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks,
                                             Exits, "loop.exit");
 
   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
   L->verifyLoop();
 
   // The guard blocks were created outside the loop, so they need to become
   // members of the parent loop.
   if (auto ParentLoop = L->getParentLoop()) {
     for (auto G : GuardBlocks) {
       ParentLoop->addBasicBlockToLoop(G, LI);
+      // Ensure the guard block predecessors are in a valid loop. After the
+      // change to the control flow hub for common successors, a guard block
+      // predecessor may not be in a loop or may be in an outer loop.
+      for (auto Pred : predecessors(G)) {
+        auto PredLoop = LI.getLoopFor(Pred);
+        if (!ParentLoop->contains(PredLoop)) {
+          if (PredLoop)
+            LI.removeBlock(Pred);
+          ParentLoop->addBasicBlockToLoop(Pred, LI);
+        }
+      }
     }
     ParentLoop->verifyLoop();
   }
 
 #if defined(EXPENSIVE_CHECKS)
   LI.verify(DT);
 #endif // EXPENSIVE_CHECKS
 

llvm/test/Transforms/UnifyLoopExits/reduce_guards.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -unify-loop-exits -enable-new-pm=0 -S | FileCheck %s
+; RUN: opt < %s -passes=unify-loop-exits -S | FileCheck %s
+
+; A loop has exit blocks, B and D, that branch to the same successor.
+; We reduce the number of guard blocks needed by creating the loop
+; exit guard block after B and D rather than before B and D.
+
+define void @unreachable_from_loop(i1 %PredEntry, i1 %PredA, i1 %PredB) {
+; CHECK-LABEL: @unreachable_from_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[E:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[C:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[D:%.*]], label [[E]]
+; CHECK:       D:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
+; CHECK:       E:
+; 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:       F:
+; CHECK-NEXT:    unreachable
+; CHECK:       G:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_G:%.*]] = phi i1 [ true, [[E]] ], [ false, [[B]] ], [ false, [[D]] ]
+; CHECK-NEXT:    br i1 [[GUARD_G]], label [[G]], label [[F:%.*]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %G
+
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %E ]
+  br i1 %PredA, label %B, label %C
+
+B:
+  tail call fastcc void @check(i32 1) #0
+  br label %F
+
+C:
+  br i1 %PredB, label %D, label %E
+
+D:
+  tail call fastcc void @check(i32 2) #0
+  br label %F
+
+E:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %G
+
+F:
+  unreachable
+
+G:
+  ret void
+}
+
+; A test when the loop exit blocks appear in an inner loop.
+
+define void @unreachable_from_inner_loop(i1 %PredEntry, i1 %PredA, i1 %PredB) {
+; CHECK-LABEL: @unreachable_from_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 [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[E:%.*]], label [[F]]
+; CHECK:       E:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD1]]
+; 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_GUARD1]]
+; 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:    [[GUARD_I:%.*]] = phi i1 [ true, [[G]] ], [ [[GUARD_I_MOVED:%.*]], [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    br i1 [[GUARD_I]], label [[I]], label [[H:%.*]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    [[GUARD_G:%.*]] = phi i1 [ true, [[F]] ], [ false, [[C]] ], [ false, [[E]] ]
+; CHECK-NEXT:    [[GUARD_I_MOVED]] = phi i1 [ undef, [[F]] ], [ false, [[C]] ], [ false, [[E]] ]
+; CHECK-NEXT:    br i1 [[GUARD_G]], label [[G]], label [[LOOP_EXIT_GUARD]]
+;
+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
+}
+
+; Test with 3 nested loops to show the case when we need to change the loop for
+; the predecessors of the loop guard. Since UnifyLoopExits works from the outer
+; loop to the inner loop, the predecessors are added to the outermost loop.
+; When a guard block is added to the exit of the inner loop, the predecessor
+; block loops need to change to the middle loop.
+
+define void @three_loops(i1 %PredEntry, i1 %PredA, i1 %PredB) {
+; CHECK-LABEL: @three_loops(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[L1:%.*]], label [[H:%.*]]
+; CHECK:       L1:
+; CHECK-NEXT:    [[I1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[I2:%.*]], [[F:%.*]] ]
+; CHECK-NEXT:    br label [[L2:%.*]]
+; CHECK:       L2:
+; CHECK-NEXT:    [[J1:%.*]] = phi i32 [ 0, [[L1]] ], [ [[J2:%.*]], [[E:%.*]] ]
+; CHECK-NEXT:    br label [[L3:%.*]]
+; CHECK:       L3:
+; CHECK-NEXT:    [[K1:%.*]] = phi i32 [ 0, [[L2]] ], [ [[K2:%.*]], [[D:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD2:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[C:%.*]], label [[D]]
+; CHECK:       C:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD2]]
+; CHECK:       D:
+; CHECK-NEXT:    [[K2]] = add i32 [[K1]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp ult i32 [[K2]], 20
+; CHECK-NEXT:    br i1 [[CMP1]], label [[L3]], label [[LOOP_EXIT_GUARD2]]
+; CHECK:       E:
+; CHECK-NEXT:    [[J2]] = add i32 [[J1]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp ult i32 [[J2]], 10
+; CHECK-NEXT:    br i1 [[CMP2]], label [[L2]], label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       F:
+; CHECK-NEXT:    [[I2]] = add i32 [[I1]], 1
+; CHECK-NEXT:    [[CMP3:%.*]] = icmp ult i32 [[I2]], 5
+; CHECK-NEXT:    br i1 [[CMP3]], label [[L1]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       G:
+; CHECK-NEXT:    unreachable
+; CHECK:       H:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_H:%.*]] = phi i1 [ true, [[F]] ], [ [[GUARD_H_MOVED:%.*]], [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    br i1 [[GUARD_H]], label [[H]], label [[G:%.*]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    [[GUARD_F:%.*]] = phi i1 [ true, [[E]] ], [ [[GUARD_F_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
+; CHECK-NEXT:    [[GUARD_H_MOVED]] = phi i1 [ undef, [[E]] ], [ [[GUARD_H_MOVED_MOVED:%.*]], [[LOOP_EXIT_GUARD2]] ]
+; CHECK-NEXT:    br i1 [[GUARD_F]], label [[F]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       loop.exit.guard2:
+; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[D]] ], [ false, [[A]] ], [ false, [[C]] ]
+; CHECK-NEXT:    [[GUARD_F_MOVED]] = phi i1 [ undef, [[D]] ], [ false, [[A]] ], [ false, [[C]] ]
+; CHECK-NEXT:    [[GUARD_H_MOVED_MOVED]] = phi i1 [ undef, [[D]] ], [ false, [[A]] ], [ false, [[C]] ]
+; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E]], label [[LOOP_EXIT_GUARD1]]
+;
+entry:
+  br i1 %PredEntry, label %L1, label %H
+
+L1:
+  %i1 = phi i32 [ 0, %entry ], [ %i2, %F ]
+  br label %L2
+
+L2:
+  %j1 = phi i32 [ 0, %L1 ], [ %j2, %E ]
+  br label %L3
+
+L3:
+  %k1 = phi i32 [ 0, %L2 ], [ %k2, %D ]
+  br i1 %PredA, label %A, label %B
+
+A:
+  tail call fastcc void @check(i32 1) #0
+  br label %G
+
+B:
+  br i1 %PredB, label %C, label %D
+
+C:
+  tail call fastcc void @check(i32 2) #0
+  br label %G
+
+D:
+  %k2 = add i32 %k1, 1
+  %cmp1 = icmp ult i32 %k2, 20
+  br i1 %cmp1, label %L3, label %E
+
+E:
+  %j2 = add i32 %j1, 1
+  %cmp2 = icmp ult i32 %j2, 10
+  br i1 %cmp2, label %L2, label %F
+
+F:
+  %i2 = add i32 %i1, 1
+  %cmp3 = icmp ult i32 %i2, 5
+  br i1 %cmp3, label %L1, label %H
+
+G:
+  unreachable
+
+H:
+  ret void
+}
+
+
+; The common successor does not have to be an unreachable block.
+
+define void @common_exit(i1 %PredEntry, i1 %PredA, i1 %PredB) {
+; CHECK-LABEL: @common_exit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[E:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[C:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check1(i32 1) #[[ATTR1:[0-9]+]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[D:%.*]], label [[E]]
+; CHECK:       D:
+; CHECK-NEXT:    tail call fastcc void @check1(i32 2) #[[ATTR1]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
+; CHECK:       E:
+; 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:       F:
+; CHECK-NEXT:    br label [[G]]
+; CHECK:       G:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_G:%.*]] = phi i1 [ true, [[E]] ], [ false, [[B]] ], [ false, [[D]] ]
+; CHECK-NEXT:    br i1 [[GUARD_G]], label [[G]], label [[F:%.*]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %G
+
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %E ]
+  br i1 %PredA, label %B, label %C
+
+B:
+  tail call fastcc void @check1(i32 1) #1
+  br label %F
+
+C:
+  br i1 %PredB, label %D, label %E
+
+D:
+  tail call fastcc void @check1(i32 2) #1
+  br label %F
+
+E:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %G
+
+F:
+  br label %G
+
+G:
+  ret void
+}
+
+; A test with multiple common exits.
+
+define void @multiple_common_successors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD) {
+; CHECK-LABEL: @multiple_common_successors(
+; 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 [[B:%.*]], label [[C:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    tail call fastcc void @check(i32 1) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[D:%.*]], label [[E:%.*]]
+; CHECK:       D:
+; CHECK-NEXT:    tail call fastcc void @check(i32 2) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
+; CHECK:       E:
+; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[F:%.*]], label [[G:%.*]]
+; CHECK:       F:
+; CHECK-NEXT:    tail call fastcc void @check(i32 3) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
+; CHECK:       G:
+; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[H:%.*]], label [[I]]
+; CHECK:       H:
+; CHECK-NEXT:    tail call fastcc void @check(i32 4) #[[ATTR0]]
+; CHECK-NEXT:    br label [[LOOP_EXIT_GUARD]]
+; 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:    [[GUARD_L:%.*]] = phi i1 [ true, [[I]] ], [ false, [[B]] ], [ false, [[D]] ], [ false, [[F]] ], [ false, [[H]] ]
+; CHECK-NEXT:    [[GUARD_J:%.*]] = phi i1 [ false, [[I]] ], [ true, [[B]] ], [ true, [[D]] ], [ false, [[F]] ], [ false, [[H]] ]
+; CHECK-NEXT:    br i1 [[GUARD_L]], label [[L]], label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br i1 [[GUARD_J]], label [[J:%.*]], label [[K:%.*]]
+;
+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
+}
+
+; Test when the loop exit block is tha same as a common successor
+; block. The number of guard blocks is unchanged.
+
+define void @common_successor_exit(i1 %PredEntry, i1 %PredA, i1 %PredB) {
+; CHECK-LABEL: @common_successor_exit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[INC1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC2:%.*]], [[E:%.*]] ]
+; 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 [[G]]
+; 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 [[G]]
+; CHECK:       E:
+; 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:       G:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_B:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ], [ false, [[E]] ]
+; CHECK-NEXT:    [[GUARD_D:%.*]] = phi i1 [ false, [[A]] ], [ true, [[C]] ], [ false, [[E]] ]
+; CHECK-NEXT:    br i1 [[GUARD_B]], label [[B:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br i1 [[GUARD_D]], label [[D:%.*]], label [[G]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %G
+
+A:
+  %inc1 = phi i32 [ 0, %entry ], [ %inc2, %E ]
+  br i1 %PredA, label %B, label %C
+
+B:
+  tail call fastcc void @check(i32 1) #0
+  br label %G
+
+C:
+  br i1 %PredB, label %D, label %E
+
+D:
+  tail call fastcc void @check(i32 2) #0
+  br label %G
+
+E:
+  %inc2 = add i32 %inc1, 1
+  %cmp = icmp ult i32 %inc2, 10
+  br i1 %cmp, label %A, label %G
+
+G:
+  ret void
+}
+
+declare void @check(i32 noundef %i) #0
+declare void @check1(i32 noundef %i) #1
+
+attributes #0 = { noreturn nounwind }
+attributes #1 = { nounwind }
+