Introduce unify-loop-exits pass.

[sameerds]

Summary

For each natural loop with multiple exit blocks, this pass creates a
new block N such that all exiting blocks now branch to N, and then
control flow is redistributed to all the original exit blocks.

The bulk of the tranformation is a new function introduced in
BasicBlockUtils that an redirect control flow from a set of incoming
blocks to a set of outgoing blocks via a common "hub".

This is a useful workaround for a limitation in the structurizer which
incorrectly orders blocks when processing a nest of loops. This pass
bypasses that issue by ensuring that each natural loop is recognized
as a separate region. Since the structurizer is a region pass, it no
longer sees a nest of loops in a single region, and instead processes
each "level" in the nesting as a separate region.

The AMDGPU backend provides a new option to enable this pass before
the structurizer, which may eventually be enabled by default.

[arsenm]

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

395

Could use some ASCII art graphs?

[madhur13490]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

1144

What about modularizing this function a bit to make it more readable? I see some logical blocks in this function.

[madhur13490]

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

367

A better word may "Sink"?

[sameerds]

Addressed review comments:

1. New ascii art.
2. Split the large function CreateControlFlowHub into smaller functions.

[sameerds]

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

367

Not really. "Sink" would imply an end of a flow as opposed to "Source". This really is a hub where unrelated control flow paths are made to converge and then fanout again.

[sameerds]

Fixed the ascii art example to be correct in terms of SSA. The extra
edge from In1 to Out2 would be nice to have, but it breaks the
pre-condition that Def dominates Use.

[sameerds]

Bump!

[arsenm]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

175–192

Won't the verifier catch these after the pass anyway?

If not I think the all the verification calls should be moved to a separate function

[sameerds]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

175–192

This verification happens immediately after each loop is transformed, which is useful for reporting errors closer to where they occur. If we move the verification out of this function, the outer loop that calls this function could end up working on an invalid loop structure, and the errors reported would not be very useful.

[arsenm]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

33

This seem to ignore the existence of switches (and call_br, but we don't handle that at all). Should this add a dependency on LowerSwitch (and preserve it)? Also should add a switch test or two

153

Printing empty string?

155

single quotes

159

single quotes

[sameerds]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

33

@nhaehnle had mentioned at some point that requiring LowerSwitch via AnalysisUsage is not reliable. The structurizer seems to be the only pass in LLVM that seems to do that, which does not help my confidence at all.

155

Does this really matter? Seems terribly pedantic to me, and would be surprised to see this in any coding standard. At least nothing specific showed up when I search in the LLVM, Linux and GNU coding standards.

[sameerds]

Added a comment about requiring direct branches; removed an empty string from debug output

[arsenm]

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

33

Unreliable in what way? I know there was something like a circular dependence issue in the context of one of the other passes, that might not exist here. I would still try to add it here, and this should probably error if it encounters a switch or something

155

It's not really important, but they're not identical. The char version does save a function call vs. the string

[sameerds]

require and preserve lower-switch pass

[nhaehnle]

This mostly looks good to me. I have some comments questions that affect the correctness of the code (at least in general); most of the rest is suggestions for possible simplifications / minor improvements.

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

1151

How about: "These indicate that if the Hub is entered from InBB, then control is transferred to OutBB if the corresponding value is true."

This suggests a slight refactoring of the function to have an outer loop based on Incoming and then looking at the possible cases of the BranchInst terminator, to parallel the corresponding code in redirectIncomingToHub.

1175–1176

Since Inverted does not only contain inverted conditions, could you please consistently rename it? Maybe AllConditions?

1244–1257

Smart. I wonder if you could simplify this further by transposing the loops.

Basically, first create all the phis in a loop over the outgoing blocks.

Then in a separate loop nest, iterate over the Incoming blocks, then iterate over all outgoing phis, and add the appropriate condition. If you combine this with my comment in collectPredicates, it may even be quite suitable to merge the two functions into one. This could then elide the creation of the "OldPredicates" entirely. The code doesn't need that structure for anything else, do we? (I suppose this would require doing the redirectIncomingToHub later.)

1261

std::move?

1367–1368

Shouldn't there be an edge insertion from the last guard blocks to both the last and the second-last Outgoing block? What am I missing here?

llvm/lib/Transforms/Utils/Local.cpp

3034

I believe the not should be created directly after Inst instead of before its block's terminator, to ensure that the new instruction dominates everything that Inst dominates.

3039–3040

Same argument here: the not should be create at the *start* of the entry block rather than at the end.

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

140–142

I don't understand this argument. getExitingBlocks also goes through all blocks in the loop... since you need both exiting *and* exit blocks, you may as well loop over all blocks in the loop directly. Though I guess this approach is not too bad, either, just the comment is confusing. If you want to argue that getting the exiting blocks and then enumerating successors to find exits is cheaper than enumerating exits and then enumerating predecessors, I suppose there are two arguments to be made:

• Eliminating duplicates is more natural the way you're doing it
• Iterating over successors is more efficient than iterating over predecessors in LLVM IR

197

This should be guarded by #ifndef NDEBUG.

[nhaehnle]

A quick addendum to ask whether you've run this with LLVM_ENABLE_EXPENSIVE_CHECKS -- that's required to flush out any problems with the dom tree updates.

[sameerds]

review comments: reorder loops and merge the predicate logic

[sameerds]

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

1244–1257

That's brilliant! All three functions quickly collapsed into a single function now.

1367–1368

Yes, there should be, and there was one in the first version of this review. It got lost when I refactored into separate functions. This is fixed now. The whole thing manages to work correctly even if I "forget" to add any outgoing edge from the new guard blocks. My best guess is that the updater itself all new edges incident on a new node, and since I am updating the dom tree as late as possible, this always discovers all the new edges.

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

140–142

I assume you are okay with the call to getExitingBlocks. If I were to traverse the whole loop body myself, that would just duplicate functionality that's already easily available. I rewrote the comments for clarity.

197

Wrapped this in EXPENSIVE_CHECKS instead.

[sameerds]

clang-format

[nhaehnle]

Thanks, LGTM!

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

140–142

Yes.

197

Thanks.

llvm/include/llvm/InitializePasses.h

 void initializeTargetLibraryInfoWrapperPassPass(PassRegistry&);
 void initializeTargetPassConfigPass(PassRegistry&);
 void initializeTargetTransformInfoWrapperPassPass(PassRegistry&);
 void initializeThreadSanitizerLegacyPassPass(PassRegistry&);
 void initializeTwoAddressInstructionPassPass(PassRegistry&);
 void initializeTypeBasedAAWrapperPassPass(PassRegistry&);
 void initializeTypePromotionPass(PassRegistry&);
 void initializeUnifyFunctionExitNodesPass(PassRegistry&);
+void initializeUnifyLoopExitsPass(PassRegistry &);
 void initializeUnpackMachineBundlesPass(PassRegistry&);
 void initializeUnreachableBlockElimLegacyPassPass(PassRegistry&);
 void initializeUnreachableMachineBlockElimPass(PassRegistry&);
 void initializeVectorCombineLegacyPassPass(PassRegistry&);
 void initializeVerifierLegacyPassPass(PassRegistry&);
 void initializeVirtRegMapPass(PassRegistry&);
 void initializeVirtRegRewriterPass(PassRegistry&);
 void initializeWarnMissedTransformationsLegacyPass(PassRegistry &);

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createMemDerefPrinter();
       (void) llvm::createMustExecutePrinter();
       (void) llvm::createMustBeExecutedContextPrinter();
       (void) llvm::createFloat2IntPass();
       (void) llvm::createEliminateAvailableExternallyPass();
       (void) llvm::createScalarizeMaskedMemIntrinPass();
       (void) llvm::createWarnMissedTransformationsPass();
       (void) llvm::createHardwareLoopsPass();
-      (void)llvm::createInjectTLIMappingsLegacyPass();
+      (void) llvm::createInjectTLIMappingsLegacyPass();
+      (void) llvm::createUnifyLoopExitsPass();
 
       (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

 FunctionPass *createControlHeightReductionLegacyPass();
 
 //===----------------------------------------------------------------------===//
 //
 // InjectTLIMappingsLegacy - populates the VFABI attribute with the
 // scalar-to-vector mappings from the TargetLibraryInfo.
 //
 FunctionPass *createInjectTLIMappingsLegacyPass();
+
+//===----------------------------------------------------------------------===//
+//
+// 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();
 }
 
 #endif

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

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
 #define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H
 
 // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/InstrTypes.h"
 #include <cassert>
 
 namespace llvm {
 

 // and D1 is the D block body. We can then duplicate D0 as D0A and D0B, and
 // create the following structure:
 // A -> D0A, B -> D0A, I -> D0B, D0A -> D1, D0B -> D1
 // If BPI and BFI aren't non-null, BPI/BFI will be updated accordingly.
 bool SplitIndirectBrCriticalEdges(Function &F,
                                   BranchProbabilityInfo *BPI = nullptr,
                                   BlockFrequencyInfo *BFI = nullptr);
 
+/// Given a set of incoming and outgoing blocks, create a "hub" such that every
+/// edge from an incoming block InBB to an outgoing block OutBB is now split
+/// into two edges, one from InBB to the hub and another from the hub to
+/// OutBB. The hub consists of a series of guard blocks, one for each outgoing
+/// block. Each guard block conditionally branches to the corresponding outgoing
+/// block, or the next guard block in the chain. These guard blocks are returned
+/// in the argument vector.
+///
+/// Since the control flow edges from InBB to OutBB have now been replaced, the
+/// function also updates any PHINodes in OutBB. For each such PHINode, the
+/// operands corresponding to incoming blocks are moved to a new PHINode in the
+/// hub, and the hub is made an operand of the original PHINode.
+///
+/// Input CFG:
+/// ----------
+///
+///                      Def
+///                       |
+///                       v
+///            In1       In2
+///            |  \       |
+///            |   \      |
+///            v    \     v
+///  Foo ---> Out1   `-> Out2
+///                       |
+///                       v
+///                      Use
+///
+///
+/// Create hub: Incoming = {In1, In2}, Outgoing = {Out1, Out2}
+/// ----------------------------------------------------------
+///
+///             Def
+///              |
+///              v
+///  In1        In2          Foo
+///   |    Hub   |            |
+///   |    + - - | - - +      |
+///   |    '     v     '      V
+///   +------> Guard1 -----> Out1
+///        '     |     '
+///        '     v     '
+///        '   Guard2 -----> Out2
+///        '           '      |
+///        + - - - - - +      |
+///                           v
+///                          Use
+///
+/// Limitation:
+/// -----------
+/// The updates to the PHINodes are not sufficient to restore SSA form. Consider
+/// a definition Def, its use Use, incoming block In2 and outgoing block Out2,
+/// such that:
+/// 1. In2 is reachable from D or contains D.
+/// 2. U is reachable from Out2 or is contained in Out2.
+/// 3. U is not a PHINode if U is contained in Out2.
+///
+/// Clearly, Def dominates Out2 since the program is valid SSA. But when the hub
+/// is introduced, there is a new path through the hub along which Use is
+/// reachable from entry without passing through Def, and SSA is no longer
+/// valid. To fix this, we need to look at all the blocks post-dominated by the
+/// hub on the one hand, and dominated by Out2 on the other. This is left for
+/// the caller to accomplish, since each specific use of this function may have
+/// additional information which simplifies this fixup. For example, see
+/// restoreSSA() in the UnifyLoopExits pass.
+BasicBlock *CreateControlFlowHub(DomTreeUpdater *DTU,
+                                 SmallVectorImpl<BasicBlock *> &GuardBlocks,
+                                 const SetVector<BasicBlock *> &Predecessors,
+                                 const SetVector<BasicBlock *> &Successors,
+                                 const StringRef Prefix);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H

llvm/include/llvm/Transforms/Utils/Local.h

 //===----------------------------------------------------------------------===//
 //  Transform predicates
 //
 
 /// Given an instruction, is it legal to set operand OpIdx to a non-constant
 /// value?
 bool canReplaceOperandWithVariable(const Instruction *I, unsigned OpIdx);
 
+//===----------------------------------------------------------------------===//
+//  Value helper functions
+//
+
+/// Invert the given true/false value, possibly reusing an existing copy.
+Value *invertCondition(Value *Condition);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_LOCAL_H

llvm/lib/Target/AMDGPU/AMDGPUTargetMachine.cpp

EnableDCEInRA("amdgpu-dce-in-ra",
     cl::desc("Enable machine DCE inside regalloc"));
 
 static cl::opt<bool> EnableScalarIRPasses(
   "amdgpu-scalar-ir-passes",
   cl::desc("Enable scalar IR passes"),
   cl::init(true),
   cl::Hidden);
 
+static cl::opt<bool> EnableStructurizerWorkarounds(
+    "amdgpu-enable-structurizer-workarounds",
+    cl::desc("Enable workarounds for the StructurizeCFG pass"), cl::init(false),
+    cl::Hidden);
+
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeAMDGPUTarget() {
   // Register the target
   RegisterTargetMachine<R600TargetMachine> X(getTheAMDGPUTarget());
   RegisterTargetMachine<GCNTargetMachine> Y(getTheGCNTarget());
 
   PassRegistry *PR = PassRegistry::getPassRegistry();
   initializeR600ClauseMergePassPass(*PR);
   initializeR600ControlFlowFinalizerPass(*PR);
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(createUnifyLoopExitsPass());
+    }
     addPass(createStructurizeCFGPass(true)); // true -> SkipUniformRegions
   }
   addPass(createSinkingPass());
   addPass(createAMDGPUAnnotateUniformValues());
   if (!LateCFGStructurize) {
     addPass(createSIAnnotateControlFlowPass());
   }
   addPass(createLCSSAPass());

llvm/lib/Transforms/Scalar/StructurizeCFG.cpp

 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include <algorithm>
 #include <cassert>
 #include <utility>
 
 using namespace llvm;
 using namespace llvm::PatternMatch;
 
class StructurizeCFG : public RegionPass {
 
   void orderNodes();
 
   Loop *getAdjustedLoop(RegionNode *RN);
   unsigned getAdjustedLoopDepth(RegionNode *RN);
 
   void analyzeLoops(RegionNode *N);
 
-  Value *invert(Value *Condition);
-
   Value *buildCondition(BranchInst *Term, unsigned Idx, bool Invert);
 
   void gatherPredicates(RegionNode *N);
 
   void collectInfos();
 
   void insertConditions(bool Loops);
 
if (N->isSubRegion()) {
     BranchInst *Term = cast<BranchInst>(BB->getTerminator());
 
     for (BasicBlock *Succ : Term->successors())
       if (Visited.count(Succ))
         Loops[Succ] = BB;
   }
 }
 
-/// Invert the given condition
-Value *StructurizeCFG::invert(Value *Condition) {
-  // First: Check if it's a constant
-  if (Constant *C = dyn_cast<Constant>(Condition))
-    return ConstantExpr::getNot(C);
-
-  // Second: If the condition is already inverted, return the original value
-  Value *NotCondition;
-  if (match(Condition, m_Not(m_Value(NotCondition))))
-    return NotCondition;
-
-  if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
-    // Third: Check all the users for an invert
-    BasicBlock *Parent = Inst->getParent();
-    for (User *U : Condition->users())
-      if (Instruction *I = dyn_cast<Instruction>(U))
-        if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
-          return I;
-
-    // Last option: Create a new instruction
-    return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator());
-  }
-
-  if (Argument *Arg = dyn_cast<Argument>(Condition)) {
-    BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
-    return BinaryOperator::CreateNot(Condition,
-                                     Arg->getName() + ".inv",
-                                     EntryBlock.getTerminator());
-  }
-
-  llvm_unreachable("Unhandled condition to invert");
-}
-
 /// Build the condition for one edge
 Value *StructurizeCFG::buildCondition(BranchInst *Term, unsigned Idx,
                                       bool Invert) {
   Value *Cond = Invert ? BoolFalse : BoolTrue;
   if (Term->isConditional()) {
     Cond = Term->getCondition();
 
     if (Idx != (unsigned)Invert)
-      Cond = invert(Cond);
+      Cond = invertCondition(Cond);
   }
   return Cond;
 }
 
 /// Analyze the predecessors of each block and build up predicates
 void StructurizeCFG::gatherPredicates(RegionNode *N) {
   RegionInfo *RI = ParentRegion->getRegionInfo();
   BasicBlock *BB = N->getEntry();

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

if (BI->getSuccessor(0) == Pred1) {
     IfTrue = Pred1;
     IfFalse = Pred2;
   } else {
     IfTrue = Pred2;
     IfFalse = Pred1;
   }
   return BI->getCondition();
 }
+
+// After creating a control flow hub, the operands of PHINodes in an outgoing
+// block Out no longer match the predecessors of that block. Predecessors of Out
+// that are incoming blocks to the hub are now replaced by just one edge from
+// the hub. To match this new control flow, the corresponding values from each
+// PHINode must now be moved a new PHINode in the first guard block of the hub.
+//
+// This operation cannot be performed with SSAUpdater, because it involves one
+// new use: If the block Out is in the list of Incoming blocks, then the newly
+// created PHI in the Hub will use itself along that edge from Out to Hub.
+static void reconnectPhis(BasicBlock *Out, BasicBlock *GuardBlock,
+                          const SetVector<BasicBlock *> &Incoming,
+                          BasicBlock *FirstGuardBlock) {
+  auto I = Out->begin();
+  while (I != Out->end() && isa<PHINode>(I)) {
+    auto Phi = cast<PHINode>(I);
+    auto NewPhi =
+        PHINode::Create(Phi->getType(), Incoming.size(),
+                        Phi->getName() + ".moved", &FirstGuardBlock->back());
+    for (auto In : Incoming) {
+      Value *V = UndefValue::get(Phi->getType());
+      if (In == Out) {
+        V = NewPhi;
+      } else if (Phi->getBasicBlockIndex(In) != -1) {
+        V = Phi->removeIncomingValue(In, false);
+      }
+      NewPhi->addIncoming(V, In);
+    }
+    assert(NewPhi->getNumIncomingValues() == Incoming.size());
+    if (Phi->getNumOperands() == 0) {
+      Phi->replaceAllUsesWith(NewPhi);
+      I = Phi->eraseFromParent();
+      continue;
+    }
+    Phi->addIncoming(NewPhi, GuardBlock);
+    ++I;
+  }
+}
+
+using BBPredicates = DenseMap<BasicBlock *, Value *>;
+using PredMap = DenseMap<BasicBlock *, BBPredicates>;
+using BBSetVector = SetVector<BasicBlock *>;
+
+// Collect predicates for each outgoing block:
+// OutBB x InBB -> Value
+//
+// These are used by the Hub to transfer control to the outgoing blocks.
+static void collectPredicates(PredMap &Predicates,
+                              SmallVectorImpl<WeakVH> &Inverted,
+                              const BBSetVector &Incoming,
+                              const BBSetVector &Outgoing) {
+  auto &Context = Incoming.front()->getContext();
+  auto BoolTrue = ConstantInt::getTrue(Context);
+
+  for (auto Out : Outgoing) {
+    for (auto In : predecessors(Out)) {
+      if (!Incoming.count(In))
+        continue;
+      auto Branch = cast<BranchInst>(In->getTerminator());
+      if (!Branch->isConditional()) {
+        Predicates[Out][In] = BoolTrue;
+        continue;
+      }
+      auto Condition = Branch->getCondition();
+      if (Branch->getSuccessor(0) == Out) {
+        Predicates[Out][In] = Condition;
+        continue;
+      }
+      auto Inv = invertCondition(Condition);
+      Predicates[Out][In] = Inv;
+      Inverted.push_back(Inv);
+      Inverted.push_back(Condition);
+    }
+  }
+
+  // Optimization: For each incoming block with a conditional branch, where only
+  // one successor is in an outgoing block, the predicate is always true.
+  for (auto In : Incoming) {
+    auto Branch = cast<BranchInst>(In->getTerminator());
+    if (!Branch->isConditional())
+      continue;
+    auto Succ0 = Branch->getSuccessor(0);
+    auto Succ1 = Branch->getSuccessor(1);
+    if (Outgoing.count(Succ0) && !Outgoing.count(Succ1)) {
+      Predicates[Succ0][In] = BoolTrue;
+    } else if (Outgoing.count(Succ1) && !Outgoing.count(Succ0)) {
+      Predicates[Succ1][In] = BoolTrue;
+    }
+  }
+}
+
+static void redirectIncomingToHub(const BBSetVector &Incoming,
+                                  const BBSetVector &Outgoing,
+                                  BasicBlock *FirstGuardBlock) {
+  // Replace the appropriate successors of each incoming block with the Hub.
+  for (auto In : Incoming) {
+    auto Branch = cast<BranchInst>(In->getTerminator());
+    if (!Branch->isConditional()) {
+      Branch->setSuccessor(0, FirstGuardBlock);
+      continue;
+    }
+    auto Succ0 = Branch->getSuccessor(0);
+    auto Succ1 = Branch->getSuccessor(1);
+    if (Outgoing.count(Succ0)) {
+      if (Outgoing.count(Succ1)) {
+        Branch->eraseFromParent();
+        BranchInst::Create(FirstGuardBlock, In);
+        continue;
+      }
+      Branch->setSuccessor(0, FirstGuardBlock);
+      continue;
+    }
+    assert(Outgoing.count(Succ1));
+    Branch->setSuccessor(1, FirstGuardBlock);
+  }
+}
+
+// Create one guard predicate in FirstGuardBlock for each outgoing block, that
+// decides whether control should flow to that block. This guard is a Boolean
+// PHINode over the predicates previously stored for that block.
+static void createGuardPredicates(BBPredicates &GuardPredicates,
+                                  PredMap &OldPredicates,
+                                  const BBSetVector &Incoming,
+                                  const BBSetVector &Outgoing,
+                                  BasicBlock *FirstGuardBlock) {
+  auto &Context = Incoming.front()->getContext();
+  auto BoolTrue = ConstantInt::getTrue(Context);
+  auto BoolFalse = ConstantInt::getFalse(Context);
+
+  // The predicate for the last successor 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;
+
+    // Optimization: Consider an incoming block A with both successors B1 and B2
+    // in the set of outgoing blocks. The predicates for B1 and B2 complement
+    // each other. If B1 is visited first in the loop below, control will branch
+    // to B1 using the corresponding predicate. But if that branch is not taken,
+    // then control must reach B2, which means that the predicate for B2 is
+    // always true. This optimization is performed as follows:
+    // 1. At each iteration, drop the predicates for the current outgoing block.
+    // 2. If the current block has a non-constant predicate, then it's sibling
+    //    has not been visited yet. Locate the sibling by matching the incoming
+    //    block in the remaining predicates. Only one other outgoing block can
+    //    have the same incoming block as a predecessor.
+    // 3. Unconditionally set the predicate of the sibling to "true". This also
+    //    ensures that step 2 is not attempted when this sibling is visited.
+    //
+    // Besides being a minor optimization, this improves the readability of the
+    // IR and also allows us to later assert the claim that the last successor
+    // has a trivially true predicate.
+    auto Preds = OldPredicates[Out];
+    OldPredicates.erase(Out);
+    for (auto In : Incoming) {
+      auto Predicate = Preds.count(In) ? Preds[In] : BoolFalse;
+      Phi->addIncoming(Predicate, In);
+      if (isa<Constant>(Predicate)) {
+        continue;
+      }
+      bool Found = false;
+      for (auto &OtherPreds : OldPredicates) {
+        if (OtherPreds.second.count(In)) {
+          auto &X = OtherPreds.second[In];
+          assert(!isa<Constant>(X));
+          X = BoolTrue;
+          Found = true;
+          break;
+        }
+      }
+      assert(Found);
+    }
+  }
+
+#ifndef NDEBUG
+  // Assert the original claim that the guard predicate for the last block is
+  // trivially true.
+  auto Last = Outgoing.back();
+  assert(OldPredicates.count(Last));
+  assert(OldPredicates.size() == 1);
+  auto &LastPreds = OldPredicates[Last];
+  for (auto P : LastPreds) {
+    assert(P.second == BoolTrue);
+  }
+#endif // NDEBUG
+}
+
+static void createGuardBlocks(SmallVectorImpl<BasicBlock *> &GuardBlocks,
+                              Function *F, const BBSetVector &Outgoing,
+                              BBPredicates &GuardPredicates, StringRef Prefix) {
+  // The last guard block can have two outgoing blocks as successors, since the
+  // condition for the final outgoing block is trivially true. So we create one
+  // less block (including the Hub) than the number of outgoing blocks.
+  for (int i = 0, e = Outgoing.size() - 2; i != e; ++i) {
+    GuardBlocks.push_back(
+        BasicBlock::Create(F->getContext(), Prefix + ".guard", F));
+  }
+  assert(GuardBlocks.size() == GuardPredicates.size());
+
+  // To help keep the loop simple, temporarily append the last outgoing block to
+  // the list of guard blocks.
+  GuardBlocks.push_back(Outgoing.back());
+
+  for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
+    auto Out = Outgoing[i];
+    assert(GuardPredicates.count(Out));
+    BranchInst::Create(Out, GuardBlocks[i + 1], GuardPredicates[Out],
+                       GuardBlocks[i]);
+  }
+
+  // Remove the last block from the guard list.
+  GuardBlocks.pop_back();
+}
+
+BasicBlock *llvm::CreateControlFlowHub(
+    DomTreeUpdater *DTU, SmallVectorImpl<BasicBlock *> &GuardBlocks,
+    const BBSetVector &Incoming, const BBSetVector &Outgoing,
+    const StringRef Prefix) {
+  auto F = Incoming.front()->getParent();
+  auto FirstGuardBlock =
+      BasicBlock::Create(F->getContext(), Prefix + ".guard", F);
+
+  PredMap Predicates;
+  SmallVector<WeakVH, 8> Inverted;
+  collectPredicates(Predicates, Inverted, Incoming, Outgoing);
+
+  SmallVector<DominatorTree::UpdateType, 16> Updates;
+  if (DTU) {
+    for (auto In : Incoming) {
+      for (auto Succ : successors(In)) {
+        if (Outgoing.count(Succ))
+          Updates.push_back({DominatorTree::Delete, In, Succ});
+      }
+      Updates.push_back({DominatorTree::Insert, In, FirstGuardBlock});
+    }
+  }
+
+  redirectIncomingToHub(Incoming, Outgoing, FirstGuardBlock);
+
+  BBPredicates GuardPredicates;
+  createGuardPredicates(GuardPredicates, Predicates, Incoming, Outgoing,
+                        FirstGuardBlock);
+
+  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);
+  }
+  reconnectPhis(Outgoing.back(), GuardBlocks.back(), Incoming, FirstGuardBlock);
+
+  if (DTU) {
+    for (int i = 0, e = GuardBlocks.size() - 1; i != e; ++i) {
+      Updates.push_back({DominatorTree::Insert, GuardBlocks[i], Outgoing[i]});
+      Updates.push_back(
+          {DominatorTree::Insert, GuardBlocks[i], GuardBlocks[i + 1]});
+    }
+    Updates.push_back(
+        {DominatorTree::Insert, GuardBlocks.back(), Outgoing.back()});
+    DTU->applyUpdates(Updates);
+  }
+
+  for (auto I : Inverted) {
+    if (I->use_empty())
+      if (auto Inst = dyn_cast_or_null<Instruction>(I))
+        Inst->eraseFromParent();
+  }
+
+  return FirstGuardBlock;
+}

llvm/lib/Transforms/Utils/CMakeLists.txt

add_llvm_component_library(LLVMTransformUtils
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyLibCalls.cpp
   SizeOpts.cpp
   SplitModule.cpp
   StripNonLineTableDebugInfo.cpp
   SymbolRewriter.cpp
   UnifyFunctionExitNodes.cpp
+  UnifyLoopExits.cpp
   Utils.cpp
   ValueMapper.cpp
   VNCoercion.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms/Utils
 
   DEPENDS
   intrinsics_gen
   )

llvm/lib/Transforms/Utils/Local.cpp

AllocaInst *llvm::findAllocaForValue(Value *V,
   } else {
     LLVM_DEBUG(dbgs() << "Alloca search cancelled on unknown instruction: "
                       << *V << "\n");
   }
   if (Res)
     AllocaForValue[V] = Res;
   return Res;
 }
+
+Value *llvm::invertCondition(Value *Condition) {
+  // First: Check if it's a constant
+  if (Constant *C = dyn_cast<Constant>(Condition))
+    return ConstantExpr::getNot(C);
+
+  // Second: If the condition is already inverted, return the original value
+  Value *NotCondition;
+  if (match(Condition, m_Not(m_Value(NotCondition))))
+    return NotCondition;
+
+  if (Instruction *Inst = dyn_cast<Instruction>(Condition)) {
+    // Third: Check all the users for an invert
+    BasicBlock *Parent = Inst->getParent();
+    for (User *U : Condition->users())
+      if (Instruction *I = dyn_cast<Instruction>(U))
+        if (I->getParent() == Parent && match(I, m_Not(m_Specific(Condition))))
+          return I;
+
+    // Last option: Create a new instruction
+    return BinaryOperator::CreateNot(Condition, "", Parent->getTerminator());
+  }
+
+  if (Argument *Arg = dyn_cast<Argument>(Condition)) {
+    BasicBlock &EntryBlock = Arg->getParent()->getEntryBlock();
+    return BinaryOperator::CreateNot(Condition, Arg->getName() + ".inv",
+                                     EntryBlock.getTerminator());
+  }
+
+  llvm_unreachable("Unhandled condition to invert");
+}

llvm/lib/Transforms/Utils/UnifyLoopExits.cpp

+//===- UnifyLoopExits.cpp - Redirect exiting edges to one block -*- C++ -*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// For each natural loop with multiple exit blocks, this pass creates a new
+// block N such that all exiting blocks now branch to N, and then control flow
+// is redistributed to all the original exit blocks.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Transforms/Utils.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+
+#define DEBUG_TYPE "unify-loop-exits"
+
+using namespace llvm;
+
+namespace {
+struct UnifyLoopExits : public FunctionPass {
+  static char ID;
+  UnifyLoopExits() : FunctionPass(ID) {
+    initializeUnifyLoopExitsPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.addRequired<LoopInfoWrapperPass>();
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addPreserved<LoopInfoWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+  }
+
+  bool runOnFunction(Function &F);
+};
+} // namespace
+
+char UnifyLoopExits::ID = 0;
+
+FunctionPass *llvm::createUnifyLoopExitsPass() { return new UnifyLoopExits(); }
+
+INITIALIZE_PASS_BEGIN(UnifyLoopExits, "unify-loop-exits",
+                      "Fixup each natural loop to have a single exit block",
+                      false /* Only looks at CFG */, false /* Analysis Pass */)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(UnifyLoopExits, "unify-loop-exits",
+                    "Fixup each natural loop to have a single exit block",
+                    false /* Only looks at CFG */, false /* Analysis Pass */)
+
+// The current transform introduces new control flow paths which may break the
+// SSA requirement that every def must dominate all its uses. For example,
+// consider a value D defined inside the loop that is used by some instruction
+// U outside the loop. It follows that D dominates U, since the original
+// program has valid SSA form. After merging the exits, all paths from D to U
+// now flow through the unified exit block. In addition, there may be other
+// paths that do not pass through D, but now reach the unified exit
+// block. Thus, D no longer dominates U.
+//
+// Restore the dominance by creating a phi for each such D at the new unified
+// loop exit. But when doing this, ignore any uses U that are in the new unified
+// loop exit, since those were introduced specially when the block was created.
+//
+// The use of SSAUpdater seems like overkill for this operation. The location
+// for creating the new PHI is well-known, and also the set of incoming blocks
+// to the new PHI.
+static void restoreSSA(const DominatorTree &DT, const Loop *L,
+                       const SetVector<BasicBlock *> &Incoming,
+                       BasicBlock *LoopExitBlock) {
+  using InstVector = SmallVector<Instruction *, 8>;
+  using IIMap = DenseMap<Instruction *, InstVector>;
+  IIMap ExternalUsers;
+  for (auto BB : L->blocks()) {
+    for (auto &I : *BB) {
+      for (auto &U : I.uses()) {
+        auto UserInst = cast<Instruction>(U.getUser());
+        auto UserBlock = UserInst->getParent();
+        if (UserBlock == LoopExitBlock)
+          continue;
+        if (L->contains(UserBlock))
+          continue;
+        LLVM_DEBUG(dbgs()
+                   << "added ext use for " << I.getName() << "("
+                   << BB->getName() << ")"
+                   << ": " << UserInst->getName() << "(" << UserBlock->getName() << ")"
+                   << "\n");
+        ExternalUsers[&I].push_back(UserInst);
+      }
+    }
+  }
+
+  for (auto II : ExternalUsers) {
+    // For each Def used outside the loop, create NewPhi in
+    // LoopExitBlock. NewPhi receives Def only along exiting blocks that
+    // dominate it, while the remaining values are undefined since those paths
+    // didn't exist in the original CFG.
+    auto Def = II.first;
+    LLVM_DEBUG(dbgs() << "externally used: " << Def->getName() << "\n");
+    auto NewPhi = PHINode::Create(Def->getType(), Incoming.size(),
+                                  Def->getName() + ".moved",
+                                  LoopExitBlock->getTerminator());
+    for (auto In : Incoming) {
+      LLVM_DEBUG(dbgs() << "predecessor " << In->getName() << ": ");
+      if (Def->getParent() == In || DT.dominates(Def, In)) {
+        LLVM_DEBUG(dbgs() << "dominated\n");
+        NewPhi->addIncoming(Def, In);
+      } else {
+        LLVM_DEBUG(dbgs() << "not dominated\n");
+        NewPhi->addIncoming(UndefValue::get(Def->getType()), In);
+      }
+    }
+
+    LLVM_DEBUG(dbgs() << "external users:");
+    for (auto U : II.second) {
+      LLVM_DEBUG(dbgs() << " " << U->getName());
+      U->replaceUsesOfWith(Def, NewPhi);
+    }
+    LLVM_DEBUG(dbgs() << "\n");
+  }
+}
+
+static bool unifyLoopExits(DominatorTree &DT, LoopInfo &LI, Loop *L) {
+  // We need SetVectors, but the Loop API takes a vector, so we use a temporary.
+  SmallVector<BasicBlock *, 8> Temp;
+  L->getExitingBlocks(Temp);
+
+  // Locate exits by examining the successors of the exiting blocks. This is
+  // cheaper than calling Loop::getExitBlocks(), since that goes through the
+  // entire list of blocks in the loop.
+  SetVector<BasicBlock *> ExitingBlocks;
+  SetVector<BasicBlock *> Exits;
+  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);
+    }
+  }
+
+  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";);
+
+  if (Exits.size() <= 1) {
+    LLVM_DEBUG(dbgs() << "loop does not have multiple exits; nothing to do\n");
+    return false;
+  }
+
+  SmallVector<BasicBlock *, 8> GuardBlocks;
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
+  auto LoopExitBlock = CreateControlFlowHub(&DTU, GuardBlocks, ExitingBlocks,
+                                            Exits, "loop.exit");
+
+  restoreSSA(DT, L, ExitingBlocks, LoopExitBlock);
+
+#if defined(EXPENSIVE_CHECKS)
+  assert(DT.verify(DominatorTree::VerificationLevel::Full));
+#else
+  assert(DT.verify(DominatorTree::VerificationLevel::Fast));
+#endif
+  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);
+    }
+    ParentLoop->verifyLoop();
+  }
+  LI.verify(DT);
+
+  return true;
+}
+
+bool UnifyLoopExits::runOnFunction(Function &F) {
+  LLVM_DEBUG(dbgs() << "===== Unifying loop exits in function " << F.getName()
+                    << "\n");
+  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  bool Changed = false;
+  auto Loops = LI.getLoopsInPreorder();
+  for (auto L : Loops) {
+    LLVM_DEBUG(dbgs() << "Loop: " << L->getHeader()->getName() << " (depth: "
+                      << LI.getLoopDepth(L->getHeader()) << ")\n");
+    Changed |= unifyLoopExits(DT, LI, L);
+  }
+  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);
+  initializeUnifyLoopExitsPass(Registry);
 }
 
 /// LLVMInitializeTransformUtils - C binding for initializeTransformUtilsPasses.
 void LLVMInitializeTransformUtils(LLVMPassRegistryRef R) {
   initializeTransformUtils(*unwrap(R));
 }
 
 void LLVMAddLowerSwitchPass(LLVMPassManagerRef PM) {

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -unify-loop-exits -structurizecfg -S | FileCheck %s
+
+; The structurizer uses an RPO traversal over a region, along with a
+; manual hack that is meant to sort ensure that blocks within a loop
+; are all visited before visiting blocks outside the loop. But this
+; does not always work as expected. For example the results are
+; incorrect when multiple nested loops are involved.
+
+; The workaround for this is to unify loop exits. Each loop now
+; becomes an SESE region with a single header and a single exit. The
+; structurizer is a region pass, and it no longer sees the entire loop
+; nest in a single region. More importantly, for each loop, the only
+; block reachable outside the loop is the region exit, which avoids
+; any confusion in the hacked RPO traversal.
+
+; In the function below, B1 is an exiting block in outer loop H1. It's
+; successor inside the loop is the header of another loop H2. Due to
+; the incorrect traversal, B1 dominates all the blocks in the
+; structurized program, except the header H1.
+
+define void @exiting-block(i1 %PredH1, i1 %PredB2, i1 %PredB1, i1 %PredH2) {
+; CHECK-LABEL: @exiting-block(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PREDB2_INV:%.*]] = xor i1 [[PREDB2:%.*]], true
+; CHECK-NEXT:    [[PREDH1_INV:%.*]] = xor i1 [[PREDH1:%.*]], true
+; CHECK-NEXT:    br label [[H1:%.*]]
+; CHECK:       H1:
+; CHECK-NEXT:    br i1 [[PREDH1_INV]], label [[B1:%.*]], label [[FLOW3:%.*]]
+; CHECK:       Flow3:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ [[PREDB1:%.*]], [[B1]] ], [ [[PREDH1]], [[H1]] ]
+; CHECK-NEXT:    br i1 [[TMP0]], 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:    [[TMP1:%.*]] = phi i1 [ false, [[FLOW2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP4:%.*]], [[FLOW2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    br i1 [[TMP2]], 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:    [[TMP3:%.*]] = phi i1 [ false, [[L1:%.*]] ], [ true, [[LOOP_EXIT_GUARD1]] ]
+; CHECK-NEXT:    br label [[FLOW4]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    br i1 [[TMP5:%.*]], label [[C:%.*]], label [[EXIT]]
+; CHECK:       Flow2:
+; CHECK-NEXT:    [[TMP4]] = phi i1 [ false, [[L2]] ], [ true, [[B2]] ]
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow4:
+; CHECK-NEXT:    [[TMP5]] = phi i1 [ false, [[FLOW5]] ], [ true, [[FLOW3]] ]
+; CHECK-NEXT:    [[TMP6:%.*]] = phi i1 [ [[TMP3]], [[FLOW5]] ], [ true, [[FLOW3]] ]
+; CHECK-NEXT:    br i1 [[TMP6]], label [[LOOP_EXIT_GUARD:%.*]], label [[H1]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br i1 [[TMP1]], label [[L1]], label [[FLOW5]]
+;
+entry:
+  br label %H1
+
+H1:                                               ; preds = %L1, %entry
+  br i1 %PredH1, label %H2, label %B1
+
+H2:                                               ; preds = %B1, %L2, %H1
+  br i1 %PredH2, label %B2, label %L1
+
+B2:                                               ; preds = %H2
+  br i1 %PredB2, label %exit, label %L2
+
+L2:                                               ; preds = %B2
+  br label %H2
+
+L1:                                               ; preds = %H2
+  br label %H1
+
+B1:                                               ; preds = %H1
+  br i1 %PredB1, label %H2, label %C
+
+C:                                                ; preds = %B1
+  br label %exit
+
+exit:                                             ; preds = %C, %B2
+  ret void
+}
+
+; The function below has three nested loops. Due to the incorrect
+; traversal, H2 dominates H3 in the structurized program, and the
+; backedge from L13 to H3 has no equivalent path.
+
+define void @incorrect-backedge(i1 %PredH2, i1 %PredH3, i1 %PredL2, i1 %PredL13, i1 %PredL1)
+; CHECK-LABEL: @incorrect-backedge(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[PREDL13_INV:%.*]] = xor i1 [[PREDL13:%.*]], true
+; CHECK-NEXT:    [[PREDH3_INV:%.*]] = xor i1 [[PREDH3:%.*]], true
+; CHECK-NEXT:    [[PREDL2_INV:%.*]] = xor i1 [[PREDL2:%.*]], true
+; CHECK-NEXT:    [[PREDH2_INV:%.*]] = xor i1 [[PREDH2:%.*]], true
+; CHECK-NEXT:    br label [[H1:%.*]]
+; CHECK:       H1:
+; CHECK-NEXT:    br label [[H2:%.*]]
+; CHECK:       H2:
+; CHECK-NEXT:    br i1 [[PREDH2_INV]], label [[H3:%.*]], label [[FLOW4:%.*]]
+; CHECK:       H3:
+; CHECK-NEXT:    br i1 [[PREDH3_INV]], label [[L2:%.*]], label [[FLOW:%.*]]
+; CHECK:       L2:
+; CHECK-NEXT:    br i1 [[PREDL2_INV]], label [[L13:%.*]], label [[FLOW3:%.*]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP0:%.*]] = phi i1 [ false, [[FLOW3]] ], [ true, [[H3]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i1 [ [[TMP7:%.*]], [[FLOW3]] ], [ true, [[H3]] ]
+; CHECK-NEXT:    br i1 [[TMP2]], label [[LOOP_EXIT_GUARD2:%.*]], label [[H3]]
+; CHECK:       L13:
+; CHECK-NEXT:    br label [[FLOW3]]
+; CHECK:       Flow5:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i1 [ [[TMP8:%.*]], [[LOOP_EXIT_GUARD1:%.*]] ], [ true, [[LOOP_EXIT_GUARD:%.*]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD1]] ], [ true, [[LOOP_EXIT_GUARD]] ]
+; CHECK-NEXT:    br i1 [[TMP4]], label [[L1:%.*]], label [[FLOW6:%.*]]
+; CHECK:       L1:
+; CHECK-NEXT:    br label [[FLOW6]]
+; CHECK:       Flow6:
+; CHECK-NEXT:    [[TMP5:%.*]] = phi i1 [ [[PREDL1:%.*]], [[L1]] ], [ [[TMP3]], [[FLOW5:%.*]] ]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[EXIT:%.*]], label [[H1]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    br i1 [[TMP11:%.*]], label [[LOOP_EXIT_GUARD1]], label [[FLOW5]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br label [[FLOW5]]
+; CHECK:       Flow3:
+; CHECK-NEXT:    [[TMP6]] = phi i1 [ true, [[L13]] ], [ false, [[L2]] ]
+; CHECK-NEXT:    [[TMP7]] = phi i1 [ [[PREDL13_INV]], [[L13]] ], [ true, [[L2]] ]
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       Flow4:
+; CHECK-NEXT:    [[TMP8]] = phi i1 [ [[TMP0]], [[LOOP_EXIT_GUARD2]] ], [ false, [[H2]] ]
+; CHECK-NEXT:    [[TMP9:%.*]] = phi i1 [ false, [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP10:%.*]] = phi i1 [ [[TMP1]], [[LOOP_EXIT_GUARD2]] ], [ true, [[H2]] ]
+; CHECK-NEXT:    [[TMP11]] = xor i1 [[TMP9]], true
+; CHECK-NEXT:    br i1 [[TMP10]], label [[LOOP_EXIT_GUARD]], label [[H2]]
+; CHECK:       loop.exit.guard2:
+; CHECK-NEXT:    br label [[FLOW4]]
+;
+{
+entry:
+  br label %H1
+
+H1:
+  br label %H2
+
+H2:
+  br i1 %PredH2, label %L1, label %H3
+
+H3:
+  br i1 %PredH3, label %exit, label %L2
+
+L2:
+  br i1 %PredL2, label %H2, label %L13
+
+L13:
+  br i1 %PredL13, label %H3, label %H1
+
+L1:
+  br i1 %PredL1, label %exit, label %H1
+
+exit:
+  ret void
+}

llvm/test/Transforms/UnifyLoopExits/basic.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -unify-loop-exits -S | FileCheck %s
+
+define void @loop_1(i1 %PredEntry, i1 %PredB, i1 %PredC, i1 %PredD) {
+; CHECK-LABEL: @loop_1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[PREDENTRY:%.*]], label [[A:%.*]], label [[G:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[C:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       D:
+; CHECK-NEXT:    br i1 [[PREDD:%.*]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       E:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       F:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       G:
+; CHECK-NEXT:    br label [[F:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[B]] ], [ false, [[C]] ], [ false, [[D]] ]
+; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E:%.*]], label [[F]]
+;
+entry:
+  br i1 %PredEntry, label %A, label %G
+
+A:                                                ; preds = %D, %entry
+  br label %B
+
+B:                                                ; preds = %A
+  br i1 %PredB, label %C, label %E
+
+C:                                                ; preds = %B
+  br i1 %PredC, label %D, label %F
+
+D:                                                ; preds = %C
+  br i1 %PredD, label %A, label %F
+
+E:                                                ; preds = %B
+  br label %exit
+
+F:                                                ; preds = %G, %D, %C
+  br label %exit
+
+G:                                                ; preds = %entry
+  br label %F
+
+exit:                                             ; preds = %F, %E
+  ret void
+}
+
+define void @loop_2(i1 %PredA, i1 %PredB, i1 %PredC) {
+; CHECK-LABEL: @loop_2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br i1 [[PREDA:%.*]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    br i1 [[PREDB:%.*]], label [[C:%.*]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       C:
+; CHECK-NEXT:    br i1 [[PREDC:%.*]], label [[D:%.*]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       D:
+; CHECK-NEXT:    br label [[A]]
+; CHECK:       X:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       Y:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       Z:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_X:%.*]] = phi i1 [ true, [[A]] ], [ false, [[B]] ], [ false, [[C]] ]
+; CHECK-NEXT:    [[GUARD_Y:%.*]] = phi i1 [ false, [[A]] ], [ true, [[B]] ], [ false, [[C]] ]
+; CHECK-NEXT:    br i1 [[GUARD_X]], label [[X:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    br i1 [[GUARD_Y]], label [[Y:%.*]], label [[Z:%.*]]
+;
+entry:
+  br label %A
+
+A:                                                ; preds = %D, %entry
+  br i1 %PredA, label %B, label %X
+
+B:                                                ; preds = %A
+  br i1 %PredB, label %C, label %Y
+
+C:                                                ; preds = %B
+  br i1 %PredC, label %D, label %Z
+
+D:                                                ; preds = %C
+  br label %A
+
+X:                                                ; preds = %B
+  br label %exit
+
+Y:                                                ; preds = %G, %D, %C
+  br label %exit
+
+Z:                                                ; preds = %entry
+  br label %exit
+
+exit:                                             ; preds = %F, %E
+  ret void
+}

llvm/test/Transforms/UnifyLoopExits/nested.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -unify-loop-exits -S | FileCheck %s
+
+define void @nested(i1 %PredB3, i1 %PredB4, i1 %PredA4, i1 %PredA3, i32 %X, i32 %Y, i32 %Z) {
+; CHECK-LABEL: @nested(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[A1:%.*]]
+; CHECK:       A1:
+; CHECK-NEXT:    br label [[B1:%.*]]
+; CHECK:       B1:
+; CHECK-NEXT:    br label [[B2:%.*]]
+; CHECK:       B2:
+; CHECK-NEXT:    [[X_INC:%.*]] = add i32 [[X:%.*]], 1
+; CHECK-NEXT:    br label [[B3:%.*]]
+; CHECK:       B3:
+; CHECK-NEXT:    br i1 [[PREDB3:%.*]], label [[B4:%.*]], label [[LOOP_EXIT_GUARD1:%.*]]
+; CHECK:       B4:
+; CHECK-NEXT:    br i1 [[PREDB4:%.*]], label [[B1]], label [[LOOP_EXIT_GUARD1]]
+; CHECK:       A2:
+; CHECK-NEXT:    br label [[A4:%.*]]
+; CHECK:       A3:
+; CHECK-NEXT:    br label [[A4]]
+; CHECK:       A4:
+; CHECK-NEXT:    [[A4_PHI:%.*]] = phi i32 [ [[Y:%.*]], [[A3:%.*]] ], [ [[X_INC_MOVED:%.*]], [[A2:%.*]] ]
+; CHECK-NEXT:    br i1 [[PREDA4:%.*]], label [[LOOP_EXIT_GUARD:%.*]], label [[A5:%.*]]
+; CHECK:       A5:
+; CHECK-NEXT:    br i1 [[PREDA3:%.*]], label [[LOOP_EXIT_GUARD]], label [[A1]]
+; CHECK:       C:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[EXIT_PHI:%.*]] = phi i32 [ [[Z:%.*]], [[C:%.*]] ], [ [[EXIT_PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
+; CHECK-NEXT:    ret void
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_C:%.*]] = phi i1 [ true, [[A4]] ], [ false, [[A5]] ]
+; CHECK-NEXT:    [[EXIT_PHI_MOVED]] = phi i32 [ undef, [[A4]] ], [ [[A4_PHI]], [[A5]] ]
+; CHECK-NEXT:    br i1 [[GUARD_C]], label [[C]], label [[EXIT]]
+; CHECK:       loop.exit.guard1:
+; CHECK-NEXT:    [[GUARD_A3:%.*]] = phi i1 [ true, [[B3]] ], [ false, [[B4]] ]
+; CHECK-NEXT:    [[X_INC_MOVED]] = phi i32 [ [[X_INC]], [[B3]] ], [ [[X_INC]], [[B4]] ]
+; CHECK-NEXT:    br i1 [[GUARD_A3]], label [[A3]], label [[A2]]
+;
+entry:
+  br label %A1
+
+A1:
+  br label %B1
+
+B1:                                                ; preds = %A
+  br label %B2
+
+B2:
+  %X.inc = add i32 %X, 1
+  br label %B3
+
+B3:                                                ; preds = %C
+  br i1 %PredB3, label %B4, label %A3
+
+B4:
+  br i1 %PredB4, label %B1, label %A2
+
+A2:
+  br label %A4
+
+A3:
+  br label %A4
+
+A4:
+  %A4.phi = phi i32 [%Y, %A3], [%X.inc, %A2]
+  br i1 %PredA4, label %C, label %A5
+
+A5:                                                ; preds = %entry
+  br i1 %PredA3, label %exit, label %A1
+
+C:
+  br label %exit
+
+exit:
+  %exit.phi = phi i32 [%A4.phi, %A5], [%Z, %C]
+  ret void
+}

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

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -unify-loop-exits -S | FileCheck %s
+
+; Loop consists of A and B:
+; - A is the header
+; - A and B are exiting blocks
+; - C and return are exit blocks.
+; Pattern: Value (%mytmp42) defined in exiting block (A) and used in
+;          exit block (return).
+;          The relevant code uses DT::dominates(Value,
+;          BasicBlock). This is misnamed because it actually checks
+;          strict dominance, causing the pattern to be miscompiled
+;          (the use receives an undef value).
+define i32 @exiting-used-in-exit(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
+; CHECK-LABEL: @exiting-used-in-exit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP41]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       C:
+; CHECK-NEXT:    [[INC:%.*]] = add i32 [[MYTMP41_MOVED:%.*]], 1
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[INC]], [[C:%.*]] ], [ [[PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
+; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[B]] ]
+; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP42]], [[A]] ], [ undef, [[B]] ]
+; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[B]] ]
+; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[C]]
+;
+entry:
+  br label %A
+
+A:                                       ; preds = %B, %A.lr.ph
+  %mytmp42 = load i32, i32* %arg1, align 4
+  %cmp1 = icmp slt i32 %mytmp42, 0
+  br i1 %cmp1, label %B, label %return
+
+B:                                           ; preds = %A
+  %mytmp41 = load i32, i32* %arg2, align 4
+  %cmp = icmp slt i32 %mytmp41, 0
+  br i1 %cmp, label %A, label %C
+
+C:
+  %inc = add i32 %mytmp41, 1
+  br label %return
+
+return:                                           ; preds = %B38, %A
+  %phi = phi i32 [ %inc, %C ], [ %mytmp42, %A ]
+  ret i32 %phi
+}
+
+; Loop consists of A, B and C:
+; - A is the header
+; - A and C are exiting blocks
+; - B is an "internal" block that dominates exiting block C
+; - D and return are exit blocks.
+; Pattern: Value (%mytmp41) defined in internal block (B) and used in an
+;          exit block (D).
+define i32 @internal-used-in-exit(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
+; CHECK-LABEL: @internal-used-in-exit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
+; CHECK-NEXT:    br label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       D:
+; CHECK-NEXT:    [[INC:%.*]] = add i32 [[MYTMP41_MOVED:%.*]], 1
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       return:
+; CHECK-NEXT:    ret i32 0
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
+; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
+; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[D:%.*]]
+;
+entry:
+  %mytmp42 = load i32, i32* %arg1, align 4
+  br label %A
+
+A:                                       ; preds = %B, %A.lr.ph
+  %cmp1 = icmp slt i32 %mytmp42, 0
+  br i1 %cmp1, label %B, label %return
+
+B:                                           ; preds = %A
+  %mytmp41 = load i32, i32* %arg2, align 4
+  br label %C
+
+C:
+  %cmp = icmp slt i32 %mytmp42, 0
+  br i1 %cmp, label %A, label %D
+
+D:
+  %inc = add i32 %mytmp41, 1
+  br label %return
+
+return:                                           ; preds = %B38, %A
+  ret i32 0
+}
+
+; Loop consists of A, B and C:
+; - A is the header
+; - A and C are exiting blocks
+; - B is an "internal" block that dominates exiting block C
+; - D and return are exit blocks.
+; Pattern: %return contains a phi node that receives values from
+;          %entry, %A and %D. This mixes all the special cases in a single phi.
+define i32 @mixed-use-in-exit(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
+; CHECK-LABEL: @mixed-use-in-exit(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP2]], label [[A:%.*]], label [[RETURN:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[MYTMP43:%.*]] = add i32 [[MYTMP42]], 1
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
+; CHECK-NEXT:    br label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       D:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[MYTMP41_MOVED:%.*]], [[D:%.*]] ], [ [[MYTMP42]], [[ENTRY:%.*]] ], [ [[PHI_MOVED:%.*]], [[LOOP_EXIT_GUARD]] ]
+; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_RETURN:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
+; CHECK-NEXT:    [[PHI_MOVED]] = phi i32 [ [[MYTMP43]], [[A]] ], [ undef, [[C]] ]
+; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
+; CHECK-NEXT:    br i1 [[GUARD_RETURN]], label [[RETURN]], label [[D]]
+;
+entry:
+  %mytmp42 = load i32, i32* %arg1, align 4
+  %cmp2 = icmp slt i32 %mytmp42, 0
+  br i1 %cmp2, label %A, label %return
+
+A:                                       ; preds = %B, %A.lr.ph
+  %mytmp43 = add i32 %mytmp42, 1
+  %cmp1 = icmp slt i32 %mytmp42, 0
+  br i1 %cmp1, label %B, label %return
+
+B:                                           ; preds = %A
+  %mytmp41 = load i32, i32* %arg2, align 4
+  br label %C
+
+C:
+  %cmp = icmp slt i32 %mytmp42, 0
+  br i1 %cmp, label %A, label %D
+
+D:
+  br label %return
+
+return:                                           ; preds = %B38, %A
+  %phi = phi i32 [ %mytmp41, %D ], [ %mytmp43, %A ], [%mytmp42, %entry]
+  ret i32 %phi
+}
+
+; Loop consists of A, B and C:
+; - A is the header
+; - A and C are exiting blocks
+; - B is an "internal" block that dominates exiting block C
+; - D and E are exit blocks.
+; Pattern: Value (%mytmp41) defined in internal block (B) and used in a
+;          downstream block not related to the loop (return). The use
+;          is a phi where the incoming block for %mytmp41 is not related
+;          to the loop (D).
+;          This pattern does not involve either the exiting blocks or
+;          the exit blocks, which catches any such assumptions built
+;          into the SSA reconstruction phase.
+define i32 @phi-via-external-block(i32* %arg1, i32* %arg2) local_unnamed_addr align 2 {
+; CHECK-LABEL: @phi-via-external-block(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[MYTMP42:%.*]] = load i32, i32* [[ARG1:%.*]], align 4
+; CHECK-NEXT:    br label [[A:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP1]], label [[B:%.*]], label [[LOOP_EXIT_GUARD:%.*]]
+; CHECK:       B:
+; CHECK-NEXT:    [[MYTMP41:%.*]] = load i32, i32* [[ARG2:%.*]], align 4
+; CHECK-NEXT:    br label [[C:%.*]]
+; CHECK:       C:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[MYTMP42]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[A]], label [[LOOP_EXIT_GUARD]]
+; CHECK:       D:
+; CHECK-NEXT:    br label [[RETURN:%.*]]
+; CHECK:       E:
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[MYTMP41_MOVED:%.*]], [[D:%.*]] ], [ [[MYTMP42]], [[E:%.*]] ]
+; CHECK-NEXT:    ret i32 [[PHI]]
+; CHECK:       loop.exit.guard:
+; CHECK-NEXT:    [[GUARD_E:%.*]] = phi i1 [ true, [[A]] ], [ false, [[C]] ]
+; CHECK-NEXT:    [[MYTMP41_MOVED]] = phi i32 [ undef, [[A]] ], [ [[MYTMP41]], [[C]] ]
+; CHECK-NEXT:    br i1 [[GUARD_E]], label [[E]], label [[D]]
+;
+entry:
+  %mytmp42 = load i32, i32* %arg1, align 4
+  br label %A
+
+A:                                       ; preds = %B, %A.lr.ph
+  %cmp1 = icmp slt i32 %mytmp42, 0
+  br i1 %cmp1, label %B, label %E
+
+B:                                           ; preds = %A
+  %mytmp41 = load i32, i32* %arg2, align 4
+  br label %C
+
+C:
+  %cmp = icmp slt i32 %mytmp42, 0
+  br i1 %cmp, label %A, label %D
+
+D:
+  br label %return
+
+E:
+  br label %return
+
+return:                                           ; preds = %B38, %A
+  %phi = phi i32 [ %mytmp41, %D ], [ %mytmp42, %E ]
+  ret i32 %phi
+}

llvm/tools/llc/llc.cpp

int main(int argc, char **argv) {
   initializePostInlineEntryExitInstrumenterPass(*Registry);
   initializeUnreachableBlockElimLegacyPassPass(*Registry);
   initializeConstantHoistingLegacyPassPass(*Registry);
   initializeScalarOpts(*Registry);
   initializeVectorization(*Registry);
   initializeScalarizeMaskedMemIntrinPass(*Registry);
   initializeExpandReductionsPass(*Registry);
   initializeHardwareLoopsPass(*Registry);
+  initializeTransformUtils(*Registry);
 
   // Initialize debugging passes.
   initializeScavengerTestPass(*Registry);
 
   // Register the target printer for --version.
   cl::AddExtraVersionPrinter(TargetRegistry::printRegisteredTargetsForVersion);
 
   cl::ParseCommandLineOptions(argc, argv, "llvm system compiler\n");