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/Analysis/CFG.h"
  21 #include "llvm/Analysis/LibCallSemantics.h"
  22 #include "llvm/CodeGen/WinEHFuncInfo.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  27 #include "llvm/Transforms/Utils/Cloning.h"
  28 #include "llvm/Transforms/Utils/Local.h"
  29 #include "llvm/Transforms/Utils/SSAUpdater.h"
  30
  31 using namespace llvm;
  32
  33 #define DEBUG_TYPE "winehprepare"
  34
  35 static cl::opt<bool> DisableDemotion(
  36     "disable-demotion", cl::Hidden,
  37     cl::desc(
  38         "Clone multicolor basic blocks but do not demote cross funclet values"),
  39     cl::init(false));
  40
  41 static cl::opt<bool> DisableCleanups(
  42     "disable-cleanups", cl::Hidden,
  43     cl::desc("Do not remove implausible terminators or other similar cleanups"),
  44     cl::init(false));
  45
  46 namespace {
  47
  48 class WinEHPrepare : public FunctionPass {
  49 public:
  50   static char ID; // Pass identification, replacement for typeid.
  51   WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
  52
  53   bool runOnFunction(Function &Fn) override;
  54
  55   bool doFinalization(Module &M) override;
  56
  57   void getAnalysisUsage(AnalysisUsage &AU) const override;
  58
  59   const char *getPassName() const override {
  60     return "Windows exception handling preparation";
  61   }
  62
  63 private:
  64   void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
  65   void
  66   insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
  67                  SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
  68   AllocaInst *insertPHILoads(PHINode *PN, Function &F);
  69   void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
  70                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
  71   void demoteNonlocalUses(Value *V, std::set<BasicBlock *> &ColorsForBB,
  72                           Function &F);
  73   bool prepareExplicitEH(Function &F,
  74                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
  75   void replaceTerminatePadWithCleanup(Function &F);
  76   void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
  77   void demotePHIsOnFunclets(Function &F);
  78   void demoteUsesBetweenFunclets(Function &F);
  79   void demoteArgumentUses(Function &F);
  80   void cloneCommonBlocks(Function &F,
  81                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
  82   void removeImplausibleTerminators(Function &F);
  83   void cleanupPreparedFunclets(Function &F);
  84   void verifyPreparedFunclets(Function &F);
  85
  86   // All fields are reset by runOnFunction.
  87   EHPersonality Personality = EHPersonality::Unknown;
  88
  89   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
  90   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
  91   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
  92 };
  93
  94 } // end anonymous namespace
  95
  96 char WinEHPrepare::ID = 0;
  97 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
  98                    false, false)
  99
 100 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
 101   return new WinEHPrepare(TM);
 102 }
 103
 104 static void findFuncletEntryPoints(Function &Fn,
 105                                    SmallVectorImpl<BasicBlock *> &EntryBlocks) {
 106   EntryBlocks.push_back(&Fn.getEntryBlock());
 107   for (BasicBlock &BB : Fn) {
 108     Instruction *First = BB.getFirstNonPHI();
 109     if (!First->isEHPad())
 110       continue;
 111     assert(!isa<LandingPadInst>(First) &&
 112            "landingpad cannot be used with funclet EH personality");
 113     // Find EH pad blocks that represent funclet start points.
 114     if (!isa<CatchEndPadInst>(First) && !isa<CleanupEndPadInst>(First))
 115       EntryBlocks.push_back(&BB);
 116   }
 117 }
 118
 119 bool WinEHPrepare::runOnFunction(Function &Fn) {
 120   if (!Fn.hasPersonalityFn())
 121     return false;
 122
 123   // Classify the personality to see what kind of preparation we need.
 124   Personality = classifyEHPersonality(Fn.getPersonalityFn());
 125
 126   // Do nothing if this is not a funclet-based personality.
 127   if (!isFuncletEHPersonality(Personality))
 128     return false;
 129
 130   // Remove unreachable blocks.  It is not valuable to assign them a color and
 131   // their existence can trick us into thinking values are alive when they are
 132   // not.
 133   removeUnreachableBlocks(Fn);
 134
 135   SmallVector<BasicBlock *, 4> EntryBlocks;
 136   findFuncletEntryPoints(Fn, EntryBlocks);
 137   return prepareExplicitEH(Fn, EntryBlocks);
 138 }
 139
 140 bool WinEHPrepare::doFinalization(Module &M) { return false; }
 141
 142 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
 143
 144 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
 145                              const BasicBlock *BB) {
 146   CxxUnwindMapEntry UME;
 147   UME.ToState = ToState;
 148   UME.Cleanup = BB;
 149   FuncInfo.CxxUnwindMap.push_back(UME);
 150   return FuncInfo.getLastStateNumber();
 151 }
 152
 153 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
 154                                 int TryHigh, int CatchHigh,
 155                                 ArrayRef<const CatchPadInst *> Handlers) {
 156   WinEHTryBlockMapEntry TBME;
 157   TBME.TryLow = TryLow;
 158   TBME.TryHigh = TryHigh;
 159   TBME.CatchHigh = CatchHigh;
 160   assert(TBME.TryLow <= TBME.TryHigh);
 161   for (const CatchPadInst *CPI : Handlers) {
 162     WinEHHandlerType HT;
 163     Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
 164     if (TypeInfo->isNullValue())
 165       HT.TypeDescriptor = nullptr;
 166     else
 167       HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
 168     HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
 169     HT.Handler = CPI->getParent();
 170     if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
 171       HT.CatchObj.Alloca = nullptr;
 172     else
 173       HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
 174     TBME.HandlerArray.push_back(HT);
 175   }
 176   FuncInfo.TryBlockMap.push_back(TBME);
 177 }
 178
 179 static const CatchPadInst *getSingleCatchPadPredecessor(const BasicBlock *BB) {
 180   for (const BasicBlock *PredBlock : predecessors(BB))
 181     if (auto *CPI = dyn_cast<CatchPadInst>(PredBlock->getFirstNonPHI()))
 182       return CPI;
 183   return nullptr;
 184 }
 185
 186 /// Find all the catchpads that feed directly into the catchendpad. Frontends
 187 /// using this personality should ensure that each catchendpad and catchpad has
 188 /// one or zero catchpad predecessors.
 189 ///
 190 /// The following C++ generates the IR after it:
 191 ///   try {
 192 ///   } catch (A) {
 193 ///   } catch (B) {
 194 ///   }
 195 ///
 196 /// IR:
 197 ///   %catchpad.A
 198 ///     catchpad [i8* A typeinfo]
 199 ///         to label %catch.A unwind label %catchpad.B
 200 ///   %catchpad.B
 201 ///     catchpad [i8* B typeinfo]
 202 ///         to label %catch.B unwind label %endcatches
 203 ///   %endcatches
 204 ///     catchendblock unwind to caller
 205 static void
 206 findCatchPadsForCatchEndPad(const BasicBlock *CatchEndBB,
 207                             SmallVectorImpl<const CatchPadInst *> &Handlers) {
 208   const CatchPadInst *CPI = getSingleCatchPadPredecessor(CatchEndBB);
 209   while (CPI) {
 210     Handlers.push_back(CPI);
 211     CPI = getSingleCatchPadPredecessor(CPI->getParent());
 212   }
 213   // We've pushed these back into reverse source order.  Reverse them to get
 214   // the list back into source order.
 215   std::reverse(Handlers.begin(), Handlers.end());
 216 }
 217
 218 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
 219 // to. If the unwind edge came from an invoke, return null.
 220 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB) {
 221   const TerminatorInst *TI = BB->getTerminator();
 222   if (isa<InvokeInst>(TI))
 223     return nullptr;
 224   if (TI->isEHPad())
 225     return BB;
 226   return cast<CleanupReturnInst>(TI)->getCleanupPad()->getParent();
 227 }
 228
 229 static void calculateExplicitCXXStateNumbers(WinEHFuncInfo &FuncInfo,
 230                                              const BasicBlock &BB,
 231                                              int ParentState) {
 232   assert(BB.isEHPad());
 233   const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 234   // All catchpad instructions will be handled when we process their
 235   // respective catchendpad instruction.
 236   if (isa<CatchPadInst>(FirstNonPHI))
 237     return;
 238
 239   if (isa<CatchEndPadInst>(FirstNonPHI)) {
 240     SmallVector<const CatchPadInst *, 2> Handlers;
 241     findCatchPadsForCatchEndPad(&BB, Handlers);
 242     const BasicBlock *FirstTryPad = Handlers.front()->getParent();
 243     int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
 244     FuncInfo.EHPadStateMap[Handlers.front()] = TryLow;
 245     for (const BasicBlock *PredBlock : predecessors(FirstTryPad))
 246       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 247         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, TryLow);
 248     int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
 249
 250     // catchpads are separate funclets in C++ EH due to the way rethrow works.
 251     // In SEH, they aren't, so no invokes will unwind to the catchendpad.
 252     FuncInfo.EHPadStateMap[FirstNonPHI] = CatchLow;
 253     int TryHigh = CatchLow - 1;
 254     for (const BasicBlock *PredBlock : predecessors(&BB))
 255       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 256         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CatchLow);
 257     int CatchHigh = FuncInfo.getLastStateNumber();
 258     addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
 259     DEBUG(dbgs() << "TryLow[" << FirstTryPad->getName() << "]: " << TryLow
 260                  << '\n');
 261     DEBUG(dbgs() << "TryHigh[" << FirstTryPad->getName() << "]: " << TryHigh
 262                  << '\n');
 263     DEBUG(dbgs() << "CatchHigh[" << FirstTryPad->getName() << "]: " << CatchHigh
 264                  << '\n');
 265   } else if (isa<CleanupPadInst>(FirstNonPHI)) {
 266     // A cleanup can have multiple exits; don't re-process after the first.
 267     if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
 268       return;
 269     int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, &BB);
 270     FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
 271     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
 272                  << BB.getName() << '\n');
 273     for (const BasicBlock *PredBlock : predecessors(&BB))
 274       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 275         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CleanupState);
 276   } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
 277     // Propagate ParentState to the cleanuppad in case it doesn't have
 278     // any cleanuprets.
 279     BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
 280     calculateExplicitCXXStateNumbers(FuncInfo, *CleanupBlock, ParentState);
 281     // Anything unwinding through CleanupEndPadInst is in ParentState.
 282     FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
 283     for (const BasicBlock *PredBlock : predecessors(&BB))
 284       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 285         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, ParentState);
 286   } else if (isa<TerminatePadInst>(FirstNonPHI)) {
 287     report_fatal_error("Not yet implemented!");
 288   } else {
 289     llvm_unreachable("unexpected EH Pad!");
 290   }
 291 }
 292
 293 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
 294                         const Function *Filter, const BasicBlock *Handler) {
 295   SEHUnwindMapEntry Entry;
 296   Entry.ToState = ParentState;
 297   Entry.IsFinally = false;
 298   Entry.Filter = Filter;
 299   Entry.Handler = Handler;
 300   FuncInfo.SEHUnwindMap.push_back(Entry);
 301   return FuncInfo.SEHUnwindMap.size() - 1;
 302 }
 303
 304 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
 305                          const BasicBlock *Handler) {
 306   SEHUnwindMapEntry Entry;
 307   Entry.ToState = ParentState;
 308   Entry.IsFinally = true;
 309   Entry.Filter = nullptr;
 310   Entry.Handler = Handler;
 311   FuncInfo.SEHUnwindMap.push_back(Entry);
 312   return FuncInfo.SEHUnwindMap.size() - 1;
 313 }
 314
 315 static void calculateExplicitSEHStateNumbers(WinEHFuncInfo &FuncInfo,
 316                                              const BasicBlock &BB,
 317                                              int ParentState) {
 318   assert(BB.isEHPad());
 319   const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 320   // All catchpad instructions will be handled when we process their
 321   // respective catchendpad instruction.
 322   if (isa<CatchPadInst>(FirstNonPHI))
 323     return;
 324
 325   if (isa<CatchEndPadInst>(FirstNonPHI)) {
 326     // Extract the filter function and the __except basic block and create a
 327     // state for them.
 328     SmallVector<const CatchPadInst *, 1> Handlers;
 329     findCatchPadsForCatchEndPad(&BB, Handlers);
 330     assert(Handlers.size() == 1 &&
 331            "SEH doesn't have multiple handlers per __try");
 332     const CatchPadInst *CPI = Handlers.front();
 333     const BasicBlock *CatchPadBB = CPI->getParent();
 334     const Constant *FilterOrNull =
 335         cast<Constant>(CPI->getArgOperand(0)->stripPointerCasts());
 336     const Function *Filter = dyn_cast<Function>(FilterOrNull);
 337     assert((Filter || FilterOrNull->isNullValue()) &&
 338            "unexpected filter value");
 339     int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
 340
 341     // Everything in the __try block uses TryState as its parent state.
 342     FuncInfo.EHPadStateMap[CPI] = TryState;
 343     DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
 344                  << CatchPadBB->getName() << '\n');
 345     for (const BasicBlock *PredBlock : predecessors(CatchPadBB))
 346       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 347         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, TryState);
 348
 349     // Everything in the __except block unwinds to ParentState, just like code
 350     // outside the __try.
 351     FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
 352     DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
 353                  << BB.getName() << '\n');
 354     for (const BasicBlock *PredBlock : predecessors(&BB))
 355       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 356         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
 357   } else if (isa<CleanupPadInst>(FirstNonPHI)) {
 358     // A cleanup can have multiple exits; don't re-process after the first.
 359     if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
 360       return;
 361     int CleanupState = addSEHFinally(FuncInfo, ParentState, &BB);
 362     FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
 363     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
 364                  << BB.getName() << '\n');
 365     for (const BasicBlock *PredBlock : predecessors(&BB))
 366       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 367         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, CleanupState);
 368   } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
 369     // Propagate ParentState to the cleanuppad in case it doesn't have
 370     // any cleanuprets.
 371     BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
 372     calculateExplicitSEHStateNumbers(FuncInfo, *CleanupBlock, ParentState);
 373     // Anything unwinding through CleanupEndPadInst is in ParentState.
 374     FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
 375     DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
 376                  << BB.getName() << '\n');
 377     for (const BasicBlock *PredBlock : predecessors(&BB))
 378       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
 379         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
 380   } else if (isa<TerminatePadInst>(FirstNonPHI)) {
 381     report_fatal_error("Not yet implemented!");
 382   } else {
 383     llvm_unreachable("unexpected EH Pad!");
 384   }
 385 }
 386
 387 /// Check if the EH Pad unwinds to caller.  Cleanups are a little bit of a
 388 /// special case because we have to look at the cleanupret instruction that uses
 389 /// the cleanuppad.
 390 static bool doesEHPadUnwindToCaller(const Instruction *EHPad) {
 391   auto *CPI = dyn_cast<CleanupPadInst>(EHPad);
 392   if (!CPI)
 393     return EHPad->mayThrow();
 394
 395   // This cleanup does not return or unwind, so we say it unwinds to caller.
 396   if (CPI->use_empty())
 397     return true;
 398
 399   const Instruction *User = CPI->user_back();
 400   if (auto *CRI = dyn_cast<CleanupReturnInst>(User))
 401     return CRI->unwindsToCaller();
 402   return cast<CleanupEndPadInst>(User)->unwindsToCaller();
 403 }
 404
 405 void llvm::calculateSEHStateNumbers(const Function *Fn,
 406                                     WinEHFuncInfo &FuncInfo) {
 407   // Don't compute state numbers twice.
 408   if (!FuncInfo.SEHUnwindMap.empty())
 409     return;
 410
 411   for (const BasicBlock &BB : *Fn) {
 412     if (!BB.isEHPad() || !doesEHPadUnwindToCaller(BB.getFirstNonPHI()))
 413       continue;
 414     calculateExplicitSEHStateNumbers(FuncInfo, BB, -1);
 415   }
 416 }
 417
 418 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
 419                                          WinEHFuncInfo &FuncInfo) {
 420   // Return if it's already been done.
 421   if (!FuncInfo.EHPadStateMap.empty())
 422     return;
 423
 424   for (const BasicBlock &BB : *Fn) {
 425     if (!BB.isEHPad())
 426       continue;
 427     if (BB.isLandingPad())
 428       report_fatal_error("MSVC C++ EH cannot use landingpads");
 429     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 430     if (!doesEHPadUnwindToCaller(FirstNonPHI))
 431       continue;
 432     calculateExplicitCXXStateNumbers(FuncInfo, BB, -1);
 433   }
 434 }
 435
 436 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
 437                            ClrHandlerType HandlerType, uint32_t TypeToken,
 438                            const BasicBlock *Handler) {
 439   ClrEHUnwindMapEntry Entry;
 440   Entry.Parent = ParentState;
 441   Entry.Handler = Handler;
 442   Entry.HandlerType = HandlerType;
 443   Entry.TypeToken = TypeToken;
 444   FuncInfo.ClrEHUnwindMap.push_back(Entry);
 445   return FuncInfo.ClrEHUnwindMap.size() - 1;
 446 }
 447
 448 void llvm::calculateClrEHStateNumbers(const Function *Fn,
 449                                       WinEHFuncInfo &FuncInfo) {
 450   // Return if it's already been done.
 451   if (!FuncInfo.EHPadStateMap.empty())
 452     return;
 453
 454   SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
 455
 456   // Each pad needs to be able to refer to its parent, so scan the function
 457   // looking for top-level handlers and seed the worklist with them.
 458   for (const BasicBlock &BB : *Fn) {
 459     if (!BB.isEHPad())
 460       continue;
 461     if (BB.isLandingPad())
 462       report_fatal_error("CoreCLR EH cannot use landingpads");
 463     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 464     if (!doesEHPadUnwindToCaller(FirstNonPHI))
 465       continue;
 466     // queue this with sentinel parent state -1 to mean unwind to caller.
 467     Worklist.emplace_back(FirstNonPHI, -1);
 468   }
 469
 470   while (!Worklist.empty()) {
 471     const Instruction *Pad;
 472     int ParentState;
 473     std::tie(Pad, ParentState) = Worklist.pop_back_val();
 474
 475     int PredState;
 476     if (const CleanupEndPadInst *EndPad = dyn_cast<CleanupEndPadInst>(Pad)) {
 477       FuncInfo.EHPadStateMap[EndPad] = ParentState;
 478       // Queue the cleanuppad, in case it doesn't have a cleanupret.
 479       Worklist.emplace_back(EndPad->getCleanupPad(), ParentState);
 480       // Preds of the endpad should get the parent state.
 481       PredState = ParentState;
 482     } else if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
 483       // A cleanup can have multiple exits; don't re-process after the first.
 484       if (FuncInfo.EHPadStateMap.count(Pad))
 485         continue;
 486       // CoreCLR personality uses arity to distinguish faults from finallies.
 487       const BasicBlock *PadBlock = Cleanup->getParent();
 488       ClrHandlerType HandlerType =
 489           (Cleanup->getNumOperands() ? ClrHandlerType::Fault
 490                                      : ClrHandlerType::Finally);
 491       int NewState =
 492           addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
 493       FuncInfo.EHPadStateMap[Cleanup] = NewState;
 494       // Propagate the new state to all preds of the cleanup
 495       PredState = NewState;
 496     } else if (const CatchEndPadInst *EndPad = dyn_cast<CatchEndPadInst>(Pad)) {
 497       FuncInfo.EHPadStateMap[EndPad] = ParentState;
 498       // Preds of the endpad should get the parent state.
 499       PredState = ParentState;
 500     } else if (const CatchPadInst *Catch = dyn_cast<CatchPadInst>(Pad)) {
 501       const BasicBlock *PadBlock = Catch->getParent();
 502       uint32_t TypeToken = static_cast<uint32_t>(
 503           cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
 504       int NewState = addClrEHHandler(FuncInfo, ParentState,
 505                                      ClrHandlerType::Catch, TypeToken, PadBlock);
 506       FuncInfo.EHPadStateMap[Catch] = NewState;
 507       // Preds of the catch get its state
 508       PredState = NewState;
 509     } else {
 510       llvm_unreachable("Unexpected EH pad");
 511     }
 512
 513     // Queue all predecessors with the given state
 514     for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
 515       if ((Pred = getEHPadFromPredecessor(Pred)))
 516         Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
 517     }
 518   }
 519 }
 520
 521 void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) {
 522   if (Personality != EHPersonality::MSVC_CXX)
 523     return;
 524   for (BasicBlock &BB : F) {
 525     Instruction *First = BB.getFirstNonPHI();
 526     auto *TPI = dyn_cast<TerminatePadInst>(First);
 527     if (!TPI)
 528       continue;
 529
 530     if (TPI->getNumArgOperands() != 1)
 531       report_fatal_error(
 532           "Expected a unary terminatepad for MSVC C++ personalities!");
 533
 534     auto *TerminateFn = dyn_cast<Function>(TPI->getArgOperand(0));
 535     if (!TerminateFn)
 536       report_fatal_error("Function operand expected in terminatepad for MSVC "
 537                          "C++ personalities!");
 538
 539     // Insert the cleanuppad instruction.
 540     auto *CPI = CleanupPadInst::Create(
 541         BB.getContext(), {}, Twine("terminatepad.for.", BB.getName()), &BB);
 542
 543     // Insert the call to the terminate instruction.
 544     auto *CallTerminate = CallInst::Create(TerminateFn, {}, &BB);
 545     CallTerminate->setDoesNotThrow();
 546     CallTerminate->setDoesNotReturn();
 547     CallTerminate->setCallingConv(TerminateFn->getCallingConv());
 548
 549     // Insert a new terminator for the cleanuppad using the same successor as
 550     // the terminatepad.
 551     CleanupReturnInst::Create(CPI, TPI->getUnwindDest(), &BB);
 552
 553     // Let's remove the terminatepad now that we've inserted the new
 554     // instructions.
 555     TPI->eraseFromParent();
 556   }
 557 }
 558
 559 static void
 560 colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks,
 561               std::map<BasicBlock *, std::set<BasicBlock *>> &BlockColors,
 562               std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
 563               std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletChildren) {
 564   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
 565   BasicBlock *EntryBlock = &F.getEntryBlock();
 566
 567   // Build up the color map, which maps each block to its set of 'colors'.
 568   // For any block B, the "colors" of B are the set of funclets F (possibly
 569   // including a root "funclet" representing the main function), such that
 570   // F will need to directly contain B or a copy of B (where the term "directly
 571   // contain" is used to distinguish from being "transitively contained" in
 572   // a nested funclet).
 573   // Use a CFG walk driven by a worklist of (block, color) pairs.  The "color"
 574   // sets attached during this processing to a block which is the entry of some
 575   // funclet F is actually the set of F's parents -- i.e. the union of colors
 576   // of all predecessors of F's entry.  For all other blocks, the color sets
 577   // are as defined above.  A post-pass fixes up the block color map to reflect
 578   // the same sense of "color" for funclet entries as for other blocks.
 579
 580   Worklist.push_back({EntryBlock, EntryBlock});
 581
 582   while (!Worklist.empty()) {
 583     BasicBlock *Visiting;
 584     BasicBlock *Color;
 585     std::tie(Visiting, Color) = Worklist.pop_back_val();
 586     Instruction *VisitingHead = Visiting->getFirstNonPHI();
 587     if (VisitingHead->isEHPad() && !isa<CatchEndPadInst>(VisitingHead) &&
 588         !isa<CleanupEndPadInst>(VisitingHead)) {
 589       // Mark this as a funclet head as a member of itself.
 590       FuncletBlocks[Visiting].insert(Visiting);
 591       // Queue exits (i.e. successors of rets/endpads) with the parent color.
 592       // Skip any exits that are catchendpads, since the parent color must then
 593       // represent one of the catches chained to that catchendpad, but the
 594       // catchendpad should get the color of the common parent of all its
 595       // chained catches (i.e. the grandparent color of the current pad).
 596       // We don't need to worry abou catchendpads going unvisited, since the
 597       // catches chained to them must have unwind edges to them by which we will
 598       // visit them.
 599       for (User *U : VisitingHead->users()) {
 600         if (auto *Exit = dyn_cast<TerminatorInst>(U)) {
 601           for (BasicBlock *Succ : successors(Exit->getParent()))
 602             if (!isa<CatchEndPadInst>(*Succ->getFirstNonPHI()))
 603               if (BlockColors[Succ].insert(Color).second)
 604                 Worklist.push_back({Succ, Color});
 605         }
 606       }
 607       // Handle CatchPad specially since its successors need different colors.
 608       if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(VisitingHead)) {
 609         // Visit the normal successor with the color of the new EH pad, and
 610         // visit the unwind successor with the color of the parent.
 611         BasicBlock *NormalSucc = CatchPad->getNormalDest();
 612         if (BlockColors[NormalSucc].insert(Visiting).second) {
 613           Worklist.push_back({NormalSucc, Visiting});
 614         }
 615         BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
 616         if (BlockColors[UnwindSucc].insert(Color).second) {
 617           Worklist.push_back({UnwindSucc, Color});
 618         }
 619         continue;
 620       }
 621       // Switch color to the current node, except for terminate pads which
 622       // have no bodies and only unwind successors and so need their successors
 623       // visited with the color of the parent.
 624       if (!isa<TerminatePadInst>(VisitingHead))
 625         Color = Visiting;
 626     } else {
 627       // Note that this is a member of the given color.
 628       FuncletBlocks[Color].insert(Visiting);
 629     }
 630
 631     TerminatorInst *Terminator = Visiting->getTerminator();
 632     if (isa<CleanupReturnInst>(Terminator) ||
 633         isa<CatchReturnInst>(Terminator) ||
 634         isa<CleanupEndPadInst>(Terminator)) {
 635       // These blocks' successors have already been queued with the parent
 636       // color.
 637       continue;
 638     }
 639     for (BasicBlock *Succ : successors(Visiting)) {
 640       if (isa<CatchEndPadInst>(Succ->getFirstNonPHI())) {
 641         // The catchendpad needs to be visited with the parent's color, not
 642         // the current color.  This will happen in the code above that visits
 643         // any catchpad unwind successor with the parent color, so we can
 644         // safely skip this successor here.
 645         continue;
 646       }
 647       if (BlockColors[Succ].insert(Color).second) {
 648         Worklist.push_back({Succ, Color});
 649       }
 650     }
 651   }
 652
 653   // The processing above actually accumulated the parent set for this
 654   // funclet into the color set for its entry; use the parent set to
 655   // populate the children map, and reset the color set to include just
 656   // the funclet itself (no instruction can target a funclet entry except on
 657   // that transitions to the child funclet).
 658   for (BasicBlock *FuncletEntry : EntryBlocks) {
 659     std::set<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
 660     for (BasicBlock *Parent : ColorMapItem)
 661       FuncletChildren[Parent].insert(FuncletEntry);
 662     ColorMapItem.clear();
 663     ColorMapItem.insert(FuncletEntry);
 664   }
 665 }
 666
 667 void WinEHPrepare::colorFunclets(Function &F,
 668                                  SmallVectorImpl<BasicBlock *> &EntryBlocks) {
 669   ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks, FuncletChildren);
 670 }
 671
 672 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
 673                                                WinEHFuncInfo &FuncInfo) {
 674   SmallVector<BasicBlock *, 4> EntryBlocks;
 675   // colorFunclets needs the set of EntryBlocks, get them using
 676   // findFuncletEntryPoints.
 677   findFuncletEntryPoints(const_cast<Function &>(*Fn), EntryBlocks);
 678
 679   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
 680   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
 681   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
 682   // Figure out which basic blocks belong to which funclets.
 683   colorFunclets(const_cast<Function &>(*Fn), EntryBlocks, BlockColors,
 684                 FuncletBlocks, FuncletChildren);
 685
 686   // We need to find the catchret successors.  To do this, we must first find
 687   // all the catchpad funclets.
 688   for (auto &Funclet : FuncletBlocks) {
 689     // Figure out what kind of funclet we are looking at; We only care about
 690     // catchpads.
 691     BasicBlock *FuncletPadBB = Funclet.first;
 692     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
 693     auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
 694     if (!CatchPad)
 695       continue;
 696
 697     // The users of a catchpad are always catchrets.
 698     for (User *Exit : CatchPad->users()) {
 699       auto *CatchReturn = dyn_cast<CatchReturnInst>(Exit);
 700       if (!CatchReturn)
 701         continue;
 702       BasicBlock *CatchRetSuccessor = CatchReturn->getSuccessor();
 703       std::set<BasicBlock *> &SuccessorColors = BlockColors[CatchRetSuccessor];
 704       assert(SuccessorColors.size() == 1 && "Expected BB to be monochrome!");
 705       BasicBlock *Color = *SuccessorColors.begin();
 706       // Record the catchret successor's funclet membership.
 707       FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color;
 708     }
 709   }
 710 }
 711
 712 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
 713   // Strip PHI nodes off of EH pads.
 714   SmallVector<PHINode *, 16> PHINodes;
 715   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 716     BasicBlock *BB = &*FI++;
 717     if (!BB->isEHPad())
 718       continue;
 719     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
 720       Instruction *I = &*BI++;
 721       auto *PN = dyn_cast<PHINode>(I);
 722       // Stop at the first non-PHI.
 723       if (!PN)
 724         break;
 725
 726       AllocaInst *SpillSlot = insertPHILoads(PN, F);
 727       if (SpillSlot)
 728         insertPHIStores(PN, SpillSlot);
 729
 730       PHINodes.push_back(PN);
 731     }
 732   }
 733
 734   for (auto *PN : PHINodes) {
 735     // There may be lingering uses on other EH PHIs being removed
 736     PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 737     PN->eraseFromParent();
 738   }
 739 }
 740
 741 void WinEHPrepare::demoteUsesBetweenFunclets(Function &F) {
 742   // Turn all inter-funclet uses of a Value into loads and stores.
 743   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 744     BasicBlock *BB = &*FI++;
 745     std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
 746     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
 747       Instruction *I = &*BI++;
 748       // Funclets are permitted to use static allocas.
 749       if (auto *AI = dyn_cast<AllocaInst>(I))
 750         if (AI->isStaticAlloca())
 751           continue;
 752
 753       demoteNonlocalUses(I, ColorsForBB, F);
 754     }
 755   }
 756 }
 757
 758 void WinEHPrepare::demoteArgumentUses(Function &F) {
 759   // Also demote function parameters used in funclets.
 760   std::set<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
 761   for (Argument &Arg : F.args())
 762     demoteNonlocalUses(&Arg, ColorsForEntry, F);
 763 }
 764
 765 void WinEHPrepare::cloneCommonBlocks(
 766     Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
 767   // We need to clone all blocks which belong to multiple funclets.  Values are
 768   // remapped throughout the funclet to propogate both the new instructions
 769   // *and* the new basic blocks themselves.
 770   for (BasicBlock *FuncletPadBB : EntryBlocks) {
 771     std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
 772
 773     std::map<BasicBlock *, BasicBlock *> Orig2Clone;
 774     ValueToValueMapTy VMap;
 775     for (BasicBlock *BB : BlocksInFunclet) {
 776       std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
 777       // We don't need to do anything if the block is monochromatic.
 778       size_t NumColorsForBB = ColorsForBB.size();
 779       if (NumColorsForBB == 1)
 780         continue;
 781
 782       // Create a new basic block and copy instructions into it!
 783       BasicBlock *CBB =
 784           CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
 785       // Insert the clone immediately after the original to ensure determinism
 786       // and to keep the same relative ordering of any funclet's blocks.
 787       CBB->insertInto(&F, BB->getNextNode());
 788
 789       // Add basic block mapping.
 790       VMap[BB] = CBB;
 791
 792       // Record delta operations that we need to perform to our color mappings.
 793       Orig2Clone[BB] = CBB;
 794     }
 795
 796     // If nothing was cloned, we're done cloning in this funclet.
 797     if (Orig2Clone.empty())
 798       continue;
 799
 800     // Update our color mappings to reflect that one block has lost a color and
 801     // another has gained a color.
 802     for (auto &BBMapping : Orig2Clone) {
 803       BasicBlock *OldBlock = BBMapping.first;
 804       BasicBlock *NewBlock = BBMapping.second;
 805
 806       BlocksInFunclet.insert(NewBlock);
 807       BlockColors[NewBlock].insert(FuncletPadBB);
 808
 809       BlocksInFunclet.erase(OldBlock);
 810       BlockColors[OldBlock].erase(FuncletPadBB);
 811     }
 812
 813     // Loop over all of the instructions in this funclet, fixing up operand
 814     // references as we go.  This uses VMap to do all the hard work.
 815     for (BasicBlock *BB : BlocksInFunclet)
 816       // Loop over all instructions, fixing each one as we find it...
 817       for (Instruction &I : *BB)
 818         RemapInstruction(&I, VMap,
 819                          RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
 820
 821     // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
 822     // the PHI nodes for NewBB now.
 823     for (auto &BBMapping : Orig2Clone) {
 824       BasicBlock *OldBlock = BBMapping.first;
 825       BasicBlock *NewBlock = BBMapping.second;
 826       for (BasicBlock *SuccBB : successors(NewBlock)) {
 827         for (Instruction &SuccI : *SuccBB) {
 828           auto *SuccPN = dyn_cast<PHINode>(&SuccI);
 829           if (!SuccPN)
 830             break;
 831
 832           // Ok, we have a PHI node.  Figure out what the incoming value was for
 833           // the OldBlock.
 834           int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
 835           if (OldBlockIdx == -1)
 836             break;
 837           Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
 838
 839           // Remap the value if necessary.
 840           if (auto *Inst = dyn_cast<Instruction>(IV)) {
 841             ValueToValueMapTy::iterator I = VMap.find(Inst);
 842             if (I != VMap.end())
 843               IV = I->second;
 844           }
 845
 846           SuccPN->addIncoming(IV, NewBlock);
 847         }
 848       }
 849     }
 850
 851     for (ValueToValueMapTy::value_type VT : VMap) {
 852       // If there were values defined in BB that are used outside the funclet,
 853       // then we now have to update all uses of the value to use either the
 854       // original value, the cloned value, or some PHI derived value.  This can
 855       // require arbitrary PHI insertion, of which we are prepared to do, clean
 856       // these up now.
 857       SmallVector<Use *, 16> UsesToRename;
 858
 859       auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
 860       if (!OldI)
 861         continue;
 862       auto *NewI = cast<Instruction>(VT.second);
 863       // Scan all uses of this instruction to see if it is used outside of its
 864       // funclet, and if so, record them in UsesToRename.
 865       for (Use &U : OldI->uses()) {
 866         Instruction *UserI = cast<Instruction>(U.getUser());
 867         BasicBlock *UserBB = UserI->getParent();
 868         std::set<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB];
 869         assert(!ColorsForUserBB.empty());
 870         if (ColorsForUserBB.size() > 1 ||
 871             *ColorsForUserBB.begin() != FuncletPadBB)
 872           UsesToRename.push_back(&U);
 873       }
 874
 875       // If there are no uses outside the block, we're done with this
 876       // instruction.
 877       if (UsesToRename.empty())
 878         continue;
 879
 880       // We found a use of OldI outside of the funclet.  Rename all uses of OldI
 881       // that are outside its funclet to be uses of the appropriate PHI node
 882       // etc.
 883       SSAUpdater SSAUpdate;
 884       SSAUpdate.Initialize(OldI->getType(), OldI->getName());
 885       SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
 886       SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
 887
 888       while (!UsesToRename.empty())
 889         SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
 890     }
 891   }
 892 }
 893
 894 void WinEHPrepare::removeImplausibleTerminators(Function &F) {
 895   // Remove implausible terminators and replace them with UnreachableInst.
 896   for (auto &Funclet : FuncletBlocks) {
 897     BasicBlock *FuncletPadBB = Funclet.first;
 898     std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
 899     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
 900     auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
 901     auto *CleanupPad = dyn_cast<CleanupPadInst>(FirstNonPHI);
 902
 903     for (BasicBlock *BB : BlocksInFunclet) {
 904       TerminatorInst *TI = BB->getTerminator();
 905       // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
 906       bool IsUnreachableRet = isa<ReturnInst>(TI) && (CatchPad || CleanupPad);
 907       // The token consumed by a CatchReturnInst must match the funclet token.
 908       bool IsUnreachableCatchret = false;
 909       if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
 910         IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
 911       // The token consumed by a CleanupReturnInst must match the funclet token.
 912       bool IsUnreachableCleanupret = false;
 913       if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
 914         IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
 915       // The token consumed by a CleanupEndPadInst must match the funclet token.
 916       bool IsUnreachableCleanupendpad = false;
 917       if (auto *CEPI = dyn_cast<CleanupEndPadInst>(TI))
 918         IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad;
 919       if (IsUnreachableRet || IsUnreachableCatchret ||
 920           IsUnreachableCleanupret || IsUnreachableCleanupendpad) {
 921         // Loop through all of our successors and make sure they know that one
 922         // of their predecessors is going away.
 923         for (BasicBlock *SuccBB : TI->successors())
 924           SuccBB->removePredecessor(BB);
 925
 926         if (IsUnreachableCleanupendpad) {
 927           // We can't simply replace a cleanupendpad with unreachable, because
 928           // its predecessor edges are EH edges and unreachable is not an EH
 929           // pad.  Change all predecessors to the "unwind to caller" form.
 930           for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 931                PI != PE;) {
 932             BasicBlock *Pred = *PI++;
 933             removeUnwindEdge(Pred);
 934           }
 935         }
 936
 937         new UnreachableInst(BB->getContext(), TI);
 938         TI->eraseFromParent();
 939       }
 940       // FIXME: Check for invokes/cleanuprets/cleanupendpads which unwind to
 941       // implausible catchendpads (i.e. catchendpad not in immediate parent
 942       // funclet).
 943     }
 944   }
 945 }
 946
 947 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
 948   // Clean-up some of the mess we made by removing useles PHI nodes, trivial
 949   // branches, etc.
 950   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 951     BasicBlock *BB = &*FI++;
 952     SimplifyInstructionsInBlock(BB);
 953     ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
 954     MergeBlockIntoPredecessor(BB);
 955   }
 956
 957   // We might have some unreachable blocks after cleaning up some impossible
 958   // control flow.
 959   removeUnreachableBlocks(F);
 960 }
 961
 962 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
 963   // Recolor the CFG to verify that all is well.
 964   for (BasicBlock &BB : F) {
 965     size_t NumColors = BlockColors[&BB].size();
 966     assert(NumColors == 1 && "Expected monochromatic BB!");
 967     if (NumColors == 0)
 968       report_fatal_error("Uncolored BB!");
 969     if (NumColors > 1)
 970       report_fatal_error("Multicolor BB!");
 971     if (!DisableDemotion) {
 972       bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
 973       assert(!EHPadHasPHI && "EH Pad still has a PHI!");
 974       if (EHPadHasPHI)
 975         report_fatal_error("EH Pad still has a PHI!");
 976     }
 977   }
 978 }
 979
 980 bool WinEHPrepare::prepareExplicitEH(
 981     Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
 982   replaceTerminatePadWithCleanup(F);
 983
 984   // Determine which blocks are reachable from which funclet entries.
 985   colorFunclets(F, EntryBlocks);
 986
 987   if (!DisableDemotion) {
 988     demotePHIsOnFunclets(F);
 989
 990     demoteUsesBetweenFunclets(F);
 991
 992     demoteArgumentUses(F);
 993   }
 994
 995   cloneCommonBlocks(F, EntryBlocks);
 996
 997   if (!DisableCleanups) {
 998     removeImplausibleTerminators(F);
 999
1000     cleanupPreparedFunclets(F);
1001   }
1002
1003   verifyPreparedFunclets(F);
1004
1005   BlockColors.clear();
1006   FuncletBlocks.clear();
1007   FuncletChildren.clear();
1008
1009   return true;
1010 }
1011
1012 // TODO: Share loads when one use dominates another, or when a catchpad exit
1013 // dominates uses (needs dominators).
1014 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1015   BasicBlock *PHIBlock = PN->getParent();
1016   AllocaInst *SpillSlot = nullptr;
1017
1018   if (isa<CleanupPadInst>(PHIBlock->getFirstNonPHI())) {
1019     // Insert a load in place of the PHI and replace all uses.
1020     SpillSlot = new AllocaInst(PN->getType(), nullptr,
1021                                Twine(PN->getName(), ".wineh.spillslot"),
1022                                &F.getEntryBlock().front());
1023     Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
1024                             &*PHIBlock->getFirstInsertionPt());
1025     PN->replaceAllUsesWith(V);
1026     return SpillSlot;
1027   }
1028
1029   DenseMap<BasicBlock *, Value *> Loads;
1030   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1031        UI != UE;) {
1032     Use &U = *UI++;
1033     auto *UsingInst = cast<Instruction>(U.getUser());
1034     BasicBlock *UsingBB = UsingInst->getParent();
1035     if (UsingBB->isEHPad()) {
1036       // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
1037       // stores for it separately.
1038       assert(isa<PHINode>(UsingInst));
1039       continue;
1040     }
1041     replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1042   }
1043   return SpillSlot;
1044 }
1045
1046 // TODO: improve store placement.  Inserting at def is probably good, but need
1047 // to be careful not to introduce interfering stores (needs liveness analysis).
1048 // TODO: identify related phi nodes that can share spill slots, and share them
1049 // (also needs liveness).
1050 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1051                                    AllocaInst *SpillSlot) {
1052   // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1053   // stored to the spill slot by the end of the given Block.
1054   SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1055
1056   Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1057
1058   while (!Worklist.empty()) {
1059     BasicBlock *EHBlock;
1060     Value *InVal;
1061     std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1062
1063     PHINode *PN = dyn_cast<PHINode>(InVal);
1064     if (PN && PN->getParent() == EHBlock) {
1065       // The value is defined by another PHI we need to remove, with no room to
1066       // insert a store after the PHI, so each predecessor needs to store its
1067       // incoming value.
1068       for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1069         Value *PredVal = PN->getIncomingValue(i);
1070
1071         // Undef can safely be skipped.
1072         if (isa<UndefValue>(PredVal))
1073           continue;
1074
1075         insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1076       }
1077     } else {
1078       // We need to store InVal, which dominates EHBlock, but can't put a store
1079       // in EHBlock, so need to put stores in each predecessor.
1080       for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1081         insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1082       }
1083     }
1084   }
1085 }
1086
1087 void WinEHPrepare::insertPHIStore(
1088     BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1089     SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1090
1091   if (PredBlock->isEHPad() &&
1092       !isa<CleanupPadInst>(PredBlock->getFirstNonPHI())) {
1093     // Pred is unsplittable, so we need to queue it on the worklist.
1094     Worklist.push_back({PredBlock, PredVal});
1095     return;
1096   }
1097
1098   // Otherwise, insert the store at the end of the basic block.
1099   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1100 }
1101
1102 // TODO: Share loads for same-funclet uses (requires dominators if funclets
1103 // aren't properly nested).
1104 void WinEHPrepare::demoteNonlocalUses(Value *V,
1105                                       std::set<BasicBlock *> &ColorsForBB,
1106                                       Function &F) {
1107   // Tokens can only be used non-locally due to control flow involving
1108   // unreachable edges.  Don't try to demote the token usage, we'll simply
1109   // delete the cloned user later.
1110   if (isa<CatchPadInst>(V) || isa<CleanupPadInst>(V))
1111     return;
1112
1113   DenseMap<BasicBlock *, Value *> Loads;
1114   AllocaInst *SpillSlot = nullptr;
1115   for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;) {
1116     Use &U = *UI++;
1117     auto *UsingInst = cast<Instruction>(U.getUser());
1118     BasicBlock *UsingBB = UsingInst->getParent();
1119
1120     // Is the Use inside a block which is colored the same as the Def?
1121     // If so, we don't need to escape the Def because we will clone
1122     // ourselves our own private copy.
1123     std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
1124     if (ColorsForUsingBB == ColorsForBB)
1125       continue;
1126
1127     replaceUseWithLoad(V, U, SpillSlot, Loads, F);
1128   }
1129   if (SpillSlot) {
1130     // Insert stores of the computed value into the stack slot.
1131     // We have to be careful if I is an invoke instruction,
1132     // because we can't insert the store AFTER the terminator instruction.
1133     BasicBlock::iterator InsertPt;
1134     if (isa<Argument>(V)) {
1135       InsertPt = F.getEntryBlock().getTerminator()->getIterator();
1136     } else if (isa<TerminatorInst>(V)) {
1137       auto *II = cast<InvokeInst>(V);
1138       // We cannot demote invoke instructions to the stack if their normal
1139       // edge is critical. Therefore, split the critical edge and create a
1140       // basic block into which the store can be inserted.
1141       if (!II->getNormalDest()->getSinglePredecessor()) {
1142         unsigned SuccNum =
1143             GetSuccessorNumber(II->getParent(), II->getNormalDest());
1144         assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
1145         BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
1146         assert(NewBlock && "Unable to split critical edge.");
1147         // Update the color mapping for the newly split edge.
1148         std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[II->getParent()];
1149         BlockColors[NewBlock] = ColorsForUsingBB;
1150         for (BasicBlock *FuncletPad : ColorsForUsingBB)
1151           FuncletBlocks[FuncletPad].insert(NewBlock);
1152       }
1153       InsertPt = II->getNormalDest()->getFirstInsertionPt();
1154     } else {
1155       InsertPt = cast<Instruction>(V)->getIterator();
1156       ++InsertPt;
1157       // Don't insert before PHI nodes or EH pad instrs.
1158       for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
1159         ;
1160     }
1161     new StoreInst(V, SpillSlot, &*InsertPt);
1162   }
1163 }
1164
1165 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1166                                       DenseMap<BasicBlock *, Value *> &Loads,
1167                                       Function &F) {
1168   // Lazilly create the spill slot.
1169   if (!SpillSlot)
1170     SpillSlot = new AllocaInst(V->getType(), nullptr,
1171                                Twine(V->getName(), ".wineh.spillslot"),
1172                                &F.getEntryBlock().front());
1173
1174   auto *UsingInst = cast<Instruction>(U.getUser());
1175   if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1176     // If this is a PHI node, we can't insert a load of the value before
1177     // the use.  Instead insert the load in the predecessor block
1178     // corresponding to the incoming value.
1179     //
1180     // Note that if there are multiple edges from a basic block to this
1181     // PHI node that we cannot have multiple loads.  The problem is that
1182     // the resulting PHI node will have multiple values (from each load)
1183     // coming in from the same block, which is illegal SSA form.
1184     // For this reason, we keep track of and reuse loads we insert.
1185     BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1186     if (auto *CatchRet =
1187             dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1188       // Putting a load above a catchret and use on the phi would still leave
1189       // a cross-funclet def/use.  We need to split the edge, change the
1190       // catchret to target the new block, and put the load there.
1191       BasicBlock *PHIBlock = UsingInst->getParent();
1192       BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1193       // SplitEdge gives us:
1194       //   IncomingBlock:
1195       //     ...
1196       //     br label %NewBlock
1197       //   NewBlock:
1198       //     catchret label %PHIBlock
1199       // But we need:
1200       //   IncomingBlock:
1201       //     ...
1202       //     catchret label %NewBlock
1203       //   NewBlock:
1204       //     br label %PHIBlock
1205       // So move the terminators to each others' blocks and swap their
1206       // successors.
1207       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1208       Goto->removeFromParent();
1209       CatchRet->removeFromParent();
1210       IncomingBlock->getInstList().push_back(CatchRet);
1211       NewBlock->getInstList().push_back(Goto);
1212       Goto->setSuccessor(0, PHIBlock);
1213       CatchRet->setSuccessor(NewBlock);
1214       // Update the color mapping for the newly split edge.
1215       std::set<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock];
1216       BlockColors[NewBlock] = ColorsForPHIBlock;
1217       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1218         FuncletBlocks[FuncletPad].insert(NewBlock);
1219       // Treat the new block as incoming for load insertion.
1220       IncomingBlock = NewBlock;
1221     }
1222     Value *&Load = Loads[IncomingBlock];
1223     // Insert the load into the predecessor block
1224     if (!Load)
1225       Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1226                           /*Volatile=*/false, IncomingBlock->getTerminator());
1227
1228     U.set(Load);
1229   } else {
1230     // Reload right before the old use.
1231     auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1232                               /*Volatile=*/false, UsingInst);
1233     U.set(Load);
1234   }
1235 }
1236
1237 void WinEHFuncInfo::addIPToStateRange(const BasicBlock *PadBB,
1238                                       MCSymbol *InvokeBegin,
1239                                       MCSymbol *InvokeEnd) {
1240   assert(PadBB->isEHPad() && EHPadStateMap.count(PadBB->getFirstNonPHI()) &&
1241          "should get EH pad BB with precomputed state");
1242   InvokeToStateMap[InvokeBegin] =
1243       std::make_pair(EHPadStateMap[PadBB->getFirstNonPHI()], InvokeEnd);
1244 }