[MergeSets] Add infrastructure to build merge sets based on Das and Ramakrishna's paper.

[fhahn]

Summary

Merge sets as described in the paper below provide a fast way to answer multiple
queries for basic blocks that may need PHI nodes, by pre-computing the merge sets
for all nodes in a dominator tree in constant time.

Dibyendu Das and U. Ramakrishna. 2005. A practical and fast iterative
algorithm for φ-function computation using DJ graphs.
ACM Trans. Program. Lang. Syst. 27, 3 (May 2005), 426-440.

Merge sets can be used to speed up code that currently calculates
iterated dominance frontiers multiple times to find nodes that need PHI
nodes when doing SSA updates.

One example is mem2reg. With merge sets, mem2reg/SROA runs about 3 times
faster for a SROA heavy test case I could find (
https://bugs.llvm.org/show_bug.cgi?id=15412)

With IDF

Total Execution Time: 33.5696 seconds (33.5756 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
10.2445 ( 31.0%)   0.1748 ( 31.4%)  10.4193 ( 31.0%)  10.4207 ( 31.0%)  SROA #2
 4.7518 ( 14.4%)   0.0120 (  2.1%)   4.7637 ( 14.2%)   4.7635 ( 14.2%)  Induction Variable Simplification
 3.1591 (  9.6%)   0.0248 (  4.5%)   3.1839 (  9.5%)   3.1862 (  9.5%)  Simple Register Coalescing

With merge sets (this patch)

Total Execution Time: 25.3381 seconds (25.3400 wall clock)

 ---User Time---   --System Time--   --User+System--   ---Wall Time---  --- Name ---
 4.8915 ( 19.8%)   0.0146 (  2.2%)   4.9061 ( 19.4%)   4.9061 ( 19.4%)  Induction Variable Simplification
 2.9898 ( 12.1%)   0.2932 ( 44.3%)   3.2830 ( 13.0%)   3.2838 ( 13.0%)  SROA #2
 2.9581 ( 12.0%)   0.0153 (  2.3%)   2.9733 ( 11.7%)   2.9739 ( 11.7%)  Simple Register Coalescing

I haven't done any micro tuning so far and the merge sets implementation
still needs a bit of polishing, but I thought it would be good to share
this early to get some high level feedback.

This potentially could be used in SSAUpdaterBulk in combination with a
fast renamer similar to the implementation in PredicateInfo (I have a
patch for such a renamer that I will post shortly).

[fhahn]

The patch currently implements variant 1 form the paper (TDMSC-I) as it is slightly simpler. I will follow up with variant 2 (TDMSC-II) in a bit and do some more detailed compile time measurement. Also the only reason MergeSets live in IteratedDominanceFrontier.h/cpp was convenience, they could be moved to their own files.

[davide]

I need to read the paper again because I forgot how the algorithm works. Please ping me in a week if I forget to review this.

[fhahn]

Move implementation to MergeSets.h/.cpp and implement variant 2 from the paper as build2().

[fhahn]

In D57123#1382553, @davide wrote:

I need to read the paper again because I forgot how the algorithm works. Please ping me in a week if I forget to review this.

Thanks Davide! On CTMark, the impact is neutral (some tiny improvements/regressions, in the noise). In some cases, computing the merge sets is more expensive, than the IDF (e.g. if we just need to place PHI nodes for a one or two allocas in a function), so we might want to pick one strategy depending on the input function.

(I also plan to refactor the implementation of both variants a bit)

[hiraditya]

Interesting, I have a merge-sets implementation in my patch: https://reviews.llvm.org/D32140
It will be interesting to compare the two.

[fhahn]

In D57123#1387411, @hiraditya wrote:

Interesting, I have a merge-sets implementation in my patch: https://reviews.llvm.org/D32140
It will be interesting to compare the two.

Interesting! It seems the biggest difference is that the implementation here does not explicitly construct the DJ graph and uses BitVectors instead of sets. It would probably make sense to split up the mergeset part and the PromoteMem2Reg part once they are ready for committing. Let me know if you are interesting in trying the implementation for your patch, I'd be happy to split it up sooner.

[hiraditya]

i think this will help quite a few optimizations get faster and enable others like instruction scheduling in SSA. We can push this patch and make incremental improvements as needed. Thanks for working on this!

[hiraditya]

llvm/include/llvm/Analysis/MergeSets.h

83

We can use a more descriptive name here and below.

llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

535–536

nit:

650

can we put the code under #ifndef in separate function.

806

nit:

[hiraditya]

llvm/include/llvm/Analysis/MergeSets.h

15

is it okay to use non-ASCII characters? I'm not sure but wanted to point out.

[fhahn]

Thanks! I'll try to update this patch and a few related patches around the time of the dev meeting.

[hiraditya]

Great, looking forward to it!

[fhahn]

Rebase patch

[hiraditya]

Thanks for rebasing the patch.

llvm/lib/Analysis/MergeSets.cpp

47

Some comments would be nice!

109

Is it possible that DFS numbers are already up-to-date?

llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

660

We can put the verification part somewhere else, possibly under a flag.

llvm/include/llvm/Analysis/MergeSets.h

+//===- MergeSets.h - Calculate MergeSets ------------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+/// \file
+/// Build the merge sets for a given dominator tree. The merge set of a node N
+/// is the set of nodes that may need a PHI node for a definition in N. Based on
+/// the algorithm from
+///
+/// Dibyendu Das and U. Ramakrishna. 2005. A practical and fast iterative
+///  algorithm for φ-function computation using DJ graphs.
+///  ACM Trans. Program. Lang. Syst. 27, 3 (May 2005), 426-440.
+///
+/// It has been modified to not explicitly use the DJ graph data structure.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MERGESETS_H
+#define LLVM_ANALYSIS_MERGESETS_H
+
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFGDiff.h"
+#include "llvm/IR/Dominators.h"
+
+#include <unordered_set>
+namespace llvm {
+
+class MergeSets {
+  DominatorTree &DT;
+  DenseMap<BasicBlock *, unsigned> &BBNumbers;
+  size_t NumBBs;
+
+  struct PairHasher {
+    std::size_t operator()(const std::pair<unsigned, unsigned> &Key) const {
+      return Key.first ^
+             (Key.second + (Key.first << 6) + (Key.first >> 2) + 0x9e3779b9);
+    }
+  };
+
+  std::unordered_set<std::pair<unsigned, unsigned>, PairHasher> Visited;
+  SmallVector<BitVector, 128> Sets;
+  DenseMap<unsigned, BasicBlock *> NumToBB;
+
+  BitVector &getSet(DomTreeNode *N) { return Sets[getNum(N)]; }
+
+  BitVector &getSet(BasicBlock *BB) { return Sets[getNum(BB)]; }
+
+  BitVector &getSet(unsigned i) { return Sets[i]; }
+
+  const BitVector &getSet(unsigned i) const { return Sets[i]; }
+
+  unsigned getNum(BasicBlock *BB) const { return BBNumbers.find(BB)->second; };
+  unsigned getNum(DomTreeNode *N) const { return getNum(N->getBlock()); };
+
+  bool isInconsistentJ(DomTreeNode *Src, DomTreeNode *Dst) const;
+
+  void dumpSet(DomTreeNode *N);
+
+public:
+  MergeSets(DominatorTree &DT, DenseMap<BasicBlock *, unsigned> &BBNumbers)
+      : DT(DT), BBNumbers(BBNumbers), NumBBs(BBNumbers.size()),
+        Sets(NumBBs, BitVector(NumBBs)) {
+
+    // Reverse mapping from number to BB.
+    NumToBB.reserve(BBNumbers.size());
+    for (auto &P : BBNumbers)
+      NumToBB[P.second] = P.first;
+  }
+
+  /// Returns the merge set for nodes \p DefBBs.
+  SmallVector<BasicBlock *, 8> get(const SmallPtrSetImpl<BasicBlock *> &DefBBs);
+
+  /// Compute merge sets for CFG rooted at \p Root using TDMSC-I from the paper.
+  void build(BasicBlock *Root);
+
+  /// Compute merge sets for CFG rooted at \p Root using TDMSC-II from the
+  /// paper.
+  void build2(BasicBlock *Root);
+};
+} // namespace llvm
+#endif

llvm/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   MemDerefPrinter.cpp
   MemoryBuiltins.cpp
   MemoryDependenceAnalysis.cpp
   MemoryLocation.cpp
   MemorySSA.cpp
   MemorySSAUpdater.cpp
   ModuleDebugInfoPrinter.cpp
   ModuleSummaryAnalysis.cpp
+  MergeSets.cpp
   MustExecute.cpp
   ObjCARCAliasAnalysis.cpp
   ObjCARCAnalysisUtils.cpp
   ObjCARCInstKind.cpp
   OptimizationRemarkEmitter.cpp
   OrderedBasicBlock.cpp
   OrderedInstructions.cpp
   PHITransAddr.cpp

llvm/lib/Analysis/MergeSets.cpp

+//===- MergeSets.cpp - Compute MergeSets ----------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Compute the MergeSets for a dominator tree.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/MergeSets.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/PredIteratorCache.h"
+#include <queue>
+
+namespace llvm {
+
+#define DEBUG_TYPE "mergesets"
+
+STATISTIC(Num1Round, "Number times merge sets valid after one round.");
+STATISTIC(Num2Rounds, "Number times merge sets valid after two rounds.");
+STATISTIC(Num3Rounds,
+          "Number times merge sets valid after three or more rounds.");
+
+bool MergeSets::isInconsistentJ(DomTreeNode *Src, DomTreeNode *Dst) const {
+  if (!Src || DT.properlyDominates(Src, Dst))
+    return false;
+
+  unsigned SrcNum = getNum(Src);
+  unsigned DstNum = getNum(Dst);
+  if (Visited.find({SrcNum, DstNum}) == Visited.end())
+    return false;
+
+  BitVector Both = getSet(SrcNum);
+  unsigned SrcDCount = Both.count();
+  Both |= getSet(DstNum);
+  if (Both.count() == SrcDCount)
+    return false;
+
+  return true;
+}
+
+void MergeSets::build(BasicBlock *Root) {
+  DT.updateDFSNumbers();
+  PredIteratorCache PredCache;
+
+  bool Done = false;
+  unsigned Round = 0;
+  while (!Done) {
+    Round++;
+    Done = true;
+    Visited.clear();
+    std::queue<DomTreeNode *> WorkQueue;
+    WorkQueue.push(DT.getNode(Root));
+
+    while (!WorkQueue.empty()) {
+      DomTreeNode *N = WorkQueue.front();
+      WorkQueue.pop();
+      for (auto *C : N->getChildren())
+        WorkQueue.push(C);
+
+      for (BasicBlock *P : PredCache.get(N->getBlock())) {
+        auto *PDom = DT.getNode(P);
+        if (!PDom || DT.properlyDominates(PDom, N))
+          continue;
+
+        unsigned PNum = getNum(P);
+        unsigned NNum = getNum(N);
+        if (!Visited.insert({PNum, NNum}).second)
+          continue;
+
+        DomTreeNode *Tmp = PDom;
+        DomTreeNode *LNode = nullptr;
+        const auto &S2 = getSet(N);
+        while (Tmp->getLevel() >= N->getLevel()) {
+          auto &TmpS = getSet(Tmp);
+          TmpS |= S2;
+          TmpS.set(NNum);
+          LNode = Tmp;
+          Tmp = Tmp->getIDom();
+        }
+
+        // If any incoming edge is inconsistent, we need to do another round
+        // of the algorithm.
+        if (any_of(PredCache.get(LNode->getBlock()), [&LNode, this](
+                                                          BasicBlock *Src) {
+              return this->isInconsistentJ(this->DT.getNode(Src), LNode);
+            })) {
+          Done = false;
+          break;
+        }
+      }
+    }
+  }
+
+  if (Round == 1)
+    Num1Round++;
+  else if (Round == 2)
+    Num2Rounds++;
+  else
+    Num3Rounds++;
+}
+
+void MergeSets::build2(BasicBlock *Root) {
+  DT.updateDFSNumbers();
+
+  PredIteratorCache PredCache;
+
+  bool Done = false;
+  unsigned Round = 0;
+  while (!Done) {
+    Round++;
+    Done = true;
+    Visited.clear();
+    std::queue<DomTreeNode *> WorkQueue;
+    WorkQueue.push(DT.getNode(Root));
+
+    while (!WorkQueue.empty()) {
+      DomTreeNode *N = WorkQueue.front();
+      WorkQueue.pop();
+      for (auto *C : N->getChildren())
+        WorkQueue.push(C);
+
+      for (BasicBlock *P : PredCache.get(N->getBlock())) {
+        auto *PDom = DT.getNode(P);
+        if (!PDom || DT.properlyDominates(PDom, N))
+          continue;
+
+        unsigned PNum = getNum(P);
+        unsigned NNum = getNum(N);
+        if (!Visited.insert({PNum, NNum}).second)
+          continue;
+
+        DomTreeNode *Tmp = PDom;
+        DomTreeNode *LNode = nullptr;
+        const auto &S2 = getSet(N);
+        while (Tmp->getLevel() >= N->getLevel()) {
+          auto &TmpS = getSet(Tmp);
+          TmpS |= S2;
+          TmpS.set(NNum);
+          LNode = Tmp;
+          Tmp = Tmp->getIDom();
+        }
+
+        for (BasicBlock *Src : PredCache.get(LNode->getBlock())) {
+          auto *SrcD = DT.getNode(Src);
+          if (!isInconsistentJ(SrcD, LNode))
+            continue;
+
+          DomTreeNode *NN = SrcD;
+          DomTreeNode *LNode1 = nullptr;
+          auto &S2 = getSet(LNode);
+          while (NN->getLevel() >= LNode->getLevel()) {
+            auto &TmpS = getSet(NN);
+            TmpS |= S2;
+            LNode1 = NN;
+            NN = NN->getIDom();
+          }
+
+          // If any incoming edge is inconsistent, we need to do another round
+          // of the algorithm.
+          if (any_of(PredCache.get(LNode1->getBlock()), [&LNode1, this](
+                                                            BasicBlock *Src) {
+                return this->isInconsistentJ(this->DT.getNode(Src), LNode1);
+              })) {
+            Done = false;
+            break;
+          }
+        }
+      }
+    }
+  }
+
+  if (Round == 1)
+    Num1Round++;
+  else if (Round == 2)
+    Num2Rounds++;
+  else
+    Num3Rounds++;
+}
+
+SmallVector<BasicBlock *, 8>
+MergeSets::get(const SmallPtrSetImpl<BasicBlock *> &DefBBs) {
+  SmallVector<BasicBlock *, 8> Result;
+  BitVector M(BBNumbers.size());
+  for (auto *BB : DefBBs) {
+    assert(DT.isReachableFromEntry(BB) && "Node not reachable.");
+    M |= getSet(BB);
+  }
+
+  for (unsigned I : M.set_bits())
+    Result.push_back(NumToBB[I]);
+  return Result;
+}
+
+void MergeSets::dumpSet(DomTreeNode *N) {
+  SmallPtrSet<BasicBlock *, 1> S;
+  S.insert(N->getBlock());
+  dbgs() << "  MS for " << N->getBlock()->getName() << " : ";
+  for (auto *BB : get(S))
+    dbgs() << BB->getName() << " ";
+  dbgs() << "\n";
+}
+} // namespace llvm

llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
-#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Analysis/MergeSets.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
+#include "llvm/IR/Verifier.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
for (DbgVariableIntrinsic *DII : Info.DbgDeclares)
     DII->eraseFromParent();
 
   ++NumLocalPromoted;
   return true;
 }
 
 void PromoteMem2Reg::run() {
   Function &F = *DT.getRoot()->getParent();
-
+  /*  if (F.getName() == "gen_pic_list_from_frame_list")*/
+  // F.getParent()->dump();
   AllocaDbgDeclares.resize(Allocas.size());
 
   AllocaInfo Info;
   LargeBlockInfo LBI;
-  ForwardIDFCalculator IDF(DT);
 
+  SmallVector<std::pair<unsigned, AllocaInfo>, 32> NeedPHIs;
   for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
     AllocaInst *AI = Allocas[AllocaNum];
 
     assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
     assert(AI->getParent()->getParent() == &F &&
            "All allocas should be in the same function, which is same as DF!");
 
     removeLifetimeIntrinsicUsers(AI);
for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
     // Keep the reverse mapping of the 'Allocas' array for the rename pass.
     AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
 
     // At this point, we're committed to promoting the alloca using IDF's, and
     // the standard SSA construction algorithm.  Determine which blocks need PHI
     // nodes and see if we can optimize out some work by avoiding insertion of
     // dead phi nodes.
 
+    NeedPHIs.emplace_back(AllocaNum, std::move(Info));
+  }
+
+  if (Allocas.empty())
+    return; // All of the allocas must have been trivial!
+
+  if (!NeedPHIs.empty()) {
+    MergeSets MS(DT, BBNumbers);
+    MS.build2(&F.getEntryBlock());
+
+    for (auto &P : NeedPHIs) {
+      auto &Info = P.second;
+      unsigned AllocaNum = P.first;
       // Unique the set of defining blocks for efficient lookup.
-    SmallPtrSet<BasicBlock *, 32> DefBlocks(Info.DefiningBlocks.begin(),
-                                            Info.DefiningBlocks.end());
+      SmallPtrSet<BasicBlock *, 32> DefBlocks;
+      for (auto *BB : Info.DefiningBlocks)
+        if (DT.isReachableFromEntry(BB))
+          DefBlocks.insert(BB);
+
+      auto AI = Allocas[AllocaNum];
 
-    // Determine which blocks the value is live in.  These are blocks which lead
-    // to uses.
+      // Determine which blocks the value is live in.  These are blocks which
+      // lead to uses.
       SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
       ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
 
       // At this point, we're committed to promoting the alloca using IDF's, and
-    // the standard SSA construction algorithm.  Determine which blocks need phi
-    // nodes and see if we can optimize out some work by avoiding insertion of
-    // dead phi nodes.
-    IDF.setLiveInBlocks(LiveInBlocks);
-    IDF.setDefiningBlocks(DefBlocks);
-    SmallVector<BasicBlock *, 32> PHIBlocks;
-    IDF.calculate(PHIBlocks);
+      // the standard SSA construction algorithm.  Determine which blocks need
+      // phi nodes and see if we can optimize out some work by avoiding
+      // insertion of dead phi nodes.
+      auto PHIBlocks = MS.get(DefBlocks);
+      if (PHIBlocks.size() > 1)
         llvm::sort(PHIBlocks, [this](BasicBlock *A, BasicBlock *B) {
-      return BBNumbers.find(A)->second < BBNumbers.find(B)->second;
+          return BBNumbers.lookup(A) < BBNumbers.lookup(B);
         });
 
       unsigned CurrentVersion = 0;
-    for (BasicBlock *BB : PHIBlocks)
+      unsigned NumAdded = 0;
+      for (BasicBlock *BB : PHIBlocks) {
+        if (!LiveInBlocks.count(BB))
+          continue;
+        NumAdded++;
         QueuePhiNode(BB, AllocaNum, CurrentVersion);
       }
+#ifndef NDEBUG
+      // Verify that we added the same number of  PHI nodes using merge sets as
+      // with the iterated dominance frontier.
+      ForwardIDFCalculator IDF(DT);
+      IDF.setLiveInBlocks(LiveInBlocks);
+      IDF.setDefiningBlocks(DefBlocks);
+      SmallVector<BasicBlock *, 32> IDFPHIBlocks;
+      IDF.calculate(IDFPHIBlocks);
 
-  if (Allocas.empty())
-    return; // All of the allocas must have been trivial!
+      // Make sure both approaches result in the same number of PHIs placed.
+      assert(NumAdded == IDFPHIBlocks.size() && "Number of blocks mismatched");
+
+      SmallPtrSet<BasicBlock *, 8> PlacedBlockSet;
+      PlacedBlockSet.insert(PHIBlocks.begin(), PHIBlocks.end());
+
+      // Check all PHI blocks computed by IDF are also found using merge sets.
+      for (auto *BB : IDFPHIBlocks)
+        assert(PlacedBlockSet.count(BB) && "missed a block");
+#endif
+    }
+  }
 
   LBI.clear();
 
   // Set the incoming values for the basic block to be null values for all of
   // the alloca's.  We do this in case there is a load of a value that has not
   // been stored yet.  In this case, it will get this null value.
   RenamePassData::ValVector Values(Allocas.size());
   for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
            SomePHI->getNumIncomingValues() == NumBadPreds) {
       Value *UndefVal = UndefValue::get(SomePHI->getType());
       for (BasicBlock *Pred : Preds)
         SomePHI->addIncoming(UndefVal, Pred);
     }
   }
 
   NewPhiNodes.clear();
+  /*  if (verifyFunction(F, &dbgs())) {*/
+  // F.dump();
+  // assert(false);
+  /*}*/
 }
 
 /// Determine which blocks the value is live in.
 ///
 /// These are blocks which lead to uses.  Knowing this allows us to avoid
 /// inserting PHI nodes into blocks which don't lead to uses (thus, the
 /// inserted phi nodes would be dead).
 void PromoteMem2Reg::ComputeLiveInBlocks(

llvm/test/Transforms/Mem2Reg/merge-sets.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -S -mem2reg | FileCheck %s
+
+define void @test1() {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br i1 undef, label [[WHILE_COND:%.*]], label [[IF_END46:%.*]]
+; CHECK:       while.cond:
+; CHECK-NEXT:    [[TOP_IDX_0:%.*]] = phi i32 [ undef, [[IF_END]] ], [ [[INC16:%.*]], [[WHILE_BODY:%.*]] ]
+; CHECK-NEXT:    br label [[LOR_RHS:%.*]]
+; CHECK:       lor.rhs:
+; CHECK-NEXT:    br i1 undef, label [[WHILE_BODY]], label [[IF_END46]]
+; CHECK:       while.body:
+; CHECK-NEXT:    [[INC16]] = add nsw i32 undef, 1
+; CHECK-NEXT:    br label [[WHILE_COND]]
+; CHECK:       if.end46:
+; CHECK-NEXT:    [[TOP_IDX_1:%.*]] = phi i32 [ [[TOP_IDX_0]], [[LOR_RHS]] ], [ undef, [[IF_END]] ]
+; CHECK-NEXT:    br label [[WHILE_COND49:%.*]]
+; CHECK:       while.cond49:
+; CHECK-NEXT:    [[IDXPROM97:%.*]] = sext i32 [[TOP_IDX_1]] to i64
+; CHECK-NEXT:    br label [[WHILE_COND49]]
+;
+entry:
+  %top_idx = alloca i32, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %entry
+  br i1 undef, label %while.cond, label %if.end46
+
+while.cond:                                       ; preds = %while.body, %if.end
+  br label %lor.rhs
+
+lor.rhs:                                          ; preds = %while.cond
+  br i1 undef, label %while.body, label %if.end46
+
+while.body:                                       ; preds = %lor.rhs
+  %inc16 = add nsw i32 undef, 1
+  store i32 %inc16, i32* %top_idx, align 4
+  br label %while.cond
+
+if.end46:                                         ; preds = %lor.rhs, %if.end
+  br label %while.cond49
+
+while.cond49:                                     ; preds = %while.cond49, %if.end46
+  %top_idx.0.load139 = load i32, i32* %top_idx, align 4
+  %idxprom97 = sext i32 %top_idx.0.load139 to i64
+  br label %while.cond49
+}
+
+define void @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[SW_EPILOG:%.*]]
+; CHECK:       sw.epilog:
+; CHECK-NEXT:    br i1 undef, label [[WHILE_COND85:%.*]], label [[IF_END105:%.*]]
+; CHECK:       while.cond85:
+; CHECK-NEXT:    [[__M_0:%.*]] = phi double* [ undef, [[SW_EPILOG]] ], [ [[V1:%.*]], [[IF_END98:%.*]] ]
+; CHECK-NEXT:    br i1 undef, label [[IF_END105]], label [[IF_END98]]
+; CHECK:       if.end98:
+; CHECK-NEXT:    [[V1]] = load double*, double** undef, align 8
+; CHECK-NEXT:    br label [[WHILE_COND85]]
+; CHECK:       if.end105:
+; CHECK-NEXT:    [[__M_1:%.*]] = phi double* [ [[__M_0]], [[WHILE_COND85]] ], [ undef, [[SW_EPILOG]] ]
+; CHECK-NEXT:    unreachable
+;
+entry:
+  %__m = alloca double*, align 8
+  br label %sw.epilog
+
+sw.epilog:                                        ; preds = %entry
+  br i1 undef, label %while.cond85, label %if.end105
+
+while.cond85:                                     ; preds = %if.end98, %sw.epilog
+  br i1 undef, label %if.end105, label %if.end98
+
+if.end98:                                         ; preds = %while.cond85
+  %v1 = load double*, double** undef, align 8
+  store double* %v1, double** %__m, align 8
+  br label %while.cond85
+
+if.end105:                                        ; preds = %while.cond85, %sw.epilog
+  %tmp1 = load double*, double** %__m, align 8
+  unreachable
+}