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