[WinEHPrepare] Update demotion logic

[JosephTremoulet]

Summary

Update the demotion logic in WinEHPrepare to avoid creating new cleanups by
walking predecessors as necessary to insert stores for EH-pad PHIs.

Also avoid creating stores for EH-pad PHIs that have no uses.

The store/load placement is still pretty naive. Likely future improvements
(at least for optimized compiles) include:

• Share loads for related uses as possible
• Coalesce non-interfering use/def-related PHIs
• Store at definition point rather than each PHI pred for non-interfering lifetimes.

[majnemer]

Thanks for working on this!

LGTM with nits applied.

lib/CodeGen/WinEHPrepare.cpp

3229–3230

This looks a little funny, could you run clang-format over it?

3261

This assert shouldn't be necessary, cast will do that for you.

3277–3279

Could you reformat this with clang-format.

3296–3297

This should be formatted as well.

[JosephTremoulet]

• Remove redundant assertion
• Clang-format modified code (caught cases noted in review plus a couple more)

[JosephTremoulet]

• Remove unused variable

[JosephTremoulet]

• rebase

lib/CodeGen/WinEHPrepare.cpp

private:
 
   void mapLandingPadBlocks(LandingPadInst *LPad, LandingPadActions &Actions);
   CatchHandler *findCatchHandler(BasicBlock *BB, BasicBlock *&NextBB,
                                  VisitedBlockSet &VisitedBlocks);
   void findCleanupHandlers(LandingPadActions &Actions, BasicBlock *StartBB,
                            BasicBlock *EndBB);
 
   void processSEHCatchHandler(CatchHandler *Handler, BasicBlock *StartBB);
-
+  void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
+  void
+  insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
+                 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
+  AllocaInst *insertPHILoads(PHINode *PN, Function &F);
+  void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
+                          DenseMap<BasicBlock *, Value *> &Loads, Function &F);
+  void demoteNonlocalUses(Value *V, std::set<BasicBlock *> &ColorsForBB,
+                          Function &F);
   bool prepareExplicitEH(Function &F);
   void numberFunclet(BasicBlock *InitialBB, BasicBlock *FuncletBB);
 
   Triple TheTriple;
 
   // All fields are reset by runOnFunction.
   DominatorTree *DT = nullptr;
   const TargetLibraryInfo *LibInfo = nullptr;
while (!Worklist.empty()) {
     if (IsCleanup && isa<CleanupReturnInst>(Terminator))
       continue;
 
     Worklist.insert(Worklist.end(), succ_begin(BB), succ_end(BB));
   }
 }
 
 bool WinEHPrepare::prepareExplicitEH(Function &F) {
-  LLVMContext &Context = F.getContext();
   // Remove unreachable blocks.  It is not valuable to assign them a color and
   // their existence can trick us into thinking values are alive when they are
   // not.
   removeUnreachableBlocks(F);
 
   BasicBlock *EntryBlock = &F.getEntryBlock();
 
   // Number everything starting from the entry block.
for (BasicBlock &BB : F) {
 
     // It is possible for a normal basic block to only be reachable via an
     // exceptional basic block.  The successor of a catchret is the only case
     // where this is possible.
     if (auto *CRI = dyn_cast<CatchReturnInst>(BB.getTerminator()))
       numberFunclet(CRI->getSuccessor(), EntryBlock);
   }
 
-  // Insert cleanuppads before EH blocks with PHI nodes.
+  // Strip PHI nodes off of EH pads.
+  SmallVector<PHINode *, 16> PHINodes;
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
     BasicBlock *BB = FI++;
-    // Skip any BBs which aren't EH pads.
     if (!BB->isEHPad())
       continue;
-    // Skip any cleanuppads, they can hold non-PHI instructions.
-    if (isa<CleanupPadInst>(BB->getFirstNonPHI()))
-      continue;
-    // Skip any EH pads without PHIs, we don't need to worry about demoting into
-    // them.
-    if (!isa<PHINode>(BB->begin()))
-      continue;
-
-    // Create our new cleanuppad BB, terminate it with a cleanupret.
-    auto *NewCleanupBB = BasicBlock::Create(
-        Context, Twine(BB->getName(), ".wineh.phibb"), &F, BB);
-    auto *CPI = CleanupPadInst::Create(Type::getVoidTy(Context), {BB}, "",
-                                       NewCleanupBB);
-    CleanupReturnInst::Create(Context, /*RetVal=*/nullptr, BB, NewCleanupBB);
-
-    // Update the funclet data structures to keep them in the loop.
-    BlockColors[NewCleanupBB].insert(NewCleanupBB);
-    FuncletBlocks[NewCleanupBB].insert(NewCleanupBB);
-
-    // Reparent PHIs from the old EH BB into the cleanuppad.
     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
       Instruction *I = BI++;
       auto *PN = dyn_cast<PHINode>(I);
       // Stop at the first non-PHI.
       if (!PN)
         break;
-      PN->removeFromParent();
-      PN->insertBefore(CPI);
-    }
-
-    // Redirect predecessors from the old EH BB to the cleanuppad.
-    std::set<BasicBlock *> Preds;
-    Preds.insert(pred_begin(BB), pred_end(BB));
-    for (BasicBlock *Pred : Preds) {
-      // Don't redirect the new cleanuppad to itself!
-      if (Pred == NewCleanupBB)
-        continue;
-      TerminatorInst *TI = Pred->getTerminator();
-      for (unsigned TII = 0, TIE = TI->getNumSuccessors(); TII != TIE; ++TII) {
-        BasicBlock *Successor = TI->getSuccessor(TII);
-        if (Successor == BB)
-          TI->setSuccessor(TII, NewCleanupBB);
-      }
-    }
-  }
-
-  // Get rid of polychromatic PHI nodes.
-  for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
-    BasicBlock *BB = FI++;
-    std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
-    bool IsEHPad = BB->isEHPad();
-    for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
-      Instruction *I = BI++;
-      auto *PN = dyn_cast<PHINode>(I);
-      // Stop at the first non-PHI node.
-      if (!PN)
-        break;
 
-      // EH pads cannot be lowered with PHI nodes prefacing them.
-      if (IsEHPad) {
-        // We should have removed PHIs from all non-cleanuppad blocks.
-        if (!isa<CleanupPadInst>(BB->getFirstNonPHI()))
-          report_fatal_error("Unexpected PHI on EH Pad");
-        DemotePHIToStack(PN);
-        continue;
-      }
+      AllocaInst *SpillSlot = insertPHILoads(PN, F);
+      if (SpillSlot)
+        insertPHIStores(PN, SpillSlot);
 
-      // See if *all* the basic blocks involved in this PHI node are in the
-      // same, lone, color.  If so, demotion is not needed.
-      bool SameColor = ColorsForBB.size() == 1;
-      if (SameColor) {
-        for (unsigned PNI = 0, PNE = PN->getNumIncomingValues(); PNI != PNE;
-             ++PNI) {
-          BasicBlock *IncomingBB = PN->getIncomingBlock(PNI);
-          std::set<BasicBlock *> &ColorsForIncomingBB = BlockColors[IncomingBB];
-          // If the colors differ, bail out early and demote.
-          if (ColorsForIncomingBB != ColorsForBB) {
-            SameColor = false;
-            break;
-          }
-        }
-      }
+      PHINodes.push_back(PN);
 
-      if (!SameColor)
-        DemotePHIToStack(PN);
-    }
+  for (auto *PN : PHINodes) {
+    // There may be lingering uses on other EH PHIs being removed
+    PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
+    PN->eraseFromParent();
   }
 
   // Turn all inter-funclet uses of a Value into loads and stores.
   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
     BasicBlock *BB = FI++;
     std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
       Instruction *I = BI++;
       // Funclets are permitted to use static allocas.
       if (auto *AI = dyn_cast<AllocaInst>(I))
         if (AI->isStaticAlloca())
           continue;
 
-      // FIXME: Our spill-placement algorithm is incredibly naive.  We should
-      // try to sink+hoist as much as possible to avoid redundant stores and reloads.
-      DenseMap<BasicBlock *, Value *> Loads;
-      AllocaInst *SpillSlot = nullptr;
-      for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
-           UI != UE;) {
-        Use &U = *UI++;
-        auto *UsingInst = cast<Instruction>(U.getUser());
-        BasicBlock *UsingBB = UsingInst->getParent();
-
-        // Is the Use inside a block which is colored with a subset of the Def?
-        // If so, we don't need to escape the Def because we will clone
-        // ourselves our own private copy.
-        std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
-        if (std::includes(ColorsForBB.begin(), ColorsForBB.end(),
-                          ColorsForUsingBB.begin(), ColorsForUsingBB.end()))
-          continue;
-
-        // Lazilly create the spill slot.  We spill immediately after the value
-        // in the BasicBlock.
-        // FIXME: This can be improved to spill at the block exit points.
-        if (!SpillSlot)
-          SpillSlot = new AllocaInst(I->getType(), nullptr,
-                                     Twine(I->getName(), ".wineh.spillslot"),
-                                     EntryBlock->begin());
-
-        if (auto *PN = dyn_cast<PHINode>(UsingInst)) {
-          // If this is a PHI node, we can't insert a load of the value before
-          // the use.  Instead insert the load in the predecessor block
-          // corresponding to the incoming value.
-          //
-          // Note that if there are multiple edges from a basic block to this
-          // PHI node that we cannot have multiple loads.  The problem is that
-          // the resulting PHI node will have multiple values (from each load)
-          // coming in from the same block, which is illegal SSA form.
-          // For this reason, we keep track of and reuse loads we insert.
-          BasicBlock *IncomingBlock = PN->getIncomingBlock(U);
-          Value *&V = Loads[IncomingBlock];
-          // Insert the load into the predecessor block
-          if (!V)
-            V = new LoadInst(SpillSlot, Twine(I->getName(), ".wineh.reload"),
-                             /*Volatile=*/false,
-                             IncomingBlock->getTerminator());
-          U.set(V);
-        } else {
-          // Reload right before the old use.
-          // FIXME: This can be improved to reload at a block entry point.
-          Value *V =
-              new LoadInst(SpillSlot, Twine(I->getName(), ".wineh.reload"),
-                           /*Volatile=*/false, UsingInst);
-          U.set(V);
-        }
-      }
-      if (SpillSlot) {
-        // Insert stores of the computed value into the stack slot.
-        // We have to be careful if I is an invoke instruction,
-        // because we can't insert the store AFTER the terminator instruction.
-        BasicBlock::iterator InsertPt;
-        if (!isa<TerminatorInst>(I)) {
-          InsertPt = I;
-          ++InsertPt;
-          // Don't insert before PHI nodes or EH pad instrs.
-          for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
-            ;
-        } else {
-          auto *II = cast<InvokeInst>(I);
-          // We cannot demote invoke instructions to the stack if their normal
-          // edge is critical. Therefore, split the critical edge and create a
-          // basic block into which the store can be inserted.
-          if (!II->getNormalDest()->getSinglePredecessor()) {
-            unsigned SuccNum = GetSuccessorNumber(BB, II->getNormalDest());
-            assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
-            BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
-            assert(NewBlock && "Unable to split critical edge.");
-            // Update the color mapping for the newly split edge.
-            std::set<BasicBlock *> &ColorsForUsingBB =
-                BlockColors[II->getParent()];
-            BlockColors[NewBlock] = ColorsForUsingBB;
-            for (BasicBlock *FuncletPad : ColorsForUsingBB)
-              FuncletBlocks[FuncletPad].insert(NewBlock);
-          }
-          InsertPt = II->getNormalDest()->getFirstInsertionPt();
-        }
-        new StoreInst(I, SpillSlot, InsertPt);
-      }
+      demoteNonlocalUses(I, ColorsForBB, F);
     }
   }
+  // Also demote function parameters used in funclets.
+  std::set<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
+  for (Argument &Arg : F.args())
+    demoteNonlocalUses(&Arg, ColorsForEntry, F);
 
   // We need to clone all blocks which belong to multiple funclets.  Values are
   // remapped throughout the funclet to propogate both the new instructions
   // *and* the new basic blocks themselves.
   for (auto &Funclet : FuncletBlocks) {
     BasicBlock *FuncletPadBB = Funclet.first;
     std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
 
for (BasicBlock &BB : F) {
     if (EHPadHasPHI)
       report_fatal_error("EH Pad still has a PHI!");
   }
 
   BlockColors.clear();
   FuncletBlocks.clear();
   return true;
 }
+
+// TODO: Share loads when one use dominates another, or when a catchpad exit
+// dominates uses (needs dominators).
+AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
+  BasicBlock *PHIBlock = PN->getParent();
+  AllocaInst *SpillSlot = nullptr;
+
+  if (isa<CleanupPadInst>(PHIBlock->getFirstNonPHI())) {
+    // Insert a load in place of the PHI and replace all uses.
+    SpillSlot = new AllocaInst(PN->getType(), nullptr,
+                               Twine(PN->getName(), ".wineh.spillslot"),
+                               F.getEntryBlock().begin());
+    Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
+                            PHIBlock->getFirstInsertionPt());
+    PN->replaceAllUsesWith(V);
+    return SpillSlot;
+  }
+
+  DenseMap<BasicBlock *, Value *> Loads;
+  for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
+       UI != UE;) {
+    Use &U = *UI++;
+    auto *UsingInst = cast<Instruction>(U.getUser());
+    BasicBlock *UsingBB = UsingInst->getParent();
+    if (UsingBB->isEHPad()) {
+      // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
+      // stores for it separately.
+      assert(isa<PHINode>(UsingInst));
+      continue;
+    }
+    replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
+  }
+  return SpillSlot;
+}
+
+// TODO: improve store placement.  Inserting at def is probably good, but need
+// to be careful not to introduce interfering stores (needs liveness analysis).
+// TODO: identify related phi nodes that can share spill slots, and share them
+// (also needs liveness).
+void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
+                                   AllocaInst *SpillSlot) {
+  // Use a worklist of (Block, Value) pairs -- the given Value needs to be
+  // stored to the spill slot by the end of the given Block.
+  SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
+
+  Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
+
+  while (!Worklist.empty()) {
+    BasicBlock *EHBlock;
+    Value *InVal;
+    std::tie(EHBlock, InVal) = Worklist.pop_back_val();
+
+    PHINode *PN = dyn_cast<PHINode>(InVal);
+    if (PN && PN->getParent() == EHBlock) {
+      // The value is defined by another PHI we need to remove, with no room to
+      // insert a store after the PHI, so each predecessor needs to store its
+      // incoming value.
+      for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
+        Value *PredVal = PN->getIncomingValue(i);
+
+        // Undef can safely be skipped.
+        if (isa<UndefValue>(PredVal))
+          continue;
+
+        insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
+      }
+    } else {
+      // We need to store InVal, which dominates EHBlock, but can't put a store
+      // in EHBlock, so need to put stores in each predecessor.
+      for (BasicBlock *PredBlock : predecessors(EHBlock)) {
+        insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
+      }
+    }
+  }
+}
+
+void WinEHPrepare::insertPHIStore(
+    BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
+    SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
+
+  if (PredBlock->isEHPad() &&
+      !isa<CleanupPadInst>(PredBlock->getFirstNonPHI())) {
+    // Pred is unsplittable, so we need to queue it on the worklist.
+    Worklist.push_back({PredBlock, PredVal});
+    return;
+  }
+
+  // Otherwise, insert the store at the end of the basic block.
+  new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
+}
+
+// TODO: Share loads for same-funclet uses (requires dominators if funclets
+// aren't properly nested).
+void WinEHPrepare::demoteNonlocalUses(Value *V,
+                                      std::set<BasicBlock *> &ColorsForBB,
+                                      Function &F) {
+  DenseMap<BasicBlock *, Value *> Loads;
+  AllocaInst *SpillSlot = nullptr;
+  for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;) {
+    Use &U = *UI++;
+    auto *UsingInst = cast<Instruction>(U.getUser());
+    BasicBlock *UsingBB = UsingInst->getParent();
+
+    // Is the Use inside a block which is colored with a subset of the Def?
+    // If so, we don't need to escape the Def because we will clone
+    // ourselves our own private copy.
+    std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
+    if (std::includes(ColorsForBB.begin(), ColorsForBB.end(),
+                      ColorsForUsingBB.begin(), ColorsForUsingBB.end()))
+      continue;
+
+    replaceUseWithLoad(V, U, SpillSlot, Loads, F);
+  }
+  if (SpillSlot) {
+    // Insert stores of the computed value into the stack slot.
+    // We have to be careful if I is an invoke instruction,
+    // because we can't insert the store AFTER the terminator instruction.
+    BasicBlock::iterator InsertPt;
+    if (isa<Argument>(V)) {
+      InsertPt = F.getEntryBlock().getTerminator();
+    } else if (isa<TerminatorInst>(V)) {
+      auto *II = cast<InvokeInst>(V);
+      // We cannot demote invoke instructions to the stack if their normal
+      // edge is critical. Therefore, split the critical edge and create a
+      // basic block into which the store can be inserted.
+      if (!II->getNormalDest()->getSinglePredecessor()) {
+        unsigned SuccNum =
+            GetSuccessorNumber(II->getParent(), II->getNormalDest());
+        assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
+        BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
+        assert(NewBlock && "Unable to split critical edge.");
+        // Update the color mapping for the newly split edge.
+        std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[II->getParent()];
+        BlockColors[NewBlock] = ColorsForUsingBB;
+        for (BasicBlock *FuncletPad : ColorsForUsingBB)
+          FuncletBlocks[FuncletPad].insert(NewBlock);
+      }
+      InsertPt = II->getNormalDest()->getFirstInsertionPt();
+    } else {
+      InsertPt = cast<Instruction>(V);
+      ++InsertPt;
+      // Don't insert before PHI nodes or EH pad instrs.
+      for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
+        ;
+    }
+    new StoreInst(V, SpillSlot, InsertPt);
+  }
+}
+
+void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
+                                      DenseMap<BasicBlock *, Value *> &Loads,
+                                      Function &F) {
+  // Lazilly create the spill slot.
+  if (!SpillSlot)
+    SpillSlot = new AllocaInst(V->getType(), nullptr,
+                               Twine(V->getName(), ".wineh.spillslot"),
+                               F.getEntryBlock().begin());
+
+  auto *UsingInst = cast<Instruction>(U.getUser());
+  if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
+    // If this is a PHI node, we can't insert a load of the value before
+    // the use.  Instead insert the load in the predecessor block
+    // corresponding to the incoming value.
+    //
+    // Note that if there are multiple edges from a basic block to this
+    // PHI node that we cannot have multiple loads.  The problem is that
+    // the resulting PHI node will have multiple values (from each load)
+    // coming in from the same block, which is illegal SSA form.
+    // For this reason, we keep track of and reuse loads we insert.
+    BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
+    Value *&Load = Loads[IncomingBlock];
+    // Insert the load into the predecessor block
+    if (!Load)
+      Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
+                          /*Volatile=*/false, IncomingBlock->getTerminator());
+
+    U.set(Load);
+  } else {
+    // Reload right before the old use.
+    auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
+                              /*Volatile=*/false, UsingInst);
+    U.set(Load);
+  }
+}

test/CodeGen/WinEH/wineh-demotion.ll

+; RUN: opt -mtriple=x86_x64-pc-windows-msvc -S -winehprepare  < %s | FileCheck %s
+
+declare i32 @__CxxFrameHandler3(...)
+
+declare void @f()
+
+declare i32 @g()
+
+declare void @h(i32)
+
+declare i1 @i()
+
+; CHECK-LABEL: @test1(
+define void @test1(i1 %B) personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  ; Spill slot should be inserted here
+  ; CHECK: [[Slot:%[^ ]+]] = alloca
+  ; Can't store for %phi at these defs because the lifetimes overlap
+  ; CHECK-NOT: store
+  %x = call i32 @g()
+  %y = call i32 @g()
+  br i1 %B, label %left, label %right
+left:
+  ; CHECK: left:
+  ; CHECK-NEXT: store i32 %x, i32* [[Slot]]
+  ; CHECK-NEXT: invoke void @f
+  invoke void @f()
+          to label %exit unwind label %merge
+right:
+  ; CHECK: right:
+  ; CHECK-NEXT: store i32 %y, i32* [[Slot]]
+  ; CHECK-NEXT: invoke void @f
+  invoke void @f()
+          to label %exit unwind label %merge
+merge:
+  ; CHECK: merge:
+  ; CHECK-NOT: = phi
+  %phi = phi i32 [ %x, %left ], [ %y, %right ]
+  catchpad void [] to label %catch unwind label %catchend
+
+catch:
+  ; CHECK: catch:
+  ; CHECK: [[Reload:%[^ ]+]] = load i32, i32* [[Slot]]
+  ; CHECK-NEXT: call void @h(i32 [[Reload]])
+  call void @h(i32 %phi)
+  catchret label %exit
+
+catchend:
+  catchendpad unwind to caller
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test2(
+define void @test2(i1 %B) personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  br i1 %B, label %left, label %right
+left:
+  ; Need two stores here because %x and %y interfere so they need 2 slots
+  ; CHECK: left:
+  ; CHECK:   store i32 1, i32* [[Slot1:%[^ ]+]]
+  ; CHECK:   store i32 1, i32* [[Slot2:%[^ ]+]]
+  ; CHECK-NEXT: invoke void @f
+  invoke void @f()
+          to label %exit unwind label %merge.inner
+right:
+  ; Need two stores here because %x and %y interfere so they need 2 slots
+  ; CHECK: right:
+  ; CHECK-DAG:   store i32 2, i32* [[Slot1]]
+  ; CHECK-DAG:   store i32 2, i32* [[Slot2]]
+  ; CHECK: invoke void @f
+  invoke void @f()
+          to label %exit unwind label %merge.inner
+merge.inner:
+  ; CHECK: merge.inner:
+  ; CHECK-NOT: = phi
+  ; CHECK: catchpad void
+  %x = phi i32 [ 1, %left ], [ 2, %right ]
+  catchpad void [] to label %catch.inner unwind label %catchend.inner
+
+catch.inner:
+  ; Need just one store here because only %y is affected
+  ; CHECK: catch.inner:
+  %z = call i32 @g()
+  ; CHECK:   store i32 %z
+  ; CHECK-NEXT: invoke void @f
+  invoke void @f()
+          to label %catchret.inner unwind label %merge.outer
+
+catchret.inner:
+  catchret label %exit
+catchend.inner:
+  catchendpad unwind label %merge.outer
+
+merge.outer:
+  ; CHECK: merge.outer:
+  ; CHECK-NOT: = phi
+  ; CHECK: catchpad void
+  %y = phi i32 [ %x, %catchend.inner ], [ %z, %catch.inner ]
+  catchpad void [] to label %catch.outer unwind label %catchend.outer
+
+catchend.outer:
+  catchendpad unwind to caller
+
+catch.outer:
+  ; Need to load x and y from two different slots since they're both live
+  ; and can have different values (if we came from catch.inner)
+  ; CHECK: catch.outer:
+  ; CHECK-DAG: load i32, i32* [[Slot1]]
+  ; CHECK-DAG: load i32, i32* [[Slot2]]
+  ; CHECK: catchret label
+  call void @h(i32 %x)
+  call void @h(i32 %y)
+  catchret label %exit
+
+exit:
+  ret void
+}
+
+; CHECK-LABEL: @test3(
+define void @test3(i1 %B) personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  ; need to spill parameter %B and def %x since they're used in a funclet
+  ; CHECK: entry:
+  ; CHECK-DAG: store i1 %B, i1* [[SlotB:%[^ ]+]]
+  ; CHECK-DAG: store i32 %x, i32* [[SlotX:%[^ ]+]]
+  ; CHECK: invoke void @f
+  %x = call i32 @g()
+  invoke void @f()
+          to label %exit unwind label %catchpad
+
+catchpad:
+  catchpad void [] to label %catch unwind label %catchend
+
+catch:
+  ; Need to reload %B here
+  ; CHECK: catch:
+  ; CHECK: [[ReloadB:%[^ ]+]] = load i1, i1* [[SlotB]]
+  ; CHECK: br i1 [[ReloadB]]
+  br i1 %B, label %left, label %right
+left:
+  ; Use of %x is in a phi, so need reload here in pred
+  ; CHECK: left:
+  ; CHECK: [[ReloadX:%[^ ]+]] = load i32, i32* [[SlotX]]
+  ; CHECK: br label %merge
+  br label %merge
+right:
+  br label %merge
+merge:
+  ; CHECK: merge:
+  ; CHECK:   %phi = phi i32 [ [[ReloadX]], %left ]
+  %phi = phi i32 [ %x, %left ], [ 42, %right ]
+  call void @h(i32 %phi)
+  catchret label %exit
+
+catchend:
+  catchendpad unwind to caller
+
+exit:
+  ret void
+}
+
+; test4: don't need stores for %phi.inner, as its only use is to feed %phi.outer
+;        %phi.outer needs stores in %left, %right, and %join
+; CHECK-LABEL: @test4(
+define void @test4(i1 %B) personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  ; CHECK:      entry:
+  ; CHECK:        [[Slot:%[^ ]+]] = alloca
+  ; CHECK-NEXT:   br
+  br i1 %B, label %left, label %right
+left:
+  ; CHECK: left:
+  ; CHECK-NOT: store
+  ; CHECK: store i32 %l, i32* [[Slot]]
+  ; CHECK-NEXT: invoke void @f
+  %l = call i32 @g()
+  invoke void @f()
+          to label %join unwind label %catchpad.inner
+right:
+  ; CHECK: right:
+  ; CHECK-NOT: store
+  ; CHECK: store i32 %r, i32* [[Slot]]
+  ; CHECK-NEXT: invoke void @f
+  %r = call i32 @g()
+  invoke void @f()
+          to label %join unwind label %catchpad.inner
+catchpad.inner:
+   ; CHECK: catchpad.inner:
+   ; CHECK-NEXT: catchpad void
+   %phi.inner = phi i32 [ %l, %left ], [ %r, %right ]
+   catchpad void [] to label %catch.inner unwind label %catchend.inner
+catch.inner:
+   catchret label %join
+catchend.inner:
+   catchendpad unwind label  %catchpad.outer
+join:
+  ; CHECK: join:
+  ; CHECK-NOT: store
+  ; CHECK: store i32 %j, i32* [[Slot]]
+  ; CHECK-NEXT: invoke void @f
+   %j = call i32 @g()
+   invoke void @f()
+           to label %exit unwind label %catchpad.outer
+catchpad.outer:
+   ; CHECK: catchpad.outer:
+   ; CHECK-NEXT: catchpad void
+   %phi.outer = phi i32 [ %phi.inner, %catchend.inner ], [ %j, %join ]
+   catchpad void [] to label %catch.outer unwind label %catchend.outer
+catch.outer:
+   ; CHECK: catch.outer:
+   ; CHECK:   [[Reload:%[^ ]+]] = load i32, i32* [[Slot]]
+   ; CHECK:   call void @h(i32 [[Reload]])
+   call void @h(i32 %phi.outer)
+   catchret label %exit
+catchend.outer:
+   catchendpad unwind to caller
+exit:
+   ret void
+}
+
+; CHECK-LABEL: @test5(
+define void @test5() personality i32 (...)* @__CxxFrameHandler3 {
+entry:
+  ; need store for %phi.cleanup
+  ; CHECK:      entry:
+  ; CHECK:        store i32 1, i32* [[CleanupSlot:%[^ ]+]]
+  ; CHECK-NEXT:   invoke void @f
+  invoke void @f()
+          to label %invoke.cont unwind label %cleanup
+
+invoke.cont:
+  ; need store for %phi.cleanup
+  ; CHECK:      invoke.cont:
+  ; CHECK-NEXT:   store i32 2, i32* [[CleanupSlot]]
+  ; CHECK-NEXT:   invoke void @f
+  invoke void @f()
+          to label %invoke.cont2 unwind label %cleanup
+
+cleanup:
+  ; cleanup phi can be loaded at cleanup entry
+  ; CHECK: cleanup:
+  ; CHECK-NEXT: cleanuppad void
+  ; CHECK: [[CleanupReload:%[^ ]+]] = load i32, i32* [[CleanupSlot]]
+  %phi.cleanup = phi i32 [ 1, %entry ], [ 2, %invoke.cont ]
+  cleanuppad void []
+  %b = call i1 @i()
+  br i1 %b, label %left, label %right
+
+left:
+  ; CHECK: left:
+  ; CHECK:   call void @h(i32 [[CleanupReload]]
+  call void @h(i32 %phi.cleanup)
+  br label %merge
+
+right:
+  ; CHECK: right:
+  ; CHECK:   call void @h(i32 [[CleanupReload]]
+  call void @h(i32 %phi.cleanup)
+  br label %merge
+
+merge:
+  ; need store for %phi.catch
+  ; CHECK:      merge:
+  ; CHECK-NEXT:   store i32 [[CleanupReload]], i32* [[CatchSlot:%[^ ]+]]
+  ; CHECK-NEXT:   cleanupret void
+  cleanupret void unwind label %catchpad
+
+invoke.cont2:
+  ; need store for %phi.catch
+  ; CHECK:      invoke.cont2:
+  ; CHECK-NEXT:   store i32 3, i32* [[CatchSlot]]
+  ; CHECK-NEXT:   invoke void @f
+  invoke void @f()
+          to label %exit unwind label %catchpad
+
+catchpad:
+  ; CHECK: catchpad:
+  ; CHECK-NEXT: catchpad void
+  %phi.catch = phi i32 [ %phi.cleanup, %merge ], [ 3, %invoke.cont2 ]
+  catchpad void [] to label %catch unwind label %catchend
+
+catch:
+  ; CHECK: catch:
+  ; CHECK:   [[CatchReload:%[^ ]+]] = load i32, i32* [[CatchSlot]]
+  ; CHECK:   call void @h(i32 [[CatchReload]]
+  call void @h(i32 %phi.catch)
+  catchret label %exit
+
+catchend:
+  catchendpad unwind to caller
+
+exit:
+  ret void
+}