Introduce fix-irreducible pass

[sameerds]

Summary

An irreducible SCC is one which has multiple "header" blocks, i.e., blocks
with control-flow edges incident from outside the SCC. This pass converts an
irreducible SCC into a natural loop by introducing a single new header
block and redirecting all the edges on the original headers to this
new block.

This is a useful workaround for a limitation in the structurizer
which, which produces incorrect control flow in the presence of
irreducible regions. The AMDGPU backend provides an option to
enable this pass before the structurizer, which may eventually be
enabled by default.

[arsenm]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

186 ↗

(On Diff #254106)

Unrelated change

[sameerds]

removed unrelated change; refactored out a dubious nullptr assignment

[sameerds]

missing clang-format; sorry about that noise!

[sameerds]

added an ascii diagram illustrating the transformation

[nhaehnle]

Two minor nitpicks, apart from that it LGTM

llvm/lib/Transforms/Utils/FixIrreducible.cpp

82

Nitpick: it's common to use 'class' for passes (not that it makes a real difference especially here...)

231–234

#ifndef NDEBUG for the verifyLoop calls?

[sameerds]

llvm/lib/Transforms/Utils/FixIrreducible.cpp

82

There are other examples with a struct, and some with a class whose entire body is public anyway. So decided to keep the struct.

231–234

The body of verifyLoop() is itself guarded with NDEBUG. There are places where it is called without guards, including LoopPass itself.

[RKSimon]

@sameerds Please can you take a look at http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/23136 - I think you introduced a crash on the nested.ll test on the windows EXPENSIVE_CHECK build bot

[sameerds]

In D77198#1994210, @RKSimon wrote:

@sameerds Please can you take a look at http://lab.llvm.org:8011/builders/llvm-clang-x86_64-expensive-checks-win/builds/23136 - I think you introduced a crash on the nested.ll test on the windows EXPENSIVE_CHECK build bot

Yeah. The fix is up for review: https://reviews.llvm.org/D78544

llvm/include/llvm/Analysis/LoopInfo.h

public:
   }
 
   // True if the block is a loop header node
   bool isLoopHeader(const BlockT *BB) const {
     const LoopT *L = getLoopFor(BB);
     return L && L->getHeader() == BB;
   }
 
+  /// Return the top-level loops.
+  const std::vector<LoopT *> &getTopLevelLoops() const { return TopLevelLoops; }
+
+  /// Return the top-level loops.
+  std::vector<LoopT *> &getTopLevelLoopsVector() { return TopLevelLoops; }
+
   /// This removes the specified top-level loop from this loop info object.
   /// The loop is not deleted, as it will presumably be inserted into
   /// another loop.
   LoopT *removeLoop(iterator I) {
     assert(I != end() && "Cannot remove end iterator!");
     LoopT *L = *I;
     assert(!L->getParentLoop() && "Not a top-level loop!");
     TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin()));

llvm/include/llvm/InitializePasses.h

 void initializeExpandMemCmpPassPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeExpandReductionsPass(PassRegistry&);
 void initializeMakeGuardsExplicitLegacyPassPass(PassRegistry&);
 void initializeExternalAAWrapperPassPass(PassRegistry&);
 void initializeFEntryInserterPass(PassRegistry&);
 void initializeFinalizeISelPass(PassRegistry&);
 void initializeFinalizeMachineBundlesPass(PassRegistry&);
+void initializeFixIrreduciblePass(PassRegistry &);
 void initializeFixupStatepointCallerSavedPass(PassRegistry&);
 void initializeFlattenCFGPassPass(PassRegistry&);
 void initializeFloat2IntLegacyPassPass(PassRegistry&);
 void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeForwardControlFlowIntegrityPass(PassRegistry&);
 void initializeFuncletLayoutPass(PassRegistry&);
 void initializeFunctionImportLegacyPassPass(PassRegistry&);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createMustBeExecutedContextPrinter();
       (void) llvm::createFloat2IntPass();
       (void) llvm::createEliminateAvailableExternallyPass();
       (void) llvm::createScalarizeMaskedMemIntrinPass();
       (void) llvm::createWarnMissedTransformationsPass();
       (void) llvm::createHardwareLoopsPass();
       (void) llvm::createInjectTLIMappingsLegacyPass();
       (void) llvm::createUnifyLoopExitsPass();
+      (void) llvm::createFixIrreduciblePass();
 
       (void)new llvm::IntervalPartition();
       (void)new llvm::ScalarEvolutionWrapperPass();
       llvm::Function::Create(nullptr, llvm::GlobalValue::ExternalLinkage)->viewCFGOnly();
       llvm::RGPassManager RGM;
       llvm::TargetLibraryInfoImpl TLII;
       llvm::TargetLibraryInfo TLI(TLII);
       llvm::AliasAnalysis AA(TLI);

llvm/include/llvm/Transforms/Utils.h

 
 //===----------------------------------------------------------------------===//
 //
 // UnifyLoopExits - For each loop, creates a new block N such that all exiting
 // blocks branch to N, and then N distributes control flow to all the original
 // exit blocks.
 //
 FunctionPass *createUnifyLoopExitsPass();
+
+//===----------------------------------------------------------------------===//
+//
+// FixIrreducible - Convert each SCC with irreducible control-flow
+// into a natural loop.
+//
+FunctionPass *createFixIrreduciblePass();
 }
 
 #endif

llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

bool GCNPassConfig::addPreISel() {
   // FIXME: We need to run a pass to propagate the attributes when calls are
   // supported.
 
   // Merge divergent exit nodes. StructurizeCFG won't recognize the multi-exit
   // regions formed by them.
   addPass(&AMDGPUUnifyDivergentExitNodesID);
   if (!LateCFGStructurize) {
     if (EnableStructurizerWorkarounds) {
+      addPass(createFixIrreduciblePass());
       addPass(createUnifyLoopExitsPass());
     }
     addPass(createStructurizeCFGPass(false)); // true -> SkipUniformRegions
   }
   addPass(createSinkingPass());
   addPass(createAMDGPUAnnotateUniformValues());
   if (!LateCFGStructurize) {
     addPass(createSIAnnotateControlFlowPass());

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

while (I != Out->end() && isa<PHINode>(I)) {
     Phi->addIncoming(NewPhi, GuardBlock);
     ++I;
   }
 }
 
 using BBPredicates = DenseMap<BasicBlock *, PHINode *>;
 using BBSetVector = SetVector<BasicBlock *>;
 
-// Collect predicates for each outgoing block. If control reaches the
-// Hub from an incoming block InBB, then the predicate for each
-// outgoing block OutBB decides whether control is forwarded to OutBB.
+// 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.
 //
-// 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 createGuardPredicates(BasicBlock *FirstGuardBlock,
-                                  BBPredicates &GuardPredicates,
-                                  SmallVectorImpl<WeakVH> &DeletionCandidates,
-                                  const BBSetVector &Incoming,
-                                  const BBSetVector &Outgoing) {
-  auto &Context = Incoming.front()->getContext();
-  auto BoolTrue = ConstantInt::getTrue(Context);
-  auto BoolFalse = ConstantInt::getFalse(Context);
-
-  // 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");
-    auto Phi =
-        PHINode::Create(Type::getInt1Ty(Context), Incoming.size(),
-                        StringRef("Guard.") + Out->getName(), FirstGuardBlock);
-    GuardPredicates[Out] = Phi;
-  }
+// - condition is non-null iff the branch is conditional.
+// - Succ1 is non-null iff the sole/taken target is an outgoing block.
+// - Succ2 is non-null iff condition is non-null and the fallthrough
+//         target is an outgoing block.
+static std::tuple<Value *, BasicBlock *, BasicBlock *>
+redirectToHub(BasicBlock *BB, BasicBlock *FirstGuardBlock,
+  auto Branch = cast<BranchInst>(BB->getTerminator());
+  auto Condition = Branch->isConditional() ? Branch->getCondition() : nullptr;
 
-  for (auto In : Incoming) {
-    auto Branch = cast<BranchInst>(In->getTerminator());
-    BasicBlock *Succ0 = Branch->getSuccessor(0);
-    BasicBlock *Succ1 = nullptr;
-
-    Succ0 = Outgoing.count(Succ0) ? Succ0 : nullptr;
 
-    if (Branch->isUnconditional()) {
-      Branch->setSuccessor(0, FirstGuardBlock);
-      assert(Succ0);
-    } else {
-      Succ1 = Branch->getSuccessor(1);
-      Succ1 = Outgoing.count(Succ1) ? Succ1 : nullptr;
-      assert(Succ0 || Succ1);
-      if (Succ0 && !Succ1) {
-        Branch->setSuccessor(0, FirstGuardBlock);
-      } else if (Succ1 && !Succ0) {
-        Branch->setSuccessor(1, FirstGuardBlock);
-      } else {
-        Branch->eraseFromParent();
-        BranchInst::Create(FirstGuardBlock, In);
-      }
-    }
+      BranchInst::Create(FirstGuardBlock, BB);
 
-    assert(Succ0 || Succ1);
+  return std::make_tuple(Condition, Succ0, Succ1);
+}
+
+// Capture the existing control flow as guard predicates, and redirect
+// control flow from every incoming block to the first guard block in
+// the hub.
+//
+// There is one guard predicate for each outgoing block OutBB. The
+// predicate is a PHINode with one input for each InBB which
+// represents whether the hub should transfer control flow to OutBB if
+// it arrived from InBB. 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(
+    BasicBlock *FirstGuardBlock, BBPredicates &GuardPredicates,
+    SmallVectorImpl<WeakVH> &DeletionCandidates, const BBSetVector &Incoming,
+    const BBSetVector &Outgoing) {
+  auto &Context = Incoming.front()->getContext();
+  auto BoolTrue = ConstantInt::getTrue(Context);
+  auto BoolFalse = ConstantInt::getFalse(Context);
+
+  // 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");
+    auto Phi =
+        PHINode::Create(Type::getInt1Ty(Context), Incoming.size(),
+                        StringRef("Guard.") + Out->getName(), FirstGuardBlock);
+    GuardPredicates[Out] = Phi;
+  }
+
+  for (auto In : Incoming) {
+    Value *Condition;
+    BasicBlock *Succ0;
+    BasicBlock *Succ1;
+    std::tie(Condition, Succ0, Succ1) =
+        redirectToHub(In, FirstGuardBlock, Outgoing);
 
     // Optimization: Consider an incoming block A with both successors
     // Succ0 and Succ1 in the set of outgoing blocks. The predicates
     // 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 predicate for
     // Succ1 is always true.
     bool OneSuccessorDone = false;
-    auto Condition = Branch->getCondition();
     for (int i = 0, e = Outgoing.size() - 1; i != e; ++i) {
       auto Out = Outgoing[i];
       auto Phi = GuardPredicates[Out];
       if (Out != Succ0 && Out != Succ1) {
         Phi->addIncoming(BoolFalse, In);
         continue;
       }
       // Optimization: When only one successor is an outgoing block,
for (auto In : Incoming) {
           Updates.push_back({DominatorTree::Delete, In, Succ});
       }
       Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
     }
   }
 
   BBPredicates GuardPredicates;
   SmallVector<WeakVH, 8> DeletionCandidates;
-  createGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates,
+  convertToGuardPredicates(FirstGuardBlock, GuardPredicates, DeletionCandidates,
                            Incoming, Outgoing);
 
   GuardBlocks.push_back(FirstGuardBlock);
   createGuardBlocks(GuardBlocks, F, Outgoing, GuardPredicates, Prefix);
 
   // 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);
   }

llvm/lib/Transforms/Utils/CMakeLists.txt

add_llvm_component_library(LLVMTransformUtils
   CodeExtractor.cpp
   CodeMoverUtils.cpp
   CtorUtils.cpp
   Debugify.cpp
   DemoteRegToStack.cpp
   EntryExitInstrumenter.cpp
   EscapeEnumerator.cpp
   Evaluator.cpp
+  FixIrreducible.cpp
   FlattenCFG.cpp
   FunctionComparator.cpp
   FunctionImportUtils.cpp
   GlobalStatus.cpp
   GuardUtils.cpp
   InlineFunction.cpp
   ImportedFunctionsInliningStatistics.cpp
   InjectTLIMappings.cpp

llvm/lib/Transforms/Utils/FixIrreducible.cpp

+//===- FixIrreducible.cpp - Convert irreducible control-flow into loops ---===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// An irreducible SCC is one which has multiple "header" blocks, i.e., blocks
+// with control-flow edges incident from outside the SCC.  This pass converts a
+// irreducible SCC into a natural loop by applying the following transformation:
+//
+// 1. Collect the set of headers H of the SCC.
+// 2. Collect the set of predecessors P of these headers. These may be inside as
+//    well as outside the SCC.
+// 3. Create block N and redirect every edge from set P to set H through N.
+//
+// This converts the SCC into a natural loop with N as the header: N is the only
+// block with edges incident from outside the SCC, and all backedges in the SCC
+// are incident on N, i.e., for every backedge, the head now dominates the tail.
+//
+// INPUT CFG: The blocks A and B form an irreducible loop with two headers.
+//
+//                        Entry
+//                       /     \
+//                      v       v
+//                      A ----> B
+//                      ^      /|
+//                       `----' |
+//                              v
+//                             Exit
+//
+// OUTPUT CFG: Edges incident on A and B are now redirected through a
+// new block N, forming a natural loop consisting of N, A and B.
+//
+//                        Entry
+//                          |
+//                          v
+//                    .---> N <---.
+//                   /     / \     \
+//                  |     /   \     |
+//                  \    v     v    /
+//                   `-- A     B --'
+//                             |
+//                             v
+//                            Exit
+//
+// The transformation is applied to every maximal SCC that is not already
+// recognized as a loop. The pass operates on all maximal SCCs found in the
+// function body outside of any loop, as well as those found inside each loop,
+// including inside any newly created loops. This ensures that any SCC hidden
+// inside a maximal SCC is also transformed.
+//
+// The actual transformation is handled by function CreateControlFlowHub, which
+// takes a set of incoming blocks (the predecessors) and outgoing blocks (the
+// headers). The function also moves every PHINode in an outgoing block to the
+// hub. Since the hub dominates all the outgoing blocks, each such PHINode
+// continues to dominate its uses. Since every header in an SCC has at least two
+// predecessors, every value used in the header (or later) but defined in a
+// predecessor (or earlier) is represented by a PHINode in a header. Hence the
+// above handling of PHINodes is sufficient and no further processing is
+// required to restore SSA.
+//
+// Limitation: The pass cannot handle switch statements and indirect
+//             branches. Both must be lowered to plain branches first.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/SCCIterator.h"
+#include "llvm/Analysis/LoopIterator.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+
+#define DEBUG_TYPE "fix-irreducible"
+
+using namespace llvm;
+
+namespace {
+struct FixIrreducible : public FunctionPass {
+  static char ID;
+  FixIrreducible() : FunctionPass(ID) {
+    initializeFixIrreduciblePass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.addRequiredID(LowerSwitchID);
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+    AU.addPreservedID(LowerSwitchID);
+    AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<LoopInfoWrapperPass>();
+  }
+
+  bool runOnFunction(Function &F);
+};
+} // namespace
+
+char FixIrreducible::ID = 0;
+
+FunctionPass *llvm::createFixIrreduciblePass() { return new FixIrreducible(); }
+
+INITIALIZE_PASS_BEGIN(FixIrreducible, "fix-irreducible",
+                      "Convert irreducible control-flow into natural loops",
+                      false /* Only looks at CFG */, false /* Analysis Pass */)
+INITIALIZE_PASS_DEPENDENCY(LowerSwitch)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(FixIrreducible, "fix-irreducible",
+                    "Convert irreducible control-flow into natural loops",
+                    false /* Only looks at CFG */, false /* Analysis Pass */)
+
+// When a new loop is created, existing children of the parent loop may now be
+// fully inside the new loop. Reconnect these as children of the new loop.
+static void reconnectChildLoops(LoopInfo &LI, Loop *ParentLoop, Loop *NewLoop,
+                                SetVector<BasicBlock *> &Blocks,
+                                SetVector<BasicBlock *> &Headers) {
+  auto &CandidateLoops = ParentLoop ? ParentLoop->getSubLoopsVector()
+                                    : LI.getTopLevelLoopsVector();
+  // Partition the candidate loops into two ranges. The first part
+  // contains loops that are not children of the new loop. The second
+  // part contains children that need to be moved to the new loop.
+  auto FirstChild =
+      std::partition(CandidateLoops.begin(), CandidateLoops.end(), [&](Loop *L) {
+        return L == NewLoop || Blocks.count(L->getHeader()) == 0;
+      });
+  for (auto II = FirstChild, IE = CandidateLoops.end(); II != IE; ++II) {
+    auto Child = *II;
+    LLVM_DEBUG(dbgs() << "child loop: " << Child->getHeader()->getName()
+                      << "\n");
+    // TODO: A child loop whose header is also a header in the current
+    // SCC gets destroyed since its backedges are removed. That may
+    // not be necessary if we can retain such backedges.
+    if (Headers.count(Child->getHeader())) {
+      for (auto BB : Child->blocks()) {
+        LI.changeLoopFor(BB, NewLoop);
+        LLVM_DEBUG(dbgs() << "moved block from child: " << BB->getName()
+                          << "\n");
+      }
+      LI.destroy(Child);
+      LLVM_DEBUG(dbgs() << "subsumed child loop (common header)\n");
+      continue;
+    }
+
+    if (ParentLoop) {
+      LLVM_DEBUG(dbgs() << "removed child loop from parent\n");
+      ParentLoop->removeChildLoop(Child);
+    }
+    LLVM_DEBUG(dbgs() << "added child loop to new loop\n");
+    NewLoop->addChildLoop(Child);
+  }
+  CandidateLoops.erase(FirstChild, CandidateLoops.end());
+}
+
+// Given a set of blocks and headers in an irreducible SCC, convert it into a
+// natural loop. Also insert this new loop at its appropriate place in the
+// hierarchy of loops.
+static void createNaturalLoopInternal(LoopInfo &LI, DominatorTree &DT,
+                                      Loop *ParentLoop,
+                                      SetVector<BasicBlock *> &Blocks,
+                                      SetVector<BasicBlock *> &Headers) {
+#ifndef NDEBUG
+  // All headers are part of the SCC
+  for (auto H : Headers) {
+    assert(Blocks.count(H));
+  }
+#endif
+
+  SetVector<BasicBlock *> Predecessors;
+  for (auto H : Headers) {
+    for (auto P : predecessors(H)) {
+      Predecessors.insert(P);
+    }
+  }
+
+  LLVM_DEBUG(
+      dbgs() << "Found predecessors:";
+      for (auto P : Predecessors) {
+        dbgs() << " " << P->getName();
+      }
+      dbgs() << "\n");
+
+  // Redirect all the backedges through a "hub" consisting of a series
+  // of guard blocks that manage the flow of control from the
+  // predecessors to the headers.
+  SmallVector<BasicBlock *, 8> GuardBlocks;
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+  CreateControlFlowHub(&DTU, GuardBlocks, Predecessors, Headers, "irr");
+#if defined(EXPENSIVE_CHECKS)
+  assert(DT.verify(DominatorTree::VerificationLevel::Full));
+#else
+  assert(DT.verify(DominatorTree::VerificationLevel::Fast));
+#endif
+
+  // Create a new loop from the now-transformed cycle
+  auto NewLoop = LI.AllocateLoop();
+  if (ParentLoop) {
+    ParentLoop->addChildLoop(NewLoop);
+  } else {
+    LI.addTopLevelLoop(NewLoop);
+  }
+
+  // Add the guard blocks to the new loop. The first guard block is
+  // the head of all the backedges, and it is the first to be inserted
+  // in the loop. This ensures that it is recognized as the
+  // header. Since the new loop is already in LoopInfo, the new blocks
+  // are also propagated up the chain of parent loops.
+  for (auto G : GuardBlocks) {
+    LLVM_DEBUG(dbgs() << "added guard block: " << G->getName() << "\n");
+    NewLoop->addBasicBlockToLoop(G, LI);
+  }
+
+  // Add the SCC blocks to the new loop.
+  for (auto BB : Blocks) {
+    NewLoop->addBlockEntry(BB);
+    if (LI.getLoopFor(BB) == ParentLoop) {
+      LLVM_DEBUG(dbgs() << "moved block from parent: " << BB->getName()
+                        << "\n");
+      LI.changeLoopFor(BB, NewLoop);
+    } else {
+      LLVM_DEBUG(dbgs() << "added block from child: " << BB->getName() << "\n");
+    }
+  }
+  LLVM_DEBUG(dbgs() << "header for new loop: "
+                    << NewLoop->getHeader()->getName() << "\n");
+
+  reconnectChildLoops(LI, ParentLoop, NewLoop, Blocks, Headers);
+
+  NewLoop->verifyLoop();
+  if (ParentLoop) {
+    ParentLoop->verifyLoop();
+  }
+#if defined(EXPENSIVE_CHECKS)
+  LI.verify(DT);
+#endif // EXPENSIVE_CHECKS
+}
+
+// Enable the graph traits required for traversing a Loop body.
+template <> struct GraphTraits<Loop> : LoopBodyTraits {};
+
+// Overloaded wrappers to go with the function template below.
+BasicBlock *unwrapBlock(BasicBlock *B) { return B; }
+BasicBlock *unwrapBlock(LoopBodyTraits::NodeRef &N) { return N.second; }
+
+static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Function *F,
+                              SetVector<BasicBlock *> &Blocks,
+                              SetVector<BasicBlock *> &Headers) {
+  createNaturalLoopInternal(LI, DT, nullptr, Blocks, Headers);
+}
+
+static void createNaturalLoop(LoopInfo &LI, DominatorTree &DT, Loop &L,
+                              SetVector<BasicBlock *> &Blocks,
+                              SetVector<BasicBlock *> &Headers) {
+  createNaturalLoopInternal(LI, DT, &L, Blocks, Headers);
+}
+
+// Convert irreducible SCCs; Graph G may be a Function* or a Loop&.
+template <class Graph>
+static bool makeReducible(LoopInfo &LI, DominatorTree &DT, Graph &&G) {
+  bool Changed = false;
+  for (auto Scc = scc_begin(G); !Scc.isAtEnd(); ++Scc) {
+    if (Scc->size() < 2)
+      continue;
+    SetVector<BasicBlock *> Blocks;
+    LLVM_DEBUG(dbgs() << "Found SCC:");
+    for (auto N : *Scc) {
+      auto BB = unwrapBlock(N);
+      LLVM_DEBUG(dbgs() << " " << BB->getName());
+      Blocks.insert(BB);
+    }
+    LLVM_DEBUG(dbgs() << "\n");
+
+    // Minor optimization: The SCC blocks are usually discovered in an order
+    // that is the opposite of the order in which these blocks appear as branch
+    // targets. This results in a lot of condition inversions in the control
+    // flow out of the new ControlFlowHub, which can be mitigated if the orders
+    // match. So we discover the headers using the reverse of the block order.
+    SetVector<BasicBlock *> Headers;
+    LLVM_DEBUG(dbgs() << "Found headers:");
+    for (auto BB : reverse(Blocks)) {
+      for (const auto P : predecessors(BB)) {
+        if (!Blocks.count(P)) {
+          LLVM_DEBUG(dbgs() << " " << BB->getName());
+          Headers.insert(BB);
+          break;
+        }
+      }
+    }
+    LLVM_DEBUG(dbgs() << "\n");
+
+    if (Headers.size() == 1) {
+      assert(LI.isLoopHeader(Headers.front()));
+      LLVM_DEBUG(dbgs() << "Natural loop with a single header: skipped\n");
+      continue;
+    }
+    createNaturalLoop(LI, DT, G, Blocks, Headers);
+    Changed = true;
+  }
+  return Changed;
+}
+
+bool FixIrreducible::runOnFunction(Function &F) {
+  LLVM_DEBUG(dbgs() << "===== Fix irreducible control-flow in function: "
+                    << F.getName() << "\n");
+  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  bool Changed = false;
+  SmallVector<Loop *, 8> WorkList;
+
+  LLVM_DEBUG(dbgs() << "visiting top-level\n");
+  Changed |= makeReducible(LI, DT, &F);
+
+  // Any SCCs reduced are now already in the list of top-level loops, so simply
+  // add them all to the worklist.
+  for (auto L : LI) {
+    WorkList.push_back(L);
+  }
+
+  while (!WorkList.empty()) {
+    auto L = WorkList.back();
+    WorkList.pop_back();
+    LLVM_DEBUG(dbgs() << "visiting loop with header "
+                      << L->getHeader()->getName() << "\n");
+    Changed |= makeReducible(LI, DT, *L);
+    // Any SCCs reduced are now already in the list of child loops, so simply
+    // add them all to the worklist.
+    WorkList.append(L->begin(), L->end());
+  }
+
+  return Changed;
+}

llvm/lib/Transforms/Utils/Utils.cpp

void llvm::initializeTransformUtils(PassRegistry &Registry) {
   initializeNameAnonGlobalLegacyPassPass(Registry);
   initializePromoteLegacyPassPass(Registry);
   initializeStripNonLineTableDebugInfoPass(Registry);
   initializeUnifyFunctionExitNodesPass(Registry);
   initializeMetaRenamerPass(Registry);
   initializeStripGCRelocatesPass(Registry);
   initializePredicateInfoPrinterLegacyPassPass(Registry);
   initializeInjectTLIMappingsLegacyPass(Registry);
+  initializeFixIrreduciblePass(Registry);
   initializeUnifyLoopExitsPass(Registry);
 }
 
 /// LLVMInitializeTransformUtils - C binding for initializeTransformUtilsPasses.
 void LLVMInitializeTransformUtils(LLVMPassRegistryRef R) {
   initializeTransformUtils(*unwrap(R));
 }
 

llvm/test/Transforms/FixIrreducible/basic.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -fix-irreducible -S | FileCheck %s -check-prefix=CHECK
+
+define i32 @basic(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
+; CHECK-LABEL: @basic(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       left:
+; 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:    [[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:    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
+  br i1 %PredLeft, label %right, label %exit
+
+right:
+  %R.phi = phi i32 [%Y, %entry], [%L, %left]
+  br i1 %PredRight, label %left, label %exit
+
+exit:
+  %Z = phi i32 [%L, %left], [%R.phi, %right]
+  ret i32 %Z
+}
+
+define i32 @feedback_loop(i1 %PredEntry, i1 %PredLeft, i1 %PredRight, i32 %X, i32 %Y) {
+; CHECK-LABEL: @feedback_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; 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:    [[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:    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
+
+right:
+  %R.phi = phi i32 [%Y, %entry], [%L.phi, %left]
+  br i1 %PredRight, label %left, label %exit
+
+exit:
+  %Z = phi i32 [%L.phi, %left], [%R.phi, %right]
+  ret i32 %Z
+}
+
+define i32 @multiple_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
+; CHECK-LABEL: @multiple_predecessors(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PREDB_INV:%.*]] = xor i1 [[PREDB:%.*]], true
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       C:
+; 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:    [[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
+
+B:
+  br i1 %PredB, label %D, label %C
+
+C:
+  %C.phi = phi i32 [%X, %A], [%Y, %B], [%D.inc, %D]
+  br i1 %PredC, label %D, label %exit
+
+D:
+  %D.phi = phi i32 [%A.inc, %A], [%Y, %B], [%C.phi, %C]
+  %D.inc = add i32 %D.phi, 1
+  br i1 %PredD, label %exit, label %C
+
+exit:
+  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
+  ret i32 %ret
+}
+
+define i32 @separate_predecessors(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
+; CHECK-LABEL: @separate_predecessors(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[X:%.*]], 1
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       C:
+; 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:    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
+
+B:
+  br label %D
+
+C:
+  %C.phi = phi i32 [%X, %A], [%D.inc, %D]
+  br i1 %PredC, label %exit, label %D
+
+D:
+  %D.phi = phi i32 [%Y, %B], [%C.phi, %C]
+  %D.inc = add i32 %D.phi, 1
+  br i1 %PredD, label %exit, label %C
+
+exit:
+  %ret = phi i32 [%C.phi, %C], [%D.inc, %D]
+  ret i32 %ret
+}
+
+define void @four_headers(i1 %PredEntry, i1 %PredX, i1  %PredY, i1 %PredD) {
+; CHECK-LABEL: @four_headers(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[X:%.*]], label [[Y:%.*]]
+; CHECK:       X:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       Y:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       A:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       B:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       C:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       D:
+; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[EXIT:%.*]], label [[IRR_GUARD]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ true, [[D:%.*]] ], [ [[PREDX:%.*]], [[X]] ], [ false, [[A:%.*]] ], [ false, [[B:%.*]] ], [ false, [[Y]] ], [ false, [[C:%.*]] ]
+; CHECK-NEXT:    [[GUARD_B:%.*]] = phi i1 [ false, [[D]] ], [ true, [[X]] ], [ true, [[A]] ], [ false, [[B]] ], [ false, [[Y]] ], [ false, [[C]] ]
+; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ false, [[D]] ], [ false, [[X]] ], [ false, [[A]] ], [ true, [[B]] ], [ [[PREDY:%.*]], [[Y]] ], [ false, [[C]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[IRR_GUARD1:%.*]]
+; CHECK:       irr.guard1:
+; CHECK-NEXT:    br i1 [[GUARD_B]], label [[B]], label [[IRR_GUARD2:%.*]]
+; CHECK:       irr.guard2:
+; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[D]]
+;
+entry:
+  br i1 %PredEntry, label %X, label %Y
+
+X:
+  br i1 %PredX, label %A, label %B
+
+Y:
+  br i1 %PredY, label %C, label %D
+
+A:
+  br label %B
+
+B:
+  br label %C
+
+C:
+  br label %D
+
+D:
+  br i1 %PredD, label %exit, label %A
+
+exit:
+  ret void
+}
+
+define i32 @hidden_nodes(i1 %PredEntry, i1 %PredA, i1 %PredB, i1 %PredC, i1 %PredD, i32 %X, i32 %Y) {
+; CHECK-LABEL: @hidden_nodes(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[A_INC:%.*]] = add i32 [[A_PHI_MOVED:%.*]], 1
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       B:
+; CHECK-NEXT:    br label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[C_INC:%.*]] = add i32 [[B_PHI_MOVED:%.*]], 1
+; 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:    [[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:    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
+  br label %B
+
+B:
+  %B.phi = phi i32 [%A.inc, %A], [%Y, %entry]
+  br label %C
+
+C:
+  %C.inc = add i32 %B.phi, 1
+  br label %D
+
+D:
+  br i1 %PredD, label %exit, label %E
+
+E:
+  br label %A
+
+exit:
+  ret i32 %B.phi
+}

llvm/test/Transforms/FixIrreducible/nested.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -fix-irreducible -S | FileCheck %s -check-prefix=CHECK
+
+define void @nested_irr_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5) {
+; CHECK-LABEL: @nested_irr_top_level(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       A1:
+; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
+; CHECK:       B1:
+; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
+; CHECK:       B2:
+; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]]
+; CHECK:       A3:
+; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
+; CHECK:       A2:
+; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
+; CHECK:       irr.guard1:
+; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ]
+; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1]], label [[B2]]
+;
+entry:
+  br i1 %Pred0, label %A1, label %A2
+
+A1:
+  br i1 %Pred1, label %B1, label %B2
+
+B1:
+  br i1 %Pred2, label %B2, label %A3
+
+B2:
+  br i1 %Pred3, label %B1, label %A3
+
+A3:
+  br i1 %Pred4, label %A2, label %exit
+
+A2:
+  br i1 %Pred5, label %A1, label %exit
+
+exit:
+  ret void
+}
+
+define void @nested_irr_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
+; CHECK-LABEL: @nested_irr_in_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[H1:%.*]]
+; CHECK:       H1:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       A1:
+; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
+; CHECK:       B1:
+; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[A3:%.*]]
+; CHECK:       B2:
+; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD1]], label [[A3]]
+; CHECK:       A3:
+; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IRR_GUARD]], label [[L1:%.*]]
+; CHECK:       A2:
+; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[IRR_GUARD]], label [[L1]]
+; CHECK:       L1:
+; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[EXIT:%.*]], label [[H1]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[H1]] ], [ false, [[A3]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
+; CHECK:       irr.guard1:
+; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED1:%.*]], [[A1]] ], [ false, [[B1:%.*]] ]
+; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1]], label [[B2]]
+;
+entry:
+  br label %H1
+
+H1:
+  br i1 %Pred0, label %A1, label %A2
+
+A1:
+  br i1 %Pred1, label %B1, label %B2
+
+B1:
+  br i1 %Pred2, label %B2, label %A3
+
+B2:
+  br i1 %Pred3, label %B1, label %A3
+
+A3:
+  br i1 %Pred4, label %A2, label %L1
+
+A2:
+  br i1 %Pred5, label %A1, label %L1
+
+L1:
+  br i1 %Pred6, label %exit, label %H1
+
+exit:
+  ret void
+}
+
+define void @loop_in_irr(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
+; CHECK-LABEL: @loop_in_irr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       A1:
+; CHECK-NEXT:    br label [[H1:%.*]]
+; CHECK:       H1:
+; CHECK-NEXT:    br label [[L1:%.*]]
+; CHECK:       L1:
+; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[H1]], label [[A3:%.*]]
+; CHECK:       A3:
+; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
+; CHECK:       A2:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1:%.*]], label [[A2]]
+;
+entry:
+  br i1 %Pred0, label %A1, label %A2
+
+A1:
+  br label %H1
+
+H1:
+  br label %L1
+
+L1:
+  br i1 %Pred1, label %H1, label %A3
+
+A3:
+  br i1 %Pred2, label %A2, label %exit
+
+A2:
+  br label %A1
+
+exit:
+  ret void
+}
+
+define void @loop_in_irr_shared_header(i1 %Pred0, i1 %Pred1, i1 %Pred2) {
+; CHECK-LABEL: @loop_in_irr_shared_header(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       H1:
+; CHECK-NEXT:    br label [[L1:%.*]]
+; CHECK:       L1:
+; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IRR_GUARD]], label [[A3:%.*]]
+; CHECK:       A3:
+; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD]], label [[EXIT:%.*]]
+; CHECK:       A2:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_H1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ true, [[L1]] ], [ [[PRED0:%.*]], [[ENTRY:%.*]] ], [ false, [[A3]] ]
+; CHECK-NEXT:    br i1 [[GUARD_H1]], label [[H1:%.*]], label [[A2]]
+;
+entry:
+  br i1 %Pred0, label %H1, label %A2
+
+H1:
+  br label %L1
+
+L1:
+  br i1 %Pred1, label %H1, label %A3
+
+A3:
+  br i1 %Pred2, label %A2, label %exit
+
+A2:
+  br label %H1
+
+exit:
+  ret void
+}
+
+define void @siblings_top_level(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6) {
+; CHECK-LABEL: @siblings_top_level(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
+; CHECK:       H1:
+; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
+; CHECK:       A1:
+; CHECK-NEXT:    br label [[IRR_GUARD1]]
+; CHECK:       A2:
+; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]]
+; CHECK:       L1:
+; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[EXIT:%.*]]
+; CHECK:       fork1:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       B1:
+; CHECK-NEXT:    br label [[H2:%.*]]
+; CHECK:       H2:
+; CHECK-NEXT:    br label [[L2:%.*]]
+; CHECK:       L2:
+; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]]
+; CHECK:       B2:
+; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ]
+; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]]
+; CHECK:       irr.guard1:
+; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1]], label [[A2]]
+;
+entry:
+  br i1 %Pred0, label %H1, label %fork1
+
+H1:
+  br i1 %Pred1, label %A1, label %A2
+
+A1:
+  br label %A2
+
+A2:
+  br i1 %Pred2, label %A1, label %L1
+
+L1:
+  br i1 %Pred3, label %H1, label %exit
+
+fork1:
+  br i1 %Pred4, label %B1, label %B2
+
+B1:
+  br label %H2
+
+H2:
+  br label %L2
+
+L2:
+  br i1 %Pred5, label %H2, label %B2
+
+B2:
+  br i1 %Pred6, label %B1, label %exit
+
+exit:
+  ret void
+}
+
+define void @siblings_in_loop(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7) {
+; CHECK-LABEL: @siblings_in_loop(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[H0:%.*]]
+; CHECK:       H0:
+; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[H1:%.*]], label [[FORK1:%.*]]
+; CHECK:       H1:
+; CHECK-NEXT:    br label [[IRR_GUARD1:%.*]]
+; CHECK:       A1:
+; CHECK-NEXT:    br label [[IRR_GUARD1]]
+; CHECK:       A2:
+; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[IRR_GUARD1]], label [[L1:%.*]]
+; CHECK:       L1:
+; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[H1]], label [[L0:%.*]]
+; CHECK:       fork1:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       B1:
+; CHECK-NEXT:    br label [[H2:%.*]]
+; CHECK:       H2:
+; CHECK-NEXT:    br label [[L2:%.*]]
+; CHECK:       L2:
+; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[H2]], label [[IRR_GUARD]]
+; CHECK:       B2:
+; CHECK-NEXT:    br i1 [[PRED6:%.*]], label [[IRR_GUARD]], label [[L0]]
+; CHECK:       L0:
+; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[EXIT:%.*]], label [[H0]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ true, [[B2:%.*]] ], [ [[PRED4:%.*]], [[FORK1]] ], [ false, [[L2]] ]
+; CHECK-NEXT:    br i1 [[GUARD_B1]], label [[B1:%.*]], label [[B2]]
+; CHECK:       irr.guard1:
+; CHECK-NEXT:    [[GUARD_A1:%.*]] = phi i1 [ true, [[A2:%.*]] ], [ [[PRED1:%.*]], [[H1]] ], [ false, [[A1:%.*]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A1]], label [[A1]], label [[A2]]
+;
+entry:
+  br label %H0
+
+H0:
+  br i1 %Pred0, label %H1, label %fork1
+
+H1:
+  br i1 %Pred1, label %A1, label %A2
+
+A1:
+  br label %A2
+
+A2:
+  br i1 %Pred2, label %A1, label %L1
+
+L1:
+  br i1 %Pred3, label %H1, label %L0
+
+fork1:
+  br i1 %Pred4, label %B1, label %B2
+
+B1:
+  br label %H2
+
+H2:
+  br label %L2
+
+L2:
+  br i1 %Pred5, label %H2, label %B2
+
+B2:
+  br i1 %Pred6, label %B1, label %L0
+
+L0:
+  br i1 %Pred7, label %exit, label %H0
+
+exit:
+  ret void
+}
+
+define void @irreducible_mountain_bug(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7, i1 %Pred8, i1 %Pred9, i1 %Pred10, i1 %Pred11, i1 %Pred12, i1 %Pred13) {
+; CHECK-LABEL: @irreducible_mountain_bug(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PRED0:%.*]], label [[IF_END:%.*]], label [[IF_THEN:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br i1 [[PRED1:%.*]], label [[IF_THEN7:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    br label [[IF_END16:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    br label [[IF_END16]]
+; CHECK:       if.end16:
+; CHECK-NEXT:    br i1 [[PRED2:%.*]], label [[WHILE_COND_PREHEADER:%.*]], label [[IF_THEN39:%.*]]
+; CHECK:       while.cond.preheader:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    br i1 [[PRED3:%.*]], label [[IRR_GUARD:%.*]], label [[LOR_RHS:%.*]]
+; CHECK:       cond.true49:
+; CHECK-NEXT:    br i1 [[PRED4:%.*]], label [[IF_THEN69:%.*]], label [[WHILE_BODY63:%.*]]
+; CHECK:       while.body63:
+; CHECK-NEXT:    br i1 [[PRED5:%.*]], label [[EXIT:%.*]], label [[WHILE_COND47:%.*]]
+; CHECK:       while.cond47:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       cond.end61:
+; CHECK-NEXT:    br i1 [[PRED7:%.*]], label [[WHILE_BODY63]], label [[WHILE_COND]]
+; CHECK:       if.then69:
+; CHECK-NEXT:    br i1 [[PRED8:%.*]], label [[EXIT]], label [[WHILE_COND]]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    br i1 [[PRED9:%.*]], label [[IRR_GUARD]], label [[WHILE_END76:%.*]]
+; CHECK:       while.end76:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       if.then39:
+; CHECK-NEXT:    br i1 [[PRED10:%.*]], label [[EXIT]], label [[IF_END_I145:%.*]]
+; CHECK:       if.end.i145:
+; CHECK-NEXT:    br i1 [[PRED11:%.*]], label [[EXIT]], label [[IF_END8_I149:%.*]]
+; CHECK:       if.end8.i149:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br i1 [[PRED12:%.*]], label [[EXIT]], label [[IF_END_I:%.*]]
+; CHECK:       if.end.i:
+; CHECK-NEXT:    br i1 [[PRED13:%.*]], label [[EXIT]], label [[IF_END8_I:%.*]]
+; CHECK:       if.end8.i:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[WHILE_COND47]] ], [ true, [[WHILE_COND]] ], [ false, [[LOR_RHS]] ]
+; CHECK-NEXT:    br i1 [[GUARD_COND_TRUE49]], label [[COND_TRUE49:%.*]], label [[COND_END61:%.*]]
+;
+entry:
+  br i1 %Pred0, label %if.end, label %if.then
+
+if.end:
+  br i1 %Pred1, label %if.then7, label %if.else
+
+if.then7:
+  br label %if.end16
+
+if.else:
+  br label %if.end16
+
+if.end16:
+  br i1 %Pred2, label %while.cond.preheader, label %if.then39
+
+while.cond.preheader:
+  br label %while.cond
+
+while.cond:
+  br i1 %Pred3, label %cond.true49, label %lor.rhs
+
+cond.true49:
+  br i1 %Pred4, label %if.then69, label %while.body63
+
+while.body63:
+  br i1 %Pred5, label %exit, label %while.cond47
+
+while.cond47:
+  br i1 %Pred6, label %cond.true49, label %cond.end61
+
+cond.end61:
+  br i1 %Pred7, label %while.body63, label %while.cond
+
+if.then69:
+  br i1 %Pred8, label %exit, label %while.cond
+
+lor.rhs:
+  br i1 %Pred9, label %cond.end61, label %while.end76
+
+while.end76:
+  br label %exit
+
+if.then39:
+  br i1 %Pred10, label %exit, label %if.end.i145
+
+if.end.i145:
+  br i1 %Pred11, label %exit, label %if.end8.i149
+
+if.end8.i149:
+  br label %exit
+
+if.then:
+  br i1 %Pred12, label %exit, label %if.end.i
+
+if.end.i:
+  br i1 %Pred13, label %exit, label %if.end8.i
+
+if.end8.i:
+  br label %exit
+
+exit:
+  ret void
+}

llvm/test/Transforms/FixIrreducible/switch.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -fix-irreducible -S | FileCheck %s
+
+define void @loop_1(i32 %Value, i1 %PredEntry, i1 %PredD) {
+; CHECK-LABEL: @loop_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br label [[IRR_GUARD]]
+; CHECK:       B:
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VALUE:%.*]], 1
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[LEAFBLOCK1:%.*]]
+; CHECK:       LeafBlock1:
+; CHECK-NEXT:    [[SWITCHLEAF2:%.*]] = icmp eq i32 [[VALUE]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF2]], label [[IRR_GUARD]], label [[NEWDEFAULT:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VALUE]], 0
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[IRR_GUARD]], label [[NEWDEFAULT]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_A:%.*]] = phi i1 [ true, [[LEAFBLOCK]] ], [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ false, [[LEAFBLOCK1]] ], [ false, [[A:%.*]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A]], label [[A]], label [[B:%.*]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %B
+
+A:
+  br label %B
+
+B:
+  switch i32 %Value, label %exit [
+  i32 0, label %A
+  i32 1, label %B
+  ]
+
+exit:
+  ret void
+}

llvm/test/Transforms/StructurizeCFG/workarounds/needs-fix-reducible.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -fix-irreducible -structurizecfg -S | FileCheck %s
+
+; Both B1 and B4 are headers of an irreducible cycle. But in the
+; structurized version, B1 dominates B4. The program is structurized
+; correctly when the irreducible cycle is fixed.
+
+define void @irreducible(i1 %PredEntry, i1 %PredB1, i1 %PredB2, i1 %PredB3, i1 %PredB4)
+; CHECK-LABEL: @irreducible(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PREDB2_INV:%.*]] = xor i1 [[PREDB2:%.*]], true
+; CHECK-NEXT:    [[PREDB1_INV:%.*]] = xor i1 [[PREDB1:%.*]], true
+; CHECK-NEXT:    br label [[IRR_GUARD:%.*]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ [[PREDB4:%.*]], [[B4:%.*]] ], [ false, [[IRR_GUARD]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ false, [[B4]] ], [ true, [[IRR_GUARD]] ]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[B1:%.*]], label [[FLOW1:%.*]]
+; CHECK:       B1:
+; CHECK-NEXT:    br label [[FLOW1]]
+; CHECK:       Flow1:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[PREDB1_INV]], [[B1]] ], [ [[TMP0]], [[FLOW:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[B2:%.*]], label [[FLOW2:%.*]]
+; CHECK:       B2:
+; CHECK-NEXT:    br i1 [[PREDB2_INV]], label [[B3:%.*]], label [[FLOW3:%.*]]
+; CHECK:       Flow2:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP4:%.*]], [[FLOW3]] ], [ true, [[FLOW1]] ]
+; CHECK-NEXT:    br i1 [[TMP3]], label [[EXIT:%.*]], label [[IRR_GUARD]]
+; CHECK:       B3:
+; CHECK-NEXT:    br label [[FLOW3]]
+; CHECK:       B4:
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow3:
+; CHECK-NEXT:    [[TMP4]] = phi i1 [ false, [[B3]] ], [ true, [[B2]] ]
+; CHECK-NEXT:    br label [[FLOW2]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_B1:%.*]] = phi i1 [ [[PREDENTRY:%.*]], [[ENTRY:%.*]] ], [ [[PREDB3:%.*]], [[FLOW2]] ]
+; CHECK-NEXT:    [[TMP5:%.*]] = xor i1 [[GUARD_B1]], true
+; CHECK-NEXT:    br i1 [[TMP5]], label [[B4]], label [[FLOW]]
+;
+{
+entry:
+  br i1 %PredEntry, label %B1, label %B4
+
+B1:
+  br i1 %PredB1, label %exit, label %B2
+
+B2:
+  br i1 %PredB2, label %exit, label %B3
+
+B3:
+  br i1 %PredB3, label %B1, label %B4
+
+B4:
+  br i1 %PredB4, label %B2, label %exit
+
+exit:
+  ret void
+}

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -fix-irreducible -unify-loop-exits -structurizecfg -S | FileCheck %s
+define void @irreducible_mountain_bug(i1 %Pred0, i1 %Pred1, i1 %Pred2, i1 %Pred3, i1 %Pred4, i1 %Pred5, i1 %Pred6, i1 %Pred7, i1 %Pred8, i1 %Pred9, i1 %Pred10, i1 %Pred11, i1 %Pred12, i1 %Pred13) {
+; CHECK-LABEL: @irreducible_mountain_bug(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PRED0_INV:%.*]] = xor i1 [[PRED0:%.*]], true
+; CHECK-NEXT:    [[PRED1_INV:%.*]] = xor i1 [[PRED1:%.*]], true
+; CHECK-NEXT:    [[PRED2_INV:%.*]] = xor i1 [[PRED2:%.*]], true
+; CHECK-NEXT:    [[PRED3_INV:%.*]] = xor i1 [[PRED3:%.*]], true
+; CHECK-NEXT:    [[PRED5_INV:%.*]] = xor i1 [[PRED5:%.*]], true
+; CHECK-NEXT:    [[PRED4_INV:%.*]] = xor i1 [[PRED4:%.*]], true
+; CHECK-NEXT:    [[PRED10_INV:%.*]] = xor i1 [[PRED10:%.*]], true
+; CHECK-NEXT:    [[PRED11_INV:%.*]] = xor i1 [[PRED11:%.*]], true
+; CHECK-NEXT:    [[PRED12_INV:%.*]] = xor i1 [[PRED12:%.*]], true
+; CHECK-NEXT:    [[PRED13_INV:%.*]] = xor i1 [[PRED13:%.*]], true
+; CHECK-NEXT:    br i1 [[PRED0_INV]], label [[IF_THEN:%.*]], label [[FLOW18:%.*]]
+; CHECK:       Flow18:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[FLOW3:%.*]] ], [ true, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP0]], label [[IF_END:%.*]], label [[FLOW19:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br i1 [[PRED1_INV]], label [[IF_ELSE:%.*]], label [[FLOW17:%.*]]
+; CHECK:       Flow17:
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ false, [[IF_ELSE]] ], [ true, [[IF_END]] ]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[IF_THEN7:%.*]], label [[IF_END16:%.*]]
+; CHECK:       if.then7:
+; CHECK-NEXT:    br label [[IF_END16]]
+; CHECK:       if.else:
+; CHECK-NEXT:    br label [[FLOW17]]
+; CHECK:       Flow19:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       if.end16:
+; CHECK-NEXT:    br i1 [[PRED2_INV]], label [[IF_THEN39:%.*]], label [[FLOW15:%.*]]
+; CHECK:       Flow15:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ true, [[IF_END16]] ]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[WHILE_COND_PREHEADER:%.*]], label [[FLOW16:%.*]]
+; CHECK:       while.cond.preheader:
+; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
+; CHECK:       Flow16:
+; CHECK-NEXT:    br label [[FLOW19]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    br i1 [[PRED3_INV]], label [[LOR_RHS:%.*]], label [[FLOW11:%.*]]
+; CHECK:       Flow7:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[PRED7:%.*]], [[COND_END61:%.*]] ], [ false, [[IRR_GUARD:%.*]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ false, [[COND_END61]] ], [ true, [[IRR_GUARD]] ]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[COND_TRUE49:%.*]], label [[FLOW8:%.*]]
+; CHECK:       cond.true49:
+; CHECK-NEXT:    br label [[FLOW8]]
+; CHECK:       Flow8:
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ false, [[COND_TRUE49]] ], [ true, [[FLOW7:%.*]] ]
+; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ [[PRED4_INV]], [[COND_TRUE49]] ], [ [[TMP3]], [[FLOW7]] ]
+; CHECK-NEXT:    br i1 [[TMP6]], label [[WHILE_BODY63:%.*]], label [[FLOW9:%.*]]
+; CHECK:       while.body63:
+; CHECK-NEXT:    br i1 [[PRED5_INV]], label [[WHILE_COND47:%.*]], label [[FLOW10:%.*]]
+; CHECK:       Flow9:
+; CHECK-NEXT:    [[TMP7:%.*]] = phi i1 [ true, [[FLOW10]] ], [ false, [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP8:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP5]], [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ [[TMP18:%.*]], [[FLOW10]] ], [ true, [[FLOW8]] ]
+; CHECK-NEXT:    [[TMP10:%.*]] = xor i1 [[TMP7]], true
+; CHECK-NEXT:    [[TMP11:%.*]] = xor i1 [[TMP8]], true
+; CHECK-NEXT:    br i1 [[TMP9]], label [[LOOP_EXIT_GUARD1:%.*]], label [[IRR_GUARD]]
+; CHECK:       while.cond47:
+; CHECK-NEXT:    br label [[FLOW10]]
+; CHECK:       cond.end61:
+; CHECK-NEXT:    br label [[FLOW7]]
+; CHECK:       Flow13:
+; CHECK-NEXT:    [[TMP12:%.*]] = phi i1 [ false, [[FLOW14:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    [[TMP13:%.*]] = phi i1 [ [[TMP17:%.*]], [[FLOW14]] ], [ [[TMP11]], [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    br label [[FLOW12:%.*]]
+; CHECK:       if.then69:
+; CHECK-NEXT:    br label [[FLOW14]]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    br label [[FLOW11]]
+; CHECK:       while.end76:
+; CHECK-NEXT:    br label [[FLOW6:%.*]]
+; CHECK:       if.then39:
+; CHECK-NEXT:    br i1 [[PRED10_INV]], label [[IF_END_I145:%.*]], label [[FLOW5]]
+; CHECK:       if.end.i145:
+; CHECK-NEXT:    br i1 [[PRED11_INV]], label [[IF_END8_I149:%.*]], label [[FLOW4:%.*]]
+; CHECK:       if.end8.i149:
+; CHECK-NEXT:    br label [[FLOW4]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br i1 [[PRED12_INV]], label [[IF_END_I:%.*]], label [[FLOW3]]
+; CHECK:       if.end.i:
+; CHECK-NEXT:    br i1 [[PRED13_INV]], label [[IF_END8_I:%.*]], label [[FLOW:%.*]]
+; CHECK:       if.end8.i:
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow:
+; CHECK-NEXT:    br label [[FLOW3]]
+; CHECK:       Flow3:
+; CHECK-NEXT:    br label [[FLOW18]]
+; CHECK:       Flow4:
+; CHECK-NEXT:    br label [[FLOW5]]
+; CHECK:       Flow5:
+; CHECK-NEXT:    br label [[FLOW15]]
+; CHECK:       Flow6:
+; CHECK-NEXT:    br label [[FLOW16]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       Flow11:
+; CHECK-NEXT:    [[TMP14:%.*]] = phi i1 [ false, [[LOR_RHS]] ], [ true, [[WHILE_COND]] ]
+; CHECK-NEXT:    [[TMP15:%.*]] = phi i1 [ [[PRED9:%.*]], [[LOR_RHS]] ], [ [[PRED3]], [[WHILE_COND]] ]
+; CHECK-NEXT:    br i1 [[TMP15]], label [[IRR_GUARD]], label [[FLOW12]]
+; CHECK:       irr.guard:
+; CHECK-NEXT:    [[GUARD_COND_TRUE49:%.*]] = phi i1 [ [[PRED6:%.*]], [[FLOW9]] ], [ [[TMP14]], [[FLOW11]] ]
+; CHECK-NEXT:    [[TMP16:%.*]] = xor i1 [[GUARD_COND_TRUE49]], true
+; CHECK-NEXT:    br i1 [[TMP16]], label [[COND_END61]], label [[FLOW7]]
+; CHECK:       Flow14:
+; CHECK-NEXT:    [[TMP17]] = phi i1 [ [[PRED8:%.*]], [[IF_THEN69:%.*]] ], [ [[TMP11]], [[LOOP_EXIT_GUARD2:%.*]] ]
+; CHECK-NEXT:    br label [[FLOW13:%.*]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    br i1 [[TMP19:%.*]], label [[WHILE_END76:%.*]], label [[FLOW6]]
+; CHECK:       Flow10:
+; CHECK-NEXT:    [[TMP18]] = phi i1 [ false, [[WHILE_COND47]] ], [ true, [[WHILE_BODY63]] ]
+; CHECK-NEXT:    br label [[FLOW9]]
+; CHECK:       Flow12:
+; CHECK-NEXT:    [[TMP19]] = phi i1 [ [[TMP12]], [[FLOW13]] ], [ true, [[FLOW11]] ]
+; CHECK-NEXT:    [[TMP20:%.*]] = phi i1 [ [[TMP13]], [[FLOW13]] ], [ true, [[FLOW11]] ]
+; CHECK-NEXT:    br i1 [[TMP20]], label [[LOOP_EXIT_GUARD:%.*]], label [[WHILE_COND]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br i1 [[TMP11]], label [[LOOP_EXIT_GUARD2]], label [[FLOW13]]
+; CHECK:       loop.exit.guard2:
+; CHECK-NEXT:    br i1 [[TMP10]], label [[IF_THEN69]], label [[FLOW14]]
+;
+entry:
+  br i1 %Pred0, label %if.end, label %if.then
+
+if.end:
+  br i1 %Pred1, label %if.then7, label %if.else
+
+if.then7:
+  br label %if.end16
+
+if.else:
+  br label %if.end16
+
+if.end16:
+  br i1 %Pred2, label %while.cond.preheader, label %if.then39
+
+while.cond.preheader:
+  br label %while.cond
+
+while.cond:
+  br i1 %Pred3, label %cond.true49, label %lor.rhs
+
+cond.true49:
+  br i1 %Pred4, label %if.then69, label %while.body63
+
+while.body63:
+  br i1 %Pred5, label %exit, label %while.cond47
+
+while.cond47:
+  br i1 %Pred6, label %cond.true49, label %cond.end61
+
+cond.end61:
+  br i1 %Pred7, label %while.body63, label %while.cond
+
+if.then69:
+  br i1 %Pred8, label %exit, label %while.cond
+
+lor.rhs:
+  br i1 %Pred9, label %cond.end61, label %while.end76
+
+while.end76:
+  br label %exit
+
+if.then39:
+  br i1 %Pred10, label %exit, label %if.end.i145
+
+if.end.i145:
+  br i1 %Pred11, label %exit, label %if.end8.i149
+
+if.end8.i149:
+  br label %exit
+
+if.then:
+  br i1 %Pred12, label %exit, label %if.end.i
+
+if.end.i:
+  br i1 %Pred13, label %exit, label %if.end8.i
+
+if.end8.i:
+  br label %exit
+
+exit:
+  ret void
+}