lib/CodeGen/WinEHPrepare.cpp

   1 //===-- WinEHPrepare - Prepare exception handling for code generation ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass lowers LLVM IR exception handling into something closer to what the
  11 // backend wants for functions using a personality function from a runtime
  12 // provided by MSVC. Functions with other personality functions are left alone
  13 // and may be prepared by other passes. In particular, all supported MSVC
  14 // personality functions require cleanup code to be outlined, and the C++
  15 // personality requires catch handler code to be outlined.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/ADT/MapVector.h"
  21 #include "llvm/Analysis/CFG.h"
  22 #include "llvm/Analysis/EHPersonalities.h"
  23 #include "llvm/CodeGen/MachineBasicBlock.h"
  24 #include "llvm/CodeGen/WinEHFuncInfo.h"
  25 #include "llvm/IR/Verifier.h"
  26 #include "llvm/MC/MCSymbol.h"
  27 #include "llvm/Pass.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  31 #include "llvm/Transforms/Utils/Cloning.h"
  32 #include "llvm/Transforms/Utils/Local.h"
  33 #include "llvm/Transforms/Utils/SSAUpdater.h"
  34
  35 using namespace llvm;
  36
  37 #define DEBUG_TYPE "winehprepare"
  38
  39 static cl::opt<bool> DisableDemotion(
  40     "disable-demotion", cl::Hidden,
  41     cl::desc(
  42         "Clone multicolor basic blocks but do not demote cross funclet values"),
  43     cl::init(false));
  44
  45 static cl::opt<bool> DisableCleanups(
  46     "disable-cleanups", cl::Hidden,
  47     cl::desc("Do not remove implausible terminators or other similar cleanups"),
  48     cl::init(false));
  49
  50 namespace {
  51
  52 class WinEHPrepare : public FunctionPass {
  53 public:
  54   static char ID; // Pass identification, replacement for typeid.
  55   WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
  56
  57   bool runOnFunction(Function &Fn) override;
  58
  59   bool doFinalization(Module &M) override;
  60
  61   void getAnalysisUsage(AnalysisUsage &AU) const override;
  62
  63   const char *getPassName() const override {
  64     return "Windows exception handling preparation";
  65   }
  66
  67 private:
  68   void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
  69   void
  70   insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
  71                  SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
  72   AllocaInst *insertPHILoads(PHINode *PN, Function &F);
  73   void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
  74                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
  75   bool prepareExplicitEH(Function &F);
  76   void colorFunclets(Function &F);
  77
  78   void demotePHIsOnFunclets(Function &F);
  79   void cloneCommonBlocks(Function &F);
  80   void removeImplausibleInstructions(Function &F);
  81   void cleanupPreparedFunclets(Function &F);
  82   void verifyPreparedFunclets(Function &F);
  83
  84   // All fields are reset by runOnFunction.
  85   EHPersonality Personality = EHPersonality::Unknown;
  86
  87   DenseMap<BasicBlock *, ColorVector> BlockColors;
  88   MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
  89 };
  90
  91 } // end anonymous namespace
  92
  93 char WinEHPrepare::ID = 0;
  94 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
  95                    false, false)
  96
  97 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
  98   return new WinEHPrepare(TM);
  99 }
 100
 101 bool WinEHPrepare::runOnFunction(Function &Fn) {
 102   if (!Fn.hasPersonalityFn())
 103     return false;
 104
 105   // Classify the personality to see what kind of preparation we need.
 106   Personality = classifyEHPersonality(Fn.getPersonalityFn());
 107
 108   // Do nothing if this is not a funclet-based personality.
 109   if (!isFuncletEHPersonality(Personality))
 110     return false;
 111
 112   return prepareExplicitEH(Fn);
 113 }
 114
 115 bool WinEHPrepare::doFinalization(Module &M) { return false; }
 116
 117 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
 118
 119 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
 120                              const BasicBlock *BB) {
 121   CxxUnwindMapEntry UME;
 122   UME.ToState = ToState;
 123   UME.Cleanup = BB;
 124   FuncInfo.CxxUnwindMap.push_back(UME);
 125   return FuncInfo.getLastStateNumber();
 126 }
 127
 128 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
 129                                 int TryHigh, int CatchHigh,
 130                                 ArrayRef<const CatchPadInst *> Handlers) {
 131   WinEHTryBlockMapEntry TBME;
 132   TBME.TryLow = TryLow;
 133   TBME.TryHigh = TryHigh;
 134   TBME.CatchHigh = CatchHigh;
 135   assert(TBME.TryLow <= TBME.TryHigh);
 136   for (const CatchPadInst *CPI : Handlers) {
 137     WinEHHandlerType HT;
 138     Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
 139     if (TypeInfo->isNullValue())
 140       HT.TypeDescriptor = nullptr;
 141     else
 142       HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
 143     HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
 144     HT.Handler = CPI->getParent();
 145     if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
 146       HT.CatchObj.Alloca = nullptr;
 147     else
 148       HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
 149     TBME.HandlerArray.push_back(HT);
 150   }
 151   FuncInfo.TryBlockMap.push_back(TBME);
 152 }
 153
 154 static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
 155   for (const User *U : CleanupPad->users())
 156     if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
 157       return CRI->getUnwindDest();
 158   return nullptr;
 159 }
 160
 161 static void calculateStateNumbersForInvokes(const Function *Fn,
 162                                             WinEHFuncInfo &FuncInfo) {
 163   auto *F = const_cast<Function *>(Fn);
 164   DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
 165   for (BasicBlock &BB : *F) {
 166     auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
 167     if (!II)
 168       continue;
 169
 170     auto &BBColors = BlockColors[&BB];
 171     assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
 172     BasicBlock *FuncletEntryBB = BBColors.front();
 173
 174     BasicBlock *FuncletUnwindDest;
 175     auto *FuncletPad =
 176         dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
 177     assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
 178     if (!FuncletPad)
 179       FuncletUnwindDest = nullptr;
 180     else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
 181       FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
 182     else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
 183       FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
 184     else
 185       llvm_unreachable("unexpected funclet pad!");
 186
 187     BasicBlock *InvokeUnwindDest = II->getUnwindDest();
 188     int BaseState = -1;
 189     if (FuncletUnwindDest == InvokeUnwindDest) {
 190       auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
 191       if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
 192         BaseState = BaseStateI->second;
 193     }
 194
 195     if (BaseState != -1) {
 196       FuncInfo.InvokeStateMap[II] = BaseState;
 197     } else {
 198       Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
 199       assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
 200       FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
 201     }
 202   }
 203 }
 204
 205 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
 206 // to. If the unwind edge came from an invoke, return null.
 207 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
 208                                                  Value *ParentPad) {
 209   const TerminatorInst *TI = BB->getTerminator();
 210   if (isa<InvokeInst>(TI))
 211     return nullptr;
 212   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
 213     if (CatchSwitch->getParentPad() != ParentPad)
 214       return nullptr;
 215     return BB;
 216   }
 217   assert(!TI->isEHPad() && "unexpected EHPad!");
 218   auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
 219   if (CleanupPad->getParentPad() != ParentPad)
 220     return nullptr;
 221   return CleanupPad->getParent();
 222 }
 223
 224 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
 225                                      const Instruction *FirstNonPHI,
 226                                      int ParentState) {
 227   const BasicBlock *BB = FirstNonPHI->getParent();
 228   assert(BB->isEHPad() && "not a funclet!");
 229
 230   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
 231     assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
 232            "shouldn't revist catch funclets!");
 233
 234     SmallVector<const CatchPadInst *, 2> Handlers;
 235     for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
 236       auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
 237       Handlers.push_back(CatchPad);
 238     }
 239     int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
 240     FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
 241     for (const BasicBlock *PredBlock : predecessors(BB))
 242       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
 243                                                CatchSwitch->getParentPad())))
 244         calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 245                                  TryLow);
 246     int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
 247
 248     // catchpads are separate funclets in C++ EH due to the way rethrow works.
 249     int TryHigh = CatchLow - 1;
 250     for (const auto *CatchPad : Handlers) {
 251       FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
 252       for (const User *U : CatchPad->users()) {
 253         const auto *UserI = cast<Instruction>(U);
 254         if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
 255           if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
 256             calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
 257         if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
 258           if (getCleanupRetUnwindDest(InnerCleanupPad) ==
 259               CatchSwitch->getUnwindDest())
 260             calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
 261       }
 262     }
 263     int CatchHigh = FuncInfo.getLastStateNumber();
 264     addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
 265     DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
 266     DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh << '\n');
 267     DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
 268                  << '\n');
 269   } else {
 270     auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
 271
 272     // It's possible for a cleanup to be visited twice: it might have multiple
 273     // cleanupret instructions.
 274     if (FuncInfo.EHPadStateMap.count(CleanupPad))
 275       return;
 276
 277     int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
 278     FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
 279     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
 280                  << BB->getName() << '\n');
 281     for (const BasicBlock *PredBlock : predecessors(BB)) {
 282       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
 283                                                CleanupPad->getParentPad()))) {
 284         calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 285                                  CleanupState);
 286       }
 287     }
 288     for (const User *U : CleanupPad->users()) {
 289       const auto *UserI = cast<Instruction>(U);
 290       if (UserI->isEHPad())
 291         report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
 292                            "contain exceptional actions");
 293     }
 294   }
 295 }
 296
 297 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
 298                         const Function *Filter, const BasicBlock *Handler) {
 299   SEHUnwindMapEntry Entry;
 300   Entry.ToState = ParentState;
 301   Entry.IsFinally = false;
 302   Entry.Filter = Filter;
 303   Entry.Handler = Handler;
 304   FuncInfo.SEHUnwindMap.push_back(Entry);
 305   return FuncInfo.SEHUnwindMap.size() - 1;
 306 }
 307
 308 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
 309                          const BasicBlock *Handler) {
 310   SEHUnwindMapEntry Entry;
 311   Entry.ToState = ParentState;
 312   Entry.IsFinally = true;
 313   Entry.Filter = nullptr;
 314   Entry.Handler = Handler;
 315   FuncInfo.SEHUnwindMap.push_back(Entry);
 316   return FuncInfo.SEHUnwindMap.size() - 1;
 317 }
 318
 319 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
 320                                      const Instruction *FirstNonPHI,
 321                                      int ParentState) {
 322   const BasicBlock *BB = FirstNonPHI->getParent();
 323   assert(BB->isEHPad() && "no a funclet!");
 324
 325   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
 326     assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
 327            "shouldn't revist catch funclets!");
 328
 329     // Extract the filter function and the __except basic block and create a
 330     // state for them.
 331     assert(CatchSwitch->getNumHandlers() == 1 &&
 332            "SEH doesn't have multiple handlers per __try");
 333     const auto *CatchPad =
 334         cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
 335     const BasicBlock *CatchPadBB = CatchPad->getParent();
 336     const Constant *FilterOrNull =
 337         cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
 338     const Function *Filter = dyn_cast<Function>(FilterOrNull);
 339     assert((Filter || FilterOrNull->isNullValue()) &&
 340            "unexpected filter value");
 341     int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
 342
 343     // Everything in the __try block uses TryState as its parent state.
 344     FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
 345     DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
 346                  << CatchPadBB->getName() << '\n');
 347     for (const BasicBlock *PredBlock : predecessors(BB))
 348       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
 349                                                CatchSwitch->getParentPad())))
 350         calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 351                                  TryState);
 352
 353     // Everything in the __except block unwinds to ParentState, just like code
 354     // outside the __try.
 355     for (const User *U : CatchPad->users()) {
 356       const auto *UserI = cast<Instruction>(U);
 357       if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
 358         if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
 359           calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
 360       if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
 361         if (getCleanupRetUnwindDest(InnerCleanupPad) ==
 362             CatchSwitch->getUnwindDest())
 363           calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
 364     }
 365   } else {
 366     auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
 367
 368     // It's possible for a cleanup to be visited twice: it might have multiple
 369     // cleanupret instructions.
 370     if (FuncInfo.EHPadStateMap.count(CleanupPad))
 371       return;
 372
 373     int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
 374     FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
 375     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
 376                  << BB->getName() << '\n');
 377     for (const BasicBlock *PredBlock : predecessors(BB))
 378       if ((PredBlock =
 379                getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
 380         calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 381                                  CleanupState);
 382     for (const User *U : CleanupPad->users()) {
 383       const auto *UserI = cast<Instruction>(U);
 384       if (UserI->isEHPad())
 385         report_fatal_error("Cleanup funclets for the SEH personality cannot "
 386                            "contain exceptional actions");
 387     }
 388   }
 389 }
 390
 391 static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
 392   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
 393     return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
 394            CatchSwitch->unwindsToCaller();
 395   if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
 396     return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
 397            getCleanupRetUnwindDest(CleanupPad) == nullptr;
 398   if (isa<CatchPadInst>(EHPad))
 399     return false;
 400   llvm_unreachable("unexpected EHPad!");
 401 }
 402
 403 void llvm::calculateSEHStateNumbers(const Function *Fn,
 404                                     WinEHFuncInfo &FuncInfo) {
 405   // Don't compute state numbers twice.
 406   if (!FuncInfo.SEHUnwindMap.empty())
 407     return;
 408
 409   for (const BasicBlock &BB : *Fn) {
 410     if (!BB.isEHPad())
 411       continue;
 412     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 413     if (!isTopLevelPadForMSVC(FirstNonPHI))
 414       continue;
 415     ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
 416   }
 417
 418   calculateStateNumbersForInvokes(Fn, FuncInfo);
 419 }
 420
 421 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
 422                                          WinEHFuncInfo &FuncInfo) {
 423   // Return if it's already been done.
 424   if (!FuncInfo.EHPadStateMap.empty())
 425     return;
 426
 427   for (const BasicBlock &BB : *Fn) {
 428     if (!BB.isEHPad())
 429       continue;
 430     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 431     if (!isTopLevelPadForMSVC(FirstNonPHI))
 432       continue;
 433     calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
 434   }
 435
 436   calculateStateNumbersForInvokes(Fn, FuncInfo);
 437 }
 438
 439 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
 440                            ClrHandlerType HandlerType, uint32_t TypeToken,
 441                            const BasicBlock *Handler) {
 442   ClrEHUnwindMapEntry Entry;
 443   Entry.Parent = ParentState;
 444   Entry.Handler = Handler;
 445   Entry.HandlerType = HandlerType;
 446   Entry.TypeToken = TypeToken;
 447   FuncInfo.ClrEHUnwindMap.push_back(Entry);
 448   return FuncInfo.ClrEHUnwindMap.size() - 1;
 449 }
 450
 451 void llvm::calculateClrEHStateNumbers(const Function *Fn,
 452                                       WinEHFuncInfo &FuncInfo) {
 453   // Return if it's already been done.
 454   if (!FuncInfo.EHPadStateMap.empty())
 455     return;
 456
 457   SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
 458
 459   // Each pad needs to be able to refer to its parent, so scan the function
 460   // looking for top-level handlers and seed the worklist with them.
 461   for (const BasicBlock &BB : *Fn) {
 462     if (!BB.isEHPad())
 463       continue;
 464     if (BB.isLandingPad())
 465       report_fatal_error("CoreCLR EH cannot use landingpads");
 466     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 467     if (!isTopLevelPadForMSVC(FirstNonPHI))
 468       continue;
 469     // queue this with sentinel parent state -1 to mean unwind to caller.
 470     Worklist.emplace_back(FirstNonPHI, -1);
 471   }
 472
 473   while (!Worklist.empty()) {
 474     const Instruction *Pad;
 475     int ParentState;
 476     std::tie(Pad, ParentState) = Worklist.pop_back_val();
 477
 478     Value *ParentPad;
 479     int PredState;
 480     if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
 481       // A cleanup can have multiple exits; don't re-process after the first.
 482       if (FuncInfo.EHPadStateMap.count(Cleanup))
 483         continue;
 484       // CoreCLR personality uses arity to distinguish faults from finallies.
 485       const BasicBlock *PadBlock = Cleanup->getParent();
 486       ClrHandlerType HandlerType =
 487           (Cleanup->getNumOperands() ? ClrHandlerType::Fault
 488                                      : ClrHandlerType::Finally);
 489       int NewState =
 490           addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
 491       FuncInfo.EHPadStateMap[Cleanup] = NewState;
 492       // Propagate the new state to all preds of the cleanup
 493       ParentPad = Cleanup->getParentPad();
 494       PredState = NewState;
 495     } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
 496       SmallVector<const CatchPadInst *, 1> Handlers;
 497       for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
 498         const auto *Catch = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
 499         Handlers.push_back(Catch);
 500       }
 501       FuncInfo.EHPadStateMap[CatchSwitch] = ParentState;
 502       int NewState = ParentState;
 503       for (auto HandlerI = Handlers.rbegin(), HandlerE = Handlers.rend();
 504            HandlerI != HandlerE; ++HandlerI) {
 505         const CatchPadInst *Catch = *HandlerI;
 506         const BasicBlock *PadBlock = Catch->getParent();
 507         uint32_t TypeToken = static_cast<uint32_t>(
 508             cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
 509         NewState = addClrEHHandler(FuncInfo, NewState, ClrHandlerType::Catch,
 510                                    TypeToken, PadBlock);
 511         FuncInfo.EHPadStateMap[Catch] = NewState;
 512       }
 513       for (const auto *CatchPad : Handlers) {
 514         for (const User *U : CatchPad->users()) {
 515           const auto *UserI = cast<Instruction>(U);
 516           if (UserI->isEHPad())
 517             Worklist.emplace_back(UserI, ParentState);
 518         }
 519       }
 520       PredState = NewState;
 521       ParentPad = CatchSwitch->getParentPad();
 522     } else {
 523       llvm_unreachable("Unexpected EH pad");
 524     }
 525
 526     // Queue all predecessors with the given state
 527     for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
 528       if ((Pred = getEHPadFromPredecessor(Pred, ParentPad)))
 529         Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
 530     }
 531   }
 532
 533   calculateStateNumbersForInvokes(Fn, FuncInfo);
 534 }
 535
 536 void WinEHPrepare::colorFunclets(Function &F) {
 537   BlockColors = colorEHFunclets(F);
 538
 539   // Invert the map from BB to colors to color to BBs.
 540   for (BasicBlock &BB : F) {
 541     ColorVector &Colors = BlockColors[&BB];
 542     for (BasicBlock *Color : Colors)
 543       FuncletBlocks[Color].push_back(&BB);
 544   }
 545 }
 546
 547 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
 548                                                WinEHFuncInfo &FuncInfo) {
 549   for (const BasicBlock &BB : *Fn) {
 550     const auto *CatchRet = dyn_cast<CatchReturnInst>(BB.getTerminator());
 551     if (!CatchRet)
 552       continue;
 553     // A 'catchret' returns to the outer scope's color.
 554     Value *ParentPad = CatchRet->getParentPad();
 555     const BasicBlock *Color;
 556     if (isa<ConstantTokenNone>(ParentPad))
 557       Color = &Fn->getEntryBlock();
 558     else
 559       Color = cast<Instruction>(ParentPad)->getParent();
 560     // Record the catchret successor's funclet membership.
 561     FuncInfo.CatchRetSuccessorColorMap[CatchRet] = Color;
 562   }
 563 }
 564
 565 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
 566   // Strip PHI nodes off of EH pads.
 567   SmallVector<PHINode *, 16> PHINodes;
 568   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 569     BasicBlock *BB = &*FI++;
 570     if (!BB->isEHPad())
 571       continue;
 572     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
 573       Instruction *I = &*BI++;
 574       auto *PN = dyn_cast<PHINode>(I);
 575       // Stop at the first non-PHI.
 576       if (!PN)
 577         break;
 578
 579       AllocaInst *SpillSlot = insertPHILoads(PN, F);
 580       if (SpillSlot)
 581         insertPHIStores(PN, SpillSlot);
 582
 583       PHINodes.push_back(PN);
 584     }
 585   }
 586
 587   for (auto *PN : PHINodes) {
 588     // There may be lingering uses on other EH PHIs being removed
 589     PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 590     PN->eraseFromParent();
 591   }
 592 }
 593
 594 void WinEHPrepare::cloneCommonBlocks(Function &F) {
 595   // We need to clone all blocks which belong to multiple funclets.  Values are
 596   // remapped throughout the funclet to propogate both the new instructions
 597   // *and* the new basic blocks themselves.
 598   for (auto &Funclets : FuncletBlocks) {
 599     BasicBlock *FuncletPadBB = Funclets.first;
 600     std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
 601     Value *FuncletToken;
 602     if (FuncletPadBB == &F.getEntryBlock())
 603       FuncletToken = ConstantTokenNone::get(F.getContext());
 604     else
 605       FuncletToken = FuncletPadBB->getFirstNonPHI();
 606
 607     std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
 608     ValueToValueMapTy VMap;
 609     for (BasicBlock *BB : BlocksInFunclet) {
 610       ColorVector &ColorsForBB = BlockColors[BB];
 611       // We don't need to do anything if the block is monochromatic.
 612       size_t NumColorsForBB = ColorsForBB.size();
 613       if (NumColorsForBB == 1)
 614         continue;
 615
 616       DEBUG_WITH_TYPE("winehprepare-coloring",
 617                       dbgs() << "  Cloning block \'" << BB->getName()
 618                               << "\' for funclet \'" << FuncletPadBB->getName()
 619                               << "\'.\n");
 620
 621       // Create a new basic block and copy instructions into it!
 622       BasicBlock *CBB =
 623           CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
 624       // Insert the clone immediately after the original to ensure determinism
 625       // and to keep the same relative ordering of any funclet's blocks.
 626       CBB->insertInto(&F, BB->getNextNode());
 627
 628       // Add basic block mapping.
 629       VMap[BB] = CBB;
 630
 631       // Record delta operations that we need to perform to our color mappings.
 632       Orig2Clone.emplace_back(BB, CBB);
 633     }
 634
 635     // If nothing was cloned, we're done cloning in this funclet.
 636     if (Orig2Clone.empty())
 637       continue;
 638
 639     // Update our color mappings to reflect that one block has lost a color and
 640     // another has gained a color.
 641     for (auto &BBMapping : Orig2Clone) {
 642       BasicBlock *OldBlock = BBMapping.first;
 643       BasicBlock *NewBlock = BBMapping.second;
 644
 645       BlocksInFunclet.push_back(NewBlock);
 646       ColorVector &NewColors = BlockColors[NewBlock];
 647       assert(NewColors.empty() && "A new block should only have one color!");
 648       NewColors.push_back(FuncletPadBB);
 649
 650       DEBUG_WITH_TYPE("winehprepare-coloring",
 651                       dbgs() << "  Assigned color \'" << FuncletPadBB->getName()
 652                               << "\' to block \'" << NewBlock->getName()
 653                               << "\'.\n");
 654
 655       BlocksInFunclet.erase(
 656           std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
 657           BlocksInFunclet.end());
 658       ColorVector &OldColors = BlockColors[OldBlock];
 659       OldColors.erase(
 660           std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
 661           OldColors.end());
 662
 663       DEBUG_WITH_TYPE("winehprepare-coloring",
 664                       dbgs() << "  Removed color \'" << FuncletPadBB->getName()
 665                               << "\' from block \'" << OldBlock->getName()
 666                               << "\'.\n");
 667     }
 668
 669     // Loop over all of the instructions in this funclet, fixing up operand
 670     // references as we go.  This uses VMap to do all the hard work.
 671     for (BasicBlock *BB : BlocksInFunclet)
 672       // Loop over all instructions, fixing each one as we find it...
 673       for (Instruction &I : *BB)
 674         RemapInstruction(&I, VMap,
 675                          RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
 676
 677     // Catchrets targeting cloned blocks need to be updated separately from
 678     // the loop above because they are not in the current funclet.
 679     SmallVector<CatchReturnInst *, 2> FixupCatchrets;
 680     for (auto &BBMapping : Orig2Clone) {
 681       BasicBlock *OldBlock = BBMapping.first;
 682       BasicBlock *NewBlock = BBMapping.second;
 683
 684       FixupCatchrets.clear();
 685       for (BasicBlock *Pred : predecessors(OldBlock))
 686         if (auto *CatchRet = dyn_cast<CatchReturnInst>(Pred->getTerminator()))
 687           if (CatchRet->getParentPad() == FuncletToken)
 688             FixupCatchrets.push_back(CatchRet);
 689
 690       for (CatchReturnInst *CatchRet : FixupCatchrets)
 691         CatchRet->setSuccessor(NewBlock);
 692     }
 693
 694     auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
 695       unsigned NumPreds = PN->getNumIncomingValues();
 696       for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
 697            ++PredIdx) {
 698         BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
 699         bool EdgeTargetsFunclet;
 700         if (auto *CRI =
 701                 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
 702           EdgeTargetsFunclet = (CRI->getParentPad() == FuncletToken);
 703         } else {
 704           ColorVector &IncomingColors = BlockColors[IncomingBlock];
 705           assert(!IncomingColors.empty() && "Block not colored!");
 706           assert((IncomingColors.size() == 1 ||
 707                   llvm::all_of(IncomingColors,
 708                                [&](BasicBlock *Color) {
 709                                  return Color != FuncletPadBB;
 710                                })) &&
 711                  "Cloning should leave this funclet's blocks monochromatic");
 712           EdgeTargetsFunclet = (IncomingColors.front() == FuncletPadBB);
 713         }
 714         if (IsForOldBlock != EdgeTargetsFunclet)
 715           continue;
 716         PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
 717         // Revisit the next entry.
 718         --PredIdx;
 719         --PredEnd;
 720       }
 721     };
 722
 723     for (auto &BBMapping : Orig2Clone) {
 724       BasicBlock *OldBlock = BBMapping.first;
 725       BasicBlock *NewBlock = BBMapping.second;
 726       for (Instruction &OldI : *OldBlock) {
 727         auto *OldPN = dyn_cast<PHINode>(&OldI);
 728         if (!OldPN)
 729           break;
 730         UpdatePHIOnClonedBlock(OldPN, /*IsForOldBlock=*/true);
 731       }
 732       for (Instruction &NewI : *NewBlock) {
 733         auto *NewPN = dyn_cast<PHINode>(&NewI);
 734         if (!NewPN)
 735           break;
 736         UpdatePHIOnClonedBlock(NewPN, /*IsForOldBlock=*/false);
 737       }
 738     }
 739
 740     // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
 741     // the PHI nodes for NewBB now.
 742     for (auto &BBMapping : Orig2Clone) {
 743       BasicBlock *OldBlock = BBMapping.first;
 744       BasicBlock *NewBlock = BBMapping.second;
 745       for (BasicBlock *SuccBB : successors(NewBlock)) {
 746         for (Instruction &SuccI : *SuccBB) {
 747           auto *SuccPN = dyn_cast<PHINode>(&SuccI);
 748           if (!SuccPN)
 749             break;
 750
 751           // Ok, we have a PHI node.  Figure out what the incoming value was for
 752           // the OldBlock.
 753           int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
 754           if (OldBlockIdx == -1)
 755             break;
 756           Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
 757
 758           // Remap the value if necessary.
 759           if (auto *Inst = dyn_cast<Instruction>(IV)) {
 760             ValueToValueMapTy::iterator I = VMap.find(Inst);
 761             if (I != VMap.end())
 762               IV = I->second;
 763           }
 764
 765           SuccPN->addIncoming(IV, NewBlock);
 766         }
 767       }
 768     }
 769
 770     for (ValueToValueMapTy::value_type VT : VMap) {
 771       // If there were values defined in BB that are used outside the funclet,
 772       // then we now have to update all uses of the value to use either the
 773       // original value, the cloned value, or some PHI derived value.  This can
 774       // require arbitrary PHI insertion, of which we are prepared to do, clean
 775       // these up now.
 776       SmallVector<Use *, 16> UsesToRename;
 777
 778       auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
 779       if (!OldI)
 780         continue;
 781       auto *NewI = cast<Instruction>(VT.second);
 782       // Scan all uses of this instruction to see if it is used outside of its
 783       // funclet, and if so, record them in UsesToRename.
 784       for (Use &U : OldI->uses()) {
 785         Instruction *UserI = cast<Instruction>(U.getUser());
 786         BasicBlock *UserBB = UserI->getParent();
 787         ColorVector &ColorsForUserBB = BlockColors[UserBB];
 788         assert(!ColorsForUserBB.empty());
 789         if (ColorsForUserBB.size() > 1 ||
 790             *ColorsForUserBB.begin() != FuncletPadBB)
 791           UsesToRename.push_back(&U);
 792       }
 793
 794       // If there are no uses outside the block, we're done with this
 795       // instruction.
 796       if (UsesToRename.empty())
 797         continue;
 798
 799       // We found a use of OldI outside of the funclet.  Rename all uses of OldI
 800       // that are outside its funclet to be uses of the appropriate PHI node
 801       // etc.
 802       SSAUpdater SSAUpdate;
 803       SSAUpdate.Initialize(OldI->getType(), OldI->getName());
 804       SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
 805       SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
 806
 807       while (!UsesToRename.empty())
 808         SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
 809     }
 810   }
 811 }
 812
 813 void WinEHPrepare::removeImplausibleInstructions(Function &F) {
 814   // Remove implausible terminators and replace them with UnreachableInst.
 815   for (auto &Funclet : FuncletBlocks) {
 816     BasicBlock *FuncletPadBB = Funclet.first;
 817     std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
 818     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
 819     auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);
 820     auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);
 821     auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);
 822
 823     for (BasicBlock *BB : BlocksInFunclet) {
 824       for (Instruction &I : *BB) {
 825         CallSite CS(&I);
 826         if (!CS)
 827           continue;
 828
 829         Value *FuncletBundleOperand = nullptr;
 830         if (auto BU = CS.getOperandBundle(LLVMContext::OB_funclet))
 831           FuncletBundleOperand = BU->Inputs.front();
 832
 833         if (FuncletBundleOperand == FuncletPad)
 834           continue;
 835
 836         // Skip call sites which are nounwind intrinsics.
 837         auto *CalledFn =
 838             dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
 839         if (CalledFn && CalledFn->isIntrinsic() && CS.doesNotThrow())
 840           continue;
 841
 842         // This call site was not part of this funclet, remove it.
 843         if (CS.isInvoke()) {
 844           // Remove the unwind edge if it was an invoke.
 845           removeUnwindEdge(BB);
 846           // Get a pointer to the new call.
 847           BasicBlock::iterator CallI =
 848               std::prev(BB->getTerminator()->getIterator());
 849           auto *CI = cast<CallInst>(&*CallI);
 850           changeToUnreachable(CI, /*UseLLVMTrap=*/false);
 851         } else {
 852           changeToUnreachable(&I, /*UseLLVMTrap=*/false);
 853         }
 854
 855         // There are no more instructions in the block (except for unreachable),
 856         // we are done.
 857         break;
 858       }
 859
 860       TerminatorInst *TI = BB->getTerminator();
 861       // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
 862       bool IsUnreachableRet = isa<ReturnInst>(TI) && FuncletPad;
 863       // The token consumed by a CatchReturnInst must match the funclet token.
 864       bool IsUnreachableCatchret = false;
 865       if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
 866         IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
 867       // The token consumed by a CleanupReturnInst must match the funclet token.
 868       bool IsUnreachableCleanupret = false;
 869       if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
 870         IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
 871       if (IsUnreachableRet || IsUnreachableCatchret ||
 872           IsUnreachableCleanupret) {
 873         changeToUnreachable(TI, /*UseLLVMTrap=*/false);
 874       } else if (isa<InvokeInst>(TI)) {
 875         if (Personality == EHPersonality::MSVC_CXX && CleanupPad) {
 876           // Invokes within a cleanuppad for the MSVC++ personality never
 877           // transfer control to their unwind edge: the personality will
 878           // terminate the program.
 879           removeUnwindEdge(BB);
 880         }
 881       }
 882     }
 883   }
 884 }
 885
 886 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
 887   // Clean-up some of the mess we made by removing useles PHI nodes, trivial
 888   // branches, etc.
 889   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 890     BasicBlock *BB = &*FI++;
 891     SimplifyInstructionsInBlock(BB);
 892     ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
 893     MergeBlockIntoPredecessor(BB);
 894   }
 895
 896   // We might have some unreachable blocks after cleaning up some impossible
 897   // control flow.
 898   removeUnreachableBlocks(F);
 899 }
 900
 901 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
 902   for (BasicBlock &BB : F) {
 903     size_t NumColors = BlockColors[&BB].size();
 904     assert(NumColors == 1 && "Expected monochromatic BB!");
 905     if (NumColors == 0)
 906       report_fatal_error("Uncolored BB!");
 907     if (NumColors > 1)
 908       report_fatal_error("Multicolor BB!");
 909     if (!DisableDemotion) {
 910       bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
 911       assert(!EHPadHasPHI && "EH Pad still has a PHI!");
 912     }
 913   }
 914 }
 915
 916 bool WinEHPrepare::prepareExplicitEH(Function &F) {
 917   // Remove unreachable blocks.  It is not valuable to assign them a color and
 918   // their existence can trick us into thinking values are alive when they are
 919   // not.
 920   removeUnreachableBlocks(F);
 921
 922   // Determine which blocks are reachable from which funclet entries.
 923   colorFunclets(F);
 924
 925   cloneCommonBlocks(F);
 926
 927   if (!DisableDemotion)
 928     demotePHIsOnFunclets(F);
 929
 930   if (!DisableCleanups) {
 931     DEBUG(verifyFunction(F));
 932     removeImplausibleInstructions(F);
 933
 934     DEBUG(verifyFunction(F));
 935     cleanupPreparedFunclets(F);
 936   }
 937
 938   DEBUG(verifyPreparedFunclets(F));
 939   // Recolor the CFG to verify that all is well.
 940   DEBUG(colorFunclets(F));
 941   DEBUG(verifyPreparedFunclets(F));
 942
 943   BlockColors.clear();
 944   FuncletBlocks.clear();
 945
 946   return true;
 947 }
 948
 949 // TODO: Share loads when one use dominates another, or when a catchpad exit
 950 // dominates uses (needs dominators).
 951 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
 952   BasicBlock *PHIBlock = PN->getParent();
 953   AllocaInst *SpillSlot = nullptr;
 954   Instruction *EHPad = PHIBlock->getFirstNonPHI();
 955
 956   if (!isa<TerminatorInst>(EHPad)) {
 957     // If the EHPad isn't a terminator, then we can insert a load in this block
 958     // that will dominate all uses.
 959     SpillSlot = new AllocaInst(PN->getType(), nullptr,
 960                                Twine(PN->getName(), ".wineh.spillslot"),
 961                                &F.getEntryBlock().front());
 962     Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
 963                             &*PHIBlock->getFirstInsertionPt());
 964     PN->replaceAllUsesWith(V);
 965     return SpillSlot;
 966   }
 967
 968   // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
 969   // loads of the slot before every use.
 970   DenseMap<BasicBlock *, Value *> Loads;
 971   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
 972        UI != UE;) {
 973     Use &U = *UI++;
 974     auto *UsingInst = cast<Instruction>(U.getUser());
 975     if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
 976       // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
 977       // stores for it separately.
 978       continue;
 979     }
 980     replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
 981   }
 982   return SpillSlot;
 983 }
 984
 985 // TODO: improve store placement.  Inserting at def is probably good, but need
 986 // to be careful not to introduce interfering stores (needs liveness analysis).
 987 // TODO: identify related phi nodes that can share spill slots, and share them
 988 // (also needs liveness).
 989 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
 990                                    AllocaInst *SpillSlot) {
 991   // Use a worklist of (Block, Value) pairs -- the given Value needs to be
 992   // stored to the spill slot by the end of the given Block.
 993   SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
 994
 995   Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
 996
 997   while (!Worklist.empty()) {
 998     BasicBlock *EHBlock;
 999     Value *InVal;
1000     std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1001
1002     PHINode *PN = dyn_cast<PHINode>(InVal);
1003     if (PN && PN->getParent() == EHBlock) {
1004       // The value is defined by another PHI we need to remove, with no room to
1005       // insert a store after the PHI, so each predecessor needs to store its
1006       // incoming value.
1007       for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1008         Value *PredVal = PN->getIncomingValue(i);
1009
1010         // Undef can safely be skipped.
1011         if (isa<UndefValue>(PredVal))
1012           continue;
1013
1014         insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1015       }
1016     } else {
1017       // We need to store InVal, which dominates EHBlock, but can't put a store
1018       // in EHBlock, so need to put stores in each predecessor.
1019       for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1020         insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1021       }
1022     }
1023   }
1024 }
1025
1026 void WinEHPrepare::insertPHIStore(
1027     BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1028     SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1029
1030   if (PredBlock->isEHPad() &&
1031       isa<TerminatorInst>(PredBlock->getFirstNonPHI())) {
1032     // Pred is unsplittable, so we need to queue it on the worklist.
1033     Worklist.push_back({PredBlock, PredVal});
1034     return;
1035   }
1036
1037   // Otherwise, insert the store at the end of the basic block.
1038   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1039 }
1040
1041 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1042                                       DenseMap<BasicBlock *, Value *> &Loads,
1043                                       Function &F) {
1044   // Lazilly create the spill slot.
1045   if (!SpillSlot)
1046     SpillSlot = new AllocaInst(V->getType(), nullptr,
1047                                Twine(V->getName(), ".wineh.spillslot"),
1048                                &F.getEntryBlock().front());
1049
1050   auto *UsingInst = cast<Instruction>(U.getUser());
1051   if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1052     // If this is a PHI node, we can't insert a load of the value before
1053     // the use.  Instead insert the load in the predecessor block
1054     // corresponding to the incoming value.
1055     //
1056     // Note that if there are multiple edges from a basic block to this
1057     // PHI node that we cannot have multiple loads.  The problem is that
1058     // the resulting PHI node will have multiple values (from each load)
1059     // coming in from the same block, which is illegal SSA form.
1060     // For this reason, we keep track of and reuse loads we insert.
1061     BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1062     if (auto *CatchRet =
1063             dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1064       // Putting a load above a catchret and use on the phi would still leave
1065       // a cross-funclet def/use.  We need to split the edge, change the
1066       // catchret to target the new block, and put the load there.
1067       BasicBlock *PHIBlock = UsingInst->getParent();
1068       BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1069       // SplitEdge gives us:
1070       //   IncomingBlock:
1071       //     ...
1072       //     br label %NewBlock
1073       //   NewBlock:
1074       //     catchret label %PHIBlock
1075       // But we need:
1076       //   IncomingBlock:
1077       //     ...
1078       //     catchret label %NewBlock
1079       //   NewBlock:
1080       //     br label %PHIBlock
1081       // So move the terminators to each others' blocks and swap their
1082       // successors.
1083       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1084       Goto->removeFromParent();
1085       CatchRet->removeFromParent();
1086       IncomingBlock->getInstList().push_back(CatchRet);
1087       NewBlock->getInstList().push_back(Goto);
1088       Goto->setSuccessor(0, PHIBlock);
1089       CatchRet->setSuccessor(NewBlock);
1090       // Update the color mapping for the newly split edge.
1091       ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1092       BlockColors[NewBlock] = ColorsForPHIBlock;
1093       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1094         FuncletBlocks[FuncletPad].push_back(NewBlock);
1095       // Treat the new block as incoming for load insertion.
1096       IncomingBlock = NewBlock;
1097     }
1098     Value *&Load = Loads[IncomingBlock];
1099     // Insert the load into the predecessor block
1100     if (!Load)
1101       Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1102                           /*Volatile=*/false, IncomingBlock->getTerminator());
1103
1104     U.set(Load);
1105   } else {
1106     // Reload right before the old use.
1107     auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1108                               /*Volatile=*/false, UsingInst);
1109     U.set(Load);
1110   }
1111 }
1112
1113 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1114                                       MCSymbol *InvokeBegin,
1115                                       MCSymbol *InvokeEnd) {
1116   assert(InvokeStateMap.count(II) &&
1117          "should get invoke with precomputed state");
1118   LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);
1119 }
1120
1121 WinEHFuncInfo::WinEHFuncInfo() {}