StructurizeCFG: Set Undef for non-predecessors in setPhiValues()

[ruiling]

Summary

During structurization process, we may place non-predecessor blocks
between the predecessors of a block in the structurized CFG. Take
the typical while-break case as an example:

/---A (v = ...)
|  / \
^ B   C
|  \ /|
\---L |
    \ /
     E (r = phi (v:C)...)

After structurization, the CFG would be look like:

/---A
|   |\
|   | C
|   |/
|   F1
^   |\
|   | B
|   |/
|   F2
|   |\
|   | L
\   |/
 \--F3
    |
    E

We can see that block B is placed between the predecessors(C/L) of E.
During phi reconstruction, to achieve the same sematics as before, we
are reconstructing the PHIs as:

F1: v1 = phi (v:C), (undef:A)
F3: r = phi (v1:F2), ...

But this is also saying that v1 would be live through B, which is not
quite necessary. The idea in the change is to say the incoming value
from B is Undef for the PHI in E. With this change, the reconstructed
PHI would be:

F1: v1 = phi (v:C), (undef:A)
F2: v2 = phi (v1:F1), (undef:B)
F3: r  = phi (v2:F2), ...

[foad]

I haven't read the patch carefully, but the description makes a lot of sense to me.

[sameerds]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

687–689

This is the core idea. But it's not obvious how the code implements this. Would be good to have an explanation of the Stack and the Incomings set. For example, why do we need to erase Current from Incomings? Somewhere in the traversal, the Stack seems to ensure that undefs are added to phis at intermediate Flow blocks ... needs explanation of why it always works.

[sameerds]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

688

On second thoughts, "this block" contributes an undefined value. That's the whole point of this change, right?

[ruiling]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

687–689

Sorry I don't quite get your point. The reason we need to erase Current from I

688

Yes, the core idea is the block existing before structurization but not the predecessor block does not contribute any value even after structurization. I am thinking about whether I can refine the code to be less confusing.

[ruiling]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

687–689

The reason I was erasing Current from Incomings is to try to terminate the traversal loop after finishing all the incoming predecessors. But now I think this maybe not quite necessary. The Stack is just used as traversal stack, no other meaning.

[sameerds]

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

687–689

What I mean is that the code needs comments explaining how it achieves the goal. There is a stack, so some form of DFS is happening. But it will be good to have an explanation (in the source file itself, and not this review) of why the implementation is correct. This is for future reference. It is not enough to expect that anyone reading the code will "eventually" figure out how it is all working.

[ruiling]

refine the code and add some comment.

[fhahn]

Should this use poison instead of undef?

[ruiling]

In D132450#3748269, @fhahn wrote:

Should this use poison instead of undef?

If I understand Poison correctly, Poison should work the same as Undef when they are used as incoming value to PHI, right? If so, changing to poison should work, but that should be in a separate change.

[ruiling]

any further comment?

[sameerds]

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

59–61

When the value reaching along a predecessor is a constant literal, do we still need to create the extra PHI in the earlier Flow blocks? In this case, it seems the true/false values are pushed to the predecessor block Flow10. Can this be bad for performance in some case? We can skip it by checking for constants when we add predecessors to the stack.

[ruiling]

Update to help better phi insertion

[ruiling]

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

59–61

I am not sure whether this would regress quality of generated code, but I happened to get an idea to fix the issue. Please check whether this sounds good to you. The backward traversal is done once per basic block. So I have postponed the constant check.

[ruiling]

rebase

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

 //===- StructurizeCFG.cpp -------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/StructurizeCFG.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
class StructurizeCFG {
   Function *Func;
   Region *ParentRegion;
 
   LegacyDivergenceAnalysis *DA = nullptr;
   DominatorTree *DT;
 
   SmallVector<RegionNode *, 8> Order;
   BBSet Visited;
+  BBSet FlowSet;
 
   SmallVector<WeakVH, 8> AffectedPhis;
   BBPhiMap DeletedPhis;
   BB2BBVecMap AddedPhis;
 
   PredMap Predicates;
   BranchVector Conditions;
 
void StructurizeCFG::setPhiValues() {
   SSAUpdater Updater(&InsertedPhis);
   for (const auto &AddedPhi : AddedPhis) {
     BasicBlock *To = AddedPhi.first;
     const BBVector &From = AddedPhi.second;
 
     if (!DeletedPhis.count(To))
       continue;
 
+    SmallVector<BasicBlock *> UndefBlks;
+    bool CachedUndefs = false;
     PhiMap &Map = DeletedPhis[To];
     for (const auto &PI : Map) {
       PHINode *Phi = PI.first;
       Value *Undef = UndefValue::get(Phi->getType());
       Updater.Initialize(Phi->getType(), "");
       Updater.AddAvailableValue(&Func->getEntryBlock(), Undef);
       Updater.AddAvailableValue(To, Undef);
 
-      NearestCommonDominator Dominator(DT);
-      Dominator.addBlock(To);
+      SmallSet<BasicBlock *, 8> Incomings;
       for (const auto &VI : PI.second) {
+        Incomings.insert(VI.first);
         Updater.AddAvailableValue(VI.first, VI.second);
-        Dominator.addAndRememberBlock(VI.first);
       }
 
-      if (!Dominator.resultIsRememberedBlock())
-        Updater.AddAvailableValue(Dominator.result(), Undef);
+      if (!CachedUndefs) {
+        // Build the undef blocks cache.
+        SmallSet<BasicBlock *, 8> VisitedBlock;
+        SmallVector<BasicBlock *, 8> Stack;
+        if (To == ParentRegion->getExit()) {
+          for (auto P : predecessors(To)) {
+            if (ParentRegion->contains(P))
+              Stack.push_back(P);
+          }
+        } else {
+          append_range(Stack, predecessors(To));
+        }
+
+        // Do a backward traversal over the CFG, and stop further searching if
+        // the block is not a Flow. If a block is neither flow block nor the
+        // incoming predecessor, then the incoming value from the block is
+        // undefined value for the PHI being reconstructed.
+        while (!Stack.empty()) {
+          BasicBlock *Current = Stack.pop_back_val();
+          if (VisitedBlock.contains(Current))
+            continue;
+
+          VisitedBlock.insert(Current);
+          if (FlowSet.contains(Current)) {
+            for (auto P : predecessors(Current))
+              Stack.push_back(P);
+          } else if (!Incomings.contains(Current)) {
+            UndefBlks.push_back(Current);
+          }
+        }
+        CachedUndefs = true;
+      }
+
+      for (auto UB : UndefBlks)
+        Updater.AddAvailableValue(UB, Undef);
 
       for (BasicBlock *FI : From)
         Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI));
       AffectedPhis.push_back(Phi);
     }
 
     DeletedPhis.erase(To);
   }

 
 /// Create a new flow node and update dominator tree and region info
 BasicBlock *StructurizeCFG::getNextFlow(BasicBlock *Dominator) {
   LLVMContext &Context = Func->getContext();
   BasicBlock *Insert = Order.empty() ? ParentRegion->getExit() :
                        Order.back()->getEntry();
   BasicBlock *Flow = BasicBlock::Create(Context, FlowBlockName,
                                         Func, Insert);
+  FlowSet.insert(Flow);
   DT->addNewBlock(Flow, Dominator);
   ParentRegion->getRegionInfo()->setRegionFor(Flow, ParentRegion);
   return Flow;
 }
 
 /// Create a new or reuse the previous node as flow node
 BasicBlock *StructurizeCFG::needPrefix(bool NeedEmpty) {
   BasicBlock *Entry = PrevNode->getEntry();
bool StructurizeCFG::run(Region *R, DominatorTree *DT) {
   Visited.clear();
   DeletedPhis.clear();
   AddedPhis.clear();
   Predicates.clear();
   Conditions.clear();
   Loops.clear();
   LoopPreds.clear();
   LoopConds.clear();
+  FlowSet.clear();
 
   return true;
 }
 
 Pass *llvm::createStructurizeCFGPass(bool SkipUniformRegions) {
   return new StructurizeCFGLegacyPass(SkipUniformRegions);
 }
 

llvm/test/CodeGen/AMDGPU/multilevel-break.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -mtriple=amdgcn-- -structurizecfg -si-annotate-control-flow < %s | FileCheck -check-prefix=OPT %s
 ; RUN: llc -march=amdgcn -verify-machineinstrs < %s | FileCheck -check-prefix=GCN %s
 
 ; Ensure two if.break calls, for both the inner and outer loops
 ; FIXME: duplicate comparison
 define amdgpu_vs void @multi_else_break(<4 x float> %vec, i32 %ub, i32 %cont) {
 ; OPT-LABEL: @multi_else_break(
 ; OPT-NEXT:  main_body:
 ; OPT-NEXT:    br label [[LOOP_OUTER:%.*]]
 ; OPT:       LOOP.outer:
-; OPT-NEXT:    [[PHI_BROKEN2:%.*]] = phi i64 [ [[TMP10:%.*]], [[FLOW1:%.*]] ], [ 0, [[MAIN_BODY:%.*]] ]
-; OPT-NEXT:    [[TMP43:%.*]] = phi i32 [ 0, [[MAIN_BODY]] ], [ [[TMP4:%.*]], [[FLOW1]] ]
+; OPT-NEXT:    [[PHI_BROKEN2:%.*]] = phi i64 [ [[TMP8:%.*]], [[FLOW1:%.*]] ], [ 0, [[MAIN_BODY:%.*]] ]
+; OPT-NEXT:    [[TMP43:%.*]] = phi i32 [ 0, [[MAIN_BODY]] ], [ [[TMP3:%.*]], [[FLOW1]] ]
 ; OPT-NEXT:    br label [[LOOP:%.*]]
 ; OPT:       LOOP:
-; OPT-NEXT:    [[PHI_BROKEN:%.*]] = phi i64 [ [[TMP8:%.*]], [[FLOW:%.*]] ], [ 0, [[LOOP_OUTER]] ]
-; OPT-NEXT:    [[TMP0:%.*]] = phi i32 [ undef, [[LOOP_OUTER]] ], [ [[TMP4]], [[FLOW]] ]
-; OPT-NEXT:    [[TMP45:%.*]] = phi i32 [ [[TMP43]], [[LOOP_OUTER]] ], [ [[TMP5:%.*]], [[FLOW]] ]
+; OPT-NEXT:    [[PHI_BROKEN:%.*]] = phi i64 [ [[TMP6:%.*]], [[FLOW:%.*]] ], [ 0, [[LOOP_OUTER]] ]
+; OPT-NEXT:    [[TMP45:%.*]] = phi i32 [ [[TMP43]], [[LOOP_OUTER]] ], [ [[TMP3]], [[FLOW]] ]
 ; OPT-NEXT:    [[TMP48:%.*]] = icmp slt i32 [[TMP45]], [[UB:%.*]]
-; OPT-NEXT:    [[TMP1:%.*]] = call { i1, i64 } @llvm.amdgcn.if.i64(i1 [[TMP48]])
-; OPT-NEXT:    [[TMP2:%.*]] = extractvalue { i1, i64 } [[TMP1]], 0
-; OPT-NEXT:    [[TMP3:%.*]] = extractvalue { i1, i64 } [[TMP1]], 1
-; OPT-NEXT:    br i1 [[TMP2]], label [[ENDIF:%.*]], label [[FLOW]]
+; OPT-NEXT:    [[TMP0:%.*]] = call { i1, i64 } @llvm.amdgcn.if.i64(i1 [[TMP48]])
+; OPT-NEXT:    [[TMP1:%.*]] = extractvalue { i1, i64 } [[TMP0]], 0
+; OPT-NEXT:    [[TMP2:%.*]] = extractvalue { i1, i64 } [[TMP0]], 1
+; OPT-NEXT:    br i1 [[TMP1]], label [[ENDIF:%.*]], label [[FLOW]]
 ; OPT:       Flow:
-; OPT-NEXT:    [[TMP4]] = phi i32 [ [[TMP47:%.*]], [[ENDIF]] ], [ [[TMP0]], [[LOOP]] ]
-; OPT-NEXT:    [[TMP5]] = phi i32 [ [[TMP47]], [[ENDIF]] ], [ undef, [[LOOP]] ]
-; OPT-NEXT:    [[TMP6:%.*]] = phi i1 [ [[TMP51:%.*]], [[ENDIF]] ], [ true, [[LOOP]] ]
-; OPT-NEXT:    [[TMP7:%.*]] = phi i1 [ [[TMP51_INV:%.*]], [[ENDIF]] ], [ true, [[LOOP]] ]
-; OPT-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP3]])
-; OPT-NEXT:    [[TMP8]] = call i64 @llvm.amdgcn.if.break.i64(i1 [[TMP7]], i64 [[PHI_BROKEN]])
-; OPT-NEXT:    [[TMP9:%.*]] = call i1 @llvm.amdgcn.loop.i64(i64 [[TMP8]])
-; OPT-NEXT:    [[TMP10]] = call i64 @llvm.amdgcn.if.break.i64(i1 [[TMP6]], i64 [[PHI_BROKEN2]])
-; OPT-NEXT:    br i1 [[TMP9]], label [[FLOW1]], label [[LOOP]]
+; OPT-NEXT:    [[TMP3]] = phi i32 [ [[TMP47:%.*]], [[ENDIF]] ], [ undef, [[LOOP]] ]
+; OPT-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP51:%.*]], [[ENDIF]] ], [ true, [[LOOP]] ]
+; OPT-NEXT:    [[TMP5:%.*]] = phi i1 [ [[TMP51_INV:%.*]], [[ENDIF]] ], [ true, [[LOOP]] ]
+; OPT-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP2]])
+; OPT-NEXT:    [[TMP6]] = call i64 @llvm.amdgcn.if.break.i64(i1 [[TMP5]], i64 [[PHI_BROKEN]])
+; OPT-NEXT:    [[TMP7:%.*]] = call i1 @llvm.amdgcn.loop.i64(i64 [[TMP6]])
+; OPT-NEXT:    [[TMP8]] = call i64 @llvm.amdgcn.if.break.i64(i1 [[TMP4]], i64 [[PHI_BROKEN2]])
+; OPT-NEXT:    br i1 [[TMP7]], label [[FLOW1]], label [[LOOP]]
 ; OPT:       Flow1:
-; OPT-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP8]])
-; OPT-NEXT:    [[TMP11:%.*]] = call i1 @llvm.amdgcn.loop.i64(i64 [[TMP10]])
-; OPT-NEXT:    br i1 [[TMP11]], label [[IF:%.*]], label [[LOOP_OUTER]]
+; OPT-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP6]])
+; OPT-NEXT:    [[TMP9:%.*]] = call i1 @llvm.amdgcn.loop.i64(i64 [[TMP8]])
+; OPT-NEXT:    br i1 [[TMP9]], label [[IF:%.*]], label [[LOOP_OUTER]]
 ; OPT:       IF:
-; OPT-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP10]])
+; OPT-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP8]])
 ; OPT-NEXT:    ret void
 ; OPT:       ENDIF:
 ; OPT-NEXT:    [[TMP47]] = add i32 [[TMP45]], 1
 ; OPT-NEXT:    [[TMP51]] = icmp eq i32 [[TMP47]], [[CONT:%.*]]
 ; OPT-NEXT:    [[TMP51_INV]] = xor i1 [[TMP51]], true
 ; OPT-NEXT:    br label [[FLOW]]
 ;
 ; GCN-LABEL: multi_else_break:

 ; OPT-NEXT:    [[TMP7]] = phi i1 [ [[TMP1]], [[FLOW3]] ], [ true, [[NODEBLOCK]] ]
 ; OPT-NEXT:    [[TMP8:%.*]] = phi i1 [ false, [[FLOW3]] ], [ true, [[NODEBLOCK]] ]
 ; OPT-NEXT:    br i1 [[TMP8]], label [[LEAFBLOCK:%.*]], label [[FLOW4]]
 ; OPT:       case1:
 ; OPT-NEXT:    [[LOAD2:%.*]] = load volatile i32, i32 addrspace(1)* undef, align 4
 ; OPT-NEXT:    [[CMP2]] = icmp sge i32 [[TMP]], [[LOAD2]]
 ; OPT-NEXT:    br label [[FLOW3]]
 ; OPT:       Flow5:
-; OPT-NEXT:    [[TMP9]] = phi i32 [ [[LSR_IV_NEXT]], [[CASE0]] ], [ [[TMP6]], [[LEAFBLOCK]] ]
+; OPT-NEXT:    [[TMP9]] = phi i32 [ [[LSR_IV_NEXT]], [[CASE0]] ], [ undef, [[LEAFBLOCK]] ]
 ; OPT-NEXT:    [[TMP10]] = phi i1 [ [[CMP1]], [[CASE0]] ], [ [[TMP7]], [[LEAFBLOCK]] ]
 ; OPT-NEXT:    br label [[FLOW4]]
 ; OPT:       bb9:
 ; OPT-NEXT:    call void @llvm.amdgcn.end.cf.i64(i64 [[TMP4]])
 ; OPT-NEXT:    ret void
 ;
 ; GCN-LABEL: multi_if_break_loop:
 ; GCN:       ; %bb.0: ; %bb

llvm/test/CodeGen/AMDGPU/while-break.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -march=amdgcn -mcpu=gfx1010 -verify-machineinstrs < %s | FileCheck %s -check-prefix=GCN
 
 define amdgpu_ps float @while_break(i32 %z, float %v, i32 %x, i32 %y) #0 {
 ; GCN-LABEL: while_break:
 ; GCN:       ; %bb.0: ; %entry
 ; GCN-NEXT:    s_mov_b32 s1, -1
 ; GCN-NEXT:    s_mov_b32 s0, 0
 ; GCN-NEXT:    s_branch .LBB0_2
 ; GCN-NEXT:  .LBB0_1: ; %Flow2
 ; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
 ; GCN-NEXT:    s_or_b32 exec_lo, exec_lo, s4
-; GCN-NEXT:    v_mov_b32_e32 v1, v5
 ; GCN-NEXT:    s_and_b32 s2, exec_lo, s3
 ; GCN-NEXT:    s_or_b32 s0, s2, s0
 ; GCN-NEXT:    s_andn2_b32 exec_lo, exec_lo, s0
 ; GCN-NEXT:    s_cbranch_execz .LBB0_8
 ; GCN-NEXT:  .LBB0_2: ; %header
 ; GCN-NEXT:    ; =>This Inner Loop Header: Depth=1
 ; GCN-NEXT:    s_add_i32 s1, s1, 1
 ; GCN-NEXT:    s_mov_b32 s2, 0
 ; GCN-NEXT:    v_cmp_ge_i32_e32 vcc_lo, s1, v2
-; GCN-NEXT:    ; implicit-def: $vgpr4
 ; GCN-NEXT:    s_and_saveexec_b32 s3, vcc_lo
 ; GCN-NEXT:    s_xor_b32 s3, exec_lo, s3
 ; GCN-NEXT:  ; %bb.3: ; %else
 ; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
 ; GCN-NEXT:    v_cmp_lt_i32_e32 vcc_lo, s1, v3
-; GCN-NEXT:    v_mov_b32_e32 v4, v1
 ; GCN-NEXT:    s_and_b32 s2, vcc_lo, exec_lo
 ; GCN-NEXT:  ; %bb.4: ; %Flow
 ; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
-; GCN-NEXT:    s_or_saveexec_b32 s3, s3
-; GCN-NEXT:    v_mov_b32_e32 v5, v4
-; GCN-NEXT:    s_xor_b32 exec_lo, exec_lo, s3
+; GCN-NEXT:    s_andn2_saveexec_b32 s3, s3
 ; GCN-NEXT:  ; %bb.5: ; %if
 ; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
-; GCN-NEXT:    v_add_f32_e32 v5, 1.0, v1
+; GCN-NEXT:    v_add_f32_e32 v1, 1.0, v1
 ; GCN-NEXT:    s_or_b32 s2, s2, exec_lo
 ; GCN-NEXT:  ; %bb.6: ; %Flow1
 ; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
 ; GCN-NEXT:    s_or_b32 exec_lo, exec_lo, s3
 ; GCN-NEXT:    s_mov_b32 s3, -1
 ; GCN-NEXT:    s_and_saveexec_b32 s4, s2
 ; GCN-NEXT:    s_cbranch_execz .LBB0_1
 ; GCN-NEXT:  ; %bb.7: ; %latch
 ; GCN-NEXT:    ; in Loop: Header=BB0_2 Depth=1
 ; GCN-NEXT:    v_cmp_lt_i32_e32 vcc_lo, s1, v0
-; GCN-NEXT:    v_mov_b32_e32 v4, v5
 ; GCN-NEXT:    s_orn2_b32 s3, vcc_lo, exec_lo
 ; GCN-NEXT:    s_branch .LBB0_1
 ; GCN-NEXT:  .LBB0_8: ; %end
 ; GCN-NEXT:    s_or_b32 exec_lo, exec_lo, s0
-; GCN-NEXT:    v_mov_b32_e32 v0, v4
+; GCN-NEXT:    v_mov_b32_e32 v0, v1
 ; GCN-NEXT:    ; return to shader part epilog
 entry:
   br label %header
 
 header:
   %v.1 = phi float [ %v, %entry ], [ %v.2, %latch ]
   %ind = phi i32 [ 0, %entry], [ %ind.inc, %latch ]
   %cc = icmp slt i32 %ind, %x

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:    [[TMP14:%.*]] = phi i1 [ [[TMP23:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP11:%.*]] = phi i1 [ [[TMP24:%.*]], [[FLOW10]] ], [ undef, [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ [[TMP23:%.*]], [[FLOW10]] ], [ [[TMP7]], [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ [[TMP24]], [[FLOW10]] ], [ [[TMP8]], [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i1 [ [[TMP25:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ]
 ; CHECK-NEXT:    [[DOTINV11:%.*]] = xor i1 [[TMP12]], true
 ; CHECK-NEXT:    [[DOTINV:%.*]] = xor i1 [[TMP13]], 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:%.*]] ], [ [[TMP17:%.*]], [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    [[TMP15:%.*]] = phi i1 [ [[TMP20:%.*]], [[FLOW15:%.*]] ], [ undef, [[LOOP_EXIT_GUARD1]] ]
 ; CHECK-NEXT:    [[TMP16:%.*]] = phi i1 [ [[TMP21:%.*]], [[FLOW15]] ], [ [[DOTINV]], [[LOOP_EXIT_GUARD1]] ]
 ; CHECK-NEXT:    br label [[FLOW13:%.*]]
 ; CHECK:       if.then69:
 ; CHECK-NEXT:    br label [[FLOW15]]
 ; CHECK:       lor.rhs:
 ; CHECK-NEXT:    br label [[FLOW12]]
 ; CHECK:       while.end76:
 ; CHECK-NEXT:    br label [[FLOW6:%.*]]

 ; CHECK-NEXT:    br label [[FLOW5]]
 ; CHECK:       Flow5:
 ; CHECK-NEXT:    br label [[FLOW16]]
 ; CHECK:       Flow6:
 ; CHECK-NEXT:    br label [[FLOW17]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       Flow12:
-; CHECK-NEXT:    [[TMP17]] = phi i1 [ true, [[LOR_RHS]] ], [ undef, [[WHILE_COND]] ]
+; CHECK-NEXT:    [[TMP17:%.*]] = phi i1 [ true, [[LOR_RHS]] ], [ undef, [[WHILE_COND]] ]
 ; 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:    [[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-NEXT:    br i1 [[TMP26:%.*]], 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:    [[TMP23]] = phi i1 [ undef, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ]
+; CHECK-NEXT:    [[TMP24]] = phi i1 [ undef, [[WHILE_COND47]] ], [ false, [[WHILE_BODY63]] ]
+; CHECK-NEXT:    [[TMP25]] = phi i1 [ false, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ]
 ; CHECK-NEXT:    br label [[FLOW9]]
 ; CHECK:       Flow13:
-; CHECK-NEXT:    [[TMP24]] = phi i1 [ [[TMP15]], [[FLOW14]] ], [ [[TMP17]], [[FLOW12]] ]
-; CHECK-NEXT:    [[TMP25:%.*]] = phi i1 [ [[TMP16]], [[FLOW14]] ], [ true, [[FLOW12]] ]
-; CHECK-NEXT:    br i1 [[TMP25]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]]
+; CHECK-NEXT:    [[TMP26]] = phi i1 [ [[TMP15]], [[FLOW14]] ], [ [[TMP17]], [[FLOW12]] ]
+; CHECK-NEXT:    [[TMP27:%.*]] = phi i1 [ [[TMP16]], [[FLOW14]] ], [ true, [[FLOW12]] ]
+; CHECK-NEXT:    br i1 [[TMP27]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]]
 ; CHECK:       loop.exit.guard1:
 ; CHECK-NEXT:    br i1 [[DOTINV]], label [[LOOP_EXIT_GUARD2]], label [[FLOW14]]
 ; CHECK:       loop.exit.guard2:
 ; CHECK-NEXT:    br i1 [[DOTINV11]], label [[IF_THEN69]], label [[FLOW15]]
 ;
 entry:
   br i1 %Pred0, label %if.end, label %if.then
 

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:    [[TMP4:%.*]] = phi i1 [ [[TMP6:%.*]], [[FLOW2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW2]] ], [ undef, [[H2]] ]
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP7]], [[FLOW2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ [[TMP8:%.*]], [[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 [ false, [[L1:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ undef, [[L1:%.*]] ], [ [[TMP2]], [[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 [[TMP7:%.*]], label [[C:%.*]], label [[EXIT]]
+; CHECK-NEXT:    br i1 [[TMP9:%.*]], label [[C:%.*]], label [[EXIT]]
 ; CHECK:       Flow2:
-; CHECK-NEXT:    [[TMP6]] = phi i1 [ false, [[L2]] ], [ true, [[B2]] ]
+; CHECK-NEXT:    [[TMP7]] = phi i1 [ undef, [[L2]] ], [ false, [[B2]] ]
+; CHECK-NEXT:    [[TMP8]] = phi i1 [ false, [[L2]] ], [ true, [[B2]] ]
 ; CHECK-NEXT:    br label [[FLOW]]
 ; CHECK:       Flow4:
-; CHECK-NEXT:    [[TMP7]] = phi i1 [ [[TMP2]], [[FLOW5]] ], [ [[TMP0]], [[FLOW3]] ]
-; CHECK-NEXT:    [[TMP8:%.*]] = phi i1 [ [[TMP5]], [[FLOW5]] ], [ true, [[FLOW3]] ]
-; CHECK-NEXT:    br i1 [[TMP8]], label [[LOOP_EXIT_GUARD:%.*]], label [[H1]]
+; CHECK-NEXT:    [[TMP9]] = phi i1 [ [[TMP5]], [[FLOW5]] ], [ [[TMP0]], [[FLOW3]] ]
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ [[TMP6]], [[FLOW5]] ], [ true, [[FLOW3]] ]
+; CHECK-NEXT:    br i1 [[TMP10]], label [[LOOP_EXIT_GUARD:%.*]], label [[H1]]
 ; CHECK:       loop.exit.guard1:
 ; CHECK-NEXT:    br i1 [[TMP3]], label [[L1]], label [[FLOW5]]
 ;
 entry:
   br label %H1
 
 H1:                                               ; preds = %L1, %entry
   br i1 %PredH1, label %H2, label %B1