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       if (auto *CPI = dyn_cast<CatchPadInst>(Color->getFirstNonPHI()))
 707         Color = CPI->getNormalDest();
 708       // Record the catchret successor's funclet membership.
 709       FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color;
 710     }
 711   }
 712 }
 713
 714 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
 715   // Strip PHI nodes off of EH pads.
 716   SmallVector<PHINode *, 16> PHINodes;
 717   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 718     BasicBlock *BB = &*FI++;
 719     if (!BB->isEHPad())
 720       continue;
 721     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
 722       Instruction *I = &*BI++;
 723       auto *PN = dyn_cast<PHINode>(I);
 724       // Stop at the first non-PHI.
 725       if (!PN)
 726         break;
 727
 728       AllocaInst *SpillSlot = insertPHILoads(PN, F);
 729       if (SpillSlot)
 730         insertPHIStores(PN, SpillSlot);
 731
 732       PHINodes.push_back(PN);
 733     }
 734   }
 735
 736   for (auto *PN : PHINodes) {
 737     // There may be lingering uses on other EH PHIs being removed
 738     PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 739     PN->eraseFromParent();
 740   }
 741 }
 742
 743 void WinEHPrepare::demoteUsesBetweenFunclets(Function &F) {
 744   // Turn all inter-funclet uses of a Value into loads and stores.
 745   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 746     BasicBlock *BB = &*FI++;
 747     std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
 748     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
 749       Instruction *I = &*BI++;
 750       // Funclets are permitted to use static allocas.
 751       if (auto *AI = dyn_cast<AllocaInst>(I))
 752         if (AI->isStaticAlloca())
 753           continue;
 754
 755       demoteNonlocalUses(I, ColorsForBB, F);
 756     }
 757   }
 758 }
 759
 760 void WinEHPrepare::demoteArgumentUses(Function &F) {
 761   // Also demote function parameters used in funclets.
 762   std::set<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
 763   for (Argument &Arg : F.args())
 764     demoteNonlocalUses(&Arg, ColorsForEntry, F);
 765 }
 766
 767 void WinEHPrepare::cloneCommonBlocks(
 768     Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
 769   // We need to clone all blocks which belong to multiple funclets.  Values are
 770   // remapped throughout the funclet to propogate both the new instructions
 771   // *and* the new basic blocks themselves.
 772   for (BasicBlock *FuncletPadBB : EntryBlocks) {
 773     std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
 774
 775     std::map<BasicBlock *, BasicBlock *> Orig2Clone;
 776     ValueToValueMapTy VMap;
 777     for (BasicBlock *BB : BlocksInFunclet) {
 778       std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
 779       // We don't need to do anything if the block is monochromatic.
 780       size_t NumColorsForBB = ColorsForBB.size();
 781       if (NumColorsForBB == 1)
 782         continue;
 783
 784       // Create a new basic block and copy instructions into it!
 785       BasicBlock *CBB =
 786           CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
 787       // Insert the clone immediately after the original to ensure determinism
 788       // and to keep the same relative ordering of any funclet's blocks.
 789       CBB->insertInto(&F, BB->getNextNode());
 790
 791       // Add basic block mapping.
 792       VMap[BB] = CBB;
 793
 794       // Record delta operations that we need to perform to our color mappings.
 795       Orig2Clone[BB] = CBB;
 796     }
 797
 798     // If nothing was cloned, we're done cloning in this funclet.
 799     if (Orig2Clone.empty())
 800       continue;
 801
 802     // Update our color mappings to reflect that one block has lost a color and
 803     // another has gained a color.
 804     for (auto &BBMapping : Orig2Clone) {
 805       BasicBlock *OldBlock = BBMapping.first;
 806       BasicBlock *NewBlock = BBMapping.second;
 807
 808       BlocksInFunclet.insert(NewBlock);
 809       BlockColors[NewBlock].insert(FuncletPadBB);
 810
 811       BlocksInFunclet.erase(OldBlock);
 812       BlockColors[OldBlock].erase(FuncletPadBB);
 813     }
 814
 815     // Loop over all of the instructions in this funclet, fixing up operand
 816     // references as we go.  This uses VMap to do all the hard work.
 817     for (BasicBlock *BB : BlocksInFunclet)
 818       // Loop over all instructions, fixing each one as we find it...
 819       for (Instruction &I : *BB)
 820         RemapInstruction(&I, VMap,
 821                          RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
 822
 823     // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
 824     // the PHI nodes for NewBB now.
 825     for (auto &BBMapping : Orig2Clone) {
 826       BasicBlock *OldBlock = BBMapping.first;
 827       BasicBlock *NewBlock = BBMapping.second;
 828       for (BasicBlock *SuccBB : successors(NewBlock)) {
 829         for (Instruction &SuccI : *SuccBB) {
 830           auto *SuccPN = dyn_cast<PHINode>(&SuccI);
 831           if (!SuccPN)
 832             break;
 833
 834           // Ok, we have a PHI node.  Figure out what the incoming value was for
 835           // the OldBlock.
 836           int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
 837           if (OldBlockIdx == -1)
 838             break;
 839           Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
 840
 841           // Remap the value if necessary.
 842           if (auto *Inst = dyn_cast<Instruction>(IV)) {
 843             ValueToValueMapTy::iterator I = VMap.find(Inst);
 844             if (I != VMap.end())
 845               IV = I->second;
 846           }
 847
 848           SuccPN->addIncoming(IV, NewBlock);
 849         }
 850       }
 851     }
 852
 853     for (ValueToValueMapTy::value_type VT : VMap) {
 854       // If there were values defined in BB that are used outside the funclet,
 855       // then we now have to update all uses of the value to use either the
 856       // original value, the cloned value, or some PHI derived value.  This can
 857       // require arbitrary PHI insertion, of which we are prepared to do, clean
 858       // these up now.
 859       SmallVector<Use *, 16> UsesToRename;
 860
 861       auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
 862       if (!OldI)
 863         continue;
 864       auto *NewI = cast<Instruction>(VT.second);
 865       // Scan all uses of this instruction to see if it is used outside of its
 866       // funclet, and if so, record them in UsesToRename.
 867       for (Use &U : OldI->uses()) {
 868         Instruction *UserI = cast<Instruction>(U.getUser());
 869         BasicBlock *UserBB = UserI->getParent();
 870         std::set<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB];
 871         assert(!ColorsForUserBB.empty());
 872         if (ColorsForUserBB.size() > 1 ||
 873             *ColorsForUserBB.begin() != FuncletPadBB)
 874           UsesToRename.push_back(&U);
 875       }
 876
 877       // If there are no uses outside the block, we're done with this
 878       // instruction.
 879       if (UsesToRename.empty())
 880         continue;
 881
 882       // We found a use of OldI outside of the funclet.  Rename all uses of OldI
 883       // that are outside its funclet to be uses of the appropriate PHI node
 884       // etc.
 885       SSAUpdater SSAUpdate;
 886       SSAUpdate.Initialize(OldI->getType(), OldI->getName());
 887       SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
 888       SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
 889
 890       while (!UsesToRename.empty())
 891         SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
 892     }
 893   }
 894 }
 895
 896 void WinEHPrepare::removeImplausibleTerminators(Function &F) {
 897   // Remove implausible terminators and replace them with UnreachableInst.
 898   for (auto &Funclet : FuncletBlocks) {
 899     BasicBlock *FuncletPadBB = Funclet.first;
 900     std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
 901     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
 902     auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
 903     auto *CleanupPad = dyn_cast<CleanupPadInst>(FirstNonPHI);
 904
 905     for (BasicBlock *BB : BlocksInFunclet) {
 906       TerminatorInst *TI = BB->getTerminator();
 907       // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
 908       bool IsUnreachableRet = isa<ReturnInst>(TI) && (CatchPad || CleanupPad);
 909       // The token consumed by a CatchReturnInst must match the funclet token.
 910       bool IsUnreachableCatchret = false;
 911       if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
 912         IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
 913       // The token consumed by a CleanupReturnInst must match the funclet token.
 914       bool IsUnreachableCleanupret = false;
 915       if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
 916         IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
 917       // The token consumed by a CleanupEndPadInst must match the funclet token.
 918       bool IsUnreachableCleanupendpad = false;
 919       if (auto *CEPI = dyn_cast<CleanupEndPadInst>(TI))
 920         IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad;
 921       if (IsUnreachableRet || IsUnreachableCatchret ||
 922           IsUnreachableCleanupret || IsUnreachableCleanupendpad) {
 923         // Loop through all of our successors and make sure they know that one
 924         // of their predecessors is going away.
 925         for (BasicBlock *SuccBB : TI->successors())
 926           SuccBB->removePredecessor(BB);
 927
 928         if (IsUnreachableCleanupendpad) {
 929           // We can't simply replace a cleanupendpad with unreachable, because
 930           // its predecessor edges are EH edges and unreachable is not an EH
 931           // pad.  Change all predecessors to the "unwind to caller" form.
 932           for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 933                PI != PE;) {
 934             BasicBlock *Pred = *PI++;
 935             removeUnwindEdge(Pred);
 936           }
 937         }
 938
 939         new UnreachableInst(BB->getContext(), TI);
 940         TI->eraseFromParent();
 941       }
 942       // FIXME: Check for invokes/cleanuprets/cleanupendpads which unwind to
 943       // implausible catchendpads (i.e. catchendpad not in immediate parent
 944       // funclet).
 945     }
 946   }
 947 }
 948
 949 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
 950   // Clean-up some of the mess we made by removing useles PHI nodes, trivial
 951   // branches, etc.
 952   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 953     BasicBlock *BB = &*FI++;
 954     SimplifyInstructionsInBlock(BB);
 955     ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
 956     MergeBlockIntoPredecessor(BB);
 957   }
 958
 959   // We might have some unreachable blocks after cleaning up some impossible
 960   // control flow.
 961   removeUnreachableBlocks(F);
 962 }
 963
 964 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
 965   // Recolor the CFG to verify that all is well.
 966   for (BasicBlock &BB : F) {
 967     size_t NumColors = BlockColors[&BB].size();
 968     assert(NumColors == 1 && "Expected monochromatic BB!");
 969     if (NumColors == 0)
 970       report_fatal_error("Uncolored BB!");
 971     if (NumColors > 1)
 972       report_fatal_error("Multicolor BB!");
 973     if (!DisableDemotion) {
 974       bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
 975       assert(!EHPadHasPHI && "EH Pad still has a PHI!");
 976       if (EHPadHasPHI)
 977         report_fatal_error("EH Pad still has a PHI!");
 978     }
 979   }
 980 }
 981
 982 bool WinEHPrepare::prepareExplicitEH(
 983     Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
 984   replaceTerminatePadWithCleanup(F);
 985
 986   // Determine which blocks are reachable from which funclet entries.
 987   colorFunclets(F, EntryBlocks);
 988
 989   if (!DisableDemotion) {
 990     demotePHIsOnFunclets(F);
 991
 992     demoteUsesBetweenFunclets(F);
 993
 994     demoteArgumentUses(F);
 995   }
 996
 997   cloneCommonBlocks(F, EntryBlocks);
 998
 999   if (!DisableCleanups) {
1000     removeImplausibleTerminators(F);
1001
1002     cleanupPreparedFunclets(F);
1003   }
1004
1005   verifyPreparedFunclets(F);
1006
1007   BlockColors.clear();
1008   FuncletBlocks.clear();
1009   FuncletChildren.clear();
1010
1011   return true;
1012 }
1013
1014 // TODO: Share loads when one use dominates another, or when a catchpad exit
1015 // dominates uses (needs dominators).
1016 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1017   BasicBlock *PHIBlock = PN->getParent();
1018   AllocaInst *SpillSlot = nullptr;
1019
1020   if (isa<CleanupPadInst>(PHIBlock->getFirstNonPHI())) {
1021     // Insert a load in place of the PHI and replace all uses.
1022     SpillSlot = new AllocaInst(PN->getType(), nullptr,
1023                                Twine(PN->getName(), ".wineh.spillslot"),
1024                                &F.getEntryBlock().front());
1025     Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
1026                             &*PHIBlock->getFirstInsertionPt());
1027     PN->replaceAllUsesWith(V);
1028     return SpillSlot;
1029   }
1030
1031   DenseMap<BasicBlock *, Value *> Loads;
1032   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1033        UI != UE;) {
1034     Use &U = *UI++;
1035     auto *UsingInst = cast<Instruction>(U.getUser());
1036     BasicBlock *UsingBB = UsingInst->getParent();
1037     if (UsingBB->isEHPad()) {
1038       // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
1039       // stores for it separately.
1040       assert(isa<PHINode>(UsingInst));
1041       continue;
1042     }
1043     replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1044   }
1045   return SpillSlot;
1046 }
1047
1048 // TODO: improve store placement.  Inserting at def is probably good, but need
1049 // to be careful not to introduce interfering stores (needs liveness analysis).
1050 // TODO: identify related phi nodes that can share spill slots, and share them
1051 // (also needs liveness).
1052 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1053                                    AllocaInst *SpillSlot) {
1054   // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1055   // stored to the spill slot by the end of the given Block.
1056   SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1057
1058   Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1059
1060   while (!Worklist.empty()) {
1061     BasicBlock *EHBlock;
1062     Value *InVal;
1063     std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1064
1065     PHINode *PN = dyn_cast<PHINode>(InVal);
1066     if (PN && PN->getParent() == EHBlock) {
1067       // The value is defined by another PHI we need to remove, with no room to
1068       // insert a store after the PHI, so each predecessor needs to store its
1069       // incoming value.
1070       for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1071         Value *PredVal = PN->getIncomingValue(i);
1072
1073         // Undef can safely be skipped.
1074         if (isa<UndefValue>(PredVal))
1075           continue;
1076
1077         insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1078       }
1079     } else {
1080       // We need to store InVal, which dominates EHBlock, but can't put a store
1081       // in EHBlock, so need to put stores in each predecessor.
1082       for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1083         insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1084       }
1085     }
1086   }
1087 }
1088
1089 void WinEHPrepare::insertPHIStore(
1090     BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1091     SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1092
1093   if (PredBlock->isEHPad() &&
1094       !isa<CleanupPadInst>(PredBlock->getFirstNonPHI())) {
1095     // Pred is unsplittable, so we need to queue it on the worklist.
1096     Worklist.push_back({PredBlock, PredVal});
1097     return;
1098   }
1099
1100   // Otherwise, insert the store at the end of the basic block.
1101   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1102 }
1103
1104 // TODO: Share loads for same-funclet uses (requires dominators if funclets
1105 // aren't properly nested).
1106 void WinEHPrepare::demoteNonlocalUses(Value *V,
1107                                       std::set<BasicBlock *> &ColorsForBB,
1108                                       Function &F) {
1109   // Tokens can only be used non-locally due to control flow involving
1110   // unreachable edges.  Don't try to demote the token usage, we'll simply
1111   // delete the cloned user later.
1112   if (isa<CatchPadInst>(V) || isa<CleanupPadInst>(V))
1113     return;
1114
1115   DenseMap<BasicBlock *, Value *> Loads;
1116   AllocaInst *SpillSlot = nullptr;
1117   for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;) {
1118     Use &U = *UI++;
1119     auto *UsingInst = cast<Instruction>(U.getUser());
1120     BasicBlock *UsingBB = UsingInst->getParent();
1121
1122     // Is the Use inside a block which is colored the same as the Def?
1123     // If so, we don't need to escape the Def because we will clone
1124     // ourselves our own private copy.
1125     std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
1126     if (ColorsForUsingBB == ColorsForBB)
1127       continue;
1128
1129     replaceUseWithLoad(V, U, SpillSlot, Loads, F);
1130   }
1131   if (SpillSlot) {
1132     // Insert stores of the computed value into the stack slot.
1133     // We have to be careful if I is an invoke instruction,
1134     // because we can't insert the store AFTER the terminator instruction.
1135     BasicBlock::iterator InsertPt;
1136     if (isa<Argument>(V)) {
1137       InsertPt = F.getEntryBlock().getTerminator()->getIterator();
1138     } else if (isa<TerminatorInst>(V)) {
1139       auto *II = cast<InvokeInst>(V);
1140       // We cannot demote invoke instructions to the stack if their normal
1141       // edge is critical. Therefore, split the critical edge and create a
1142       // basic block into which the store can be inserted.
1143       if (!II->getNormalDest()->getSinglePredecessor()) {
1144         unsigned SuccNum =
1145             GetSuccessorNumber(II->getParent(), II->getNormalDest());
1146         assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
1147         BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
1148         assert(NewBlock && "Unable to split critical edge.");
1149         // Update the color mapping for the newly split edge.
1150         std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[II->getParent()];
1151         BlockColors[NewBlock] = ColorsForUsingBB;
1152         for (BasicBlock *FuncletPad : ColorsForUsingBB)
1153           FuncletBlocks[FuncletPad].insert(NewBlock);
1154       }
1155       InsertPt = II->getNormalDest()->getFirstInsertionPt();
1156     } else {
1157       InsertPt = cast<Instruction>(V)->getIterator();
1158       ++InsertPt;
1159       // Don't insert before PHI nodes or EH pad instrs.
1160       for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
1161         ;
1162     }
1163     new StoreInst(V, SpillSlot, &*InsertPt);
1164   }
1165 }
1166
1167 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1168                                       DenseMap<BasicBlock *, Value *> &Loads,
1169                                       Function &F) {
1170   // Lazilly create the spill slot.
1171   if (!SpillSlot)
1172     SpillSlot = new AllocaInst(V->getType(), nullptr,
1173                                Twine(V->getName(), ".wineh.spillslot"),
1174                                &F.getEntryBlock().front());
1175
1176   auto *UsingInst = cast<Instruction>(U.getUser());
1177   if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1178     // If this is a PHI node, we can't insert a load of the value before
1179     // the use.  Instead insert the load in the predecessor block
1180     // corresponding to the incoming value.
1181     //
1182     // Note that if there are multiple edges from a basic block to this
1183     // PHI node that we cannot have multiple loads.  The problem is that
1184     // the resulting PHI node will have multiple values (from each load)
1185     // coming in from the same block, which is illegal SSA form.
1186     // For this reason, we keep track of and reuse loads we insert.
1187     BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1188     if (auto *CatchRet =
1189             dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1190       // Putting a load above a catchret and use on the phi would still leave
1191       // a cross-funclet def/use.  We need to split the edge, change the
1192       // catchret to target the new block, and put the load there.
1193       BasicBlock *PHIBlock = UsingInst->getParent();
1194       BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1195       // SplitEdge gives us:
1196       //   IncomingBlock:
1197       //     ...
1198       //     br label %NewBlock
1199       //   NewBlock:
1200       //     catchret label %PHIBlock
1201       // But we need:
1202       //   IncomingBlock:
1203       //     ...
1204       //     catchret label %NewBlock
1205       //   NewBlock:
1206       //     br label %PHIBlock
1207       // So move the terminators to each others' blocks and swap their
1208       // successors.
1209       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1210       Goto->removeFromParent();
1211       CatchRet->removeFromParent();
1212       IncomingBlock->getInstList().push_back(CatchRet);
1213       NewBlock->getInstList().push_back(Goto);
1214       Goto->setSuccessor(0, PHIBlock);
1215       CatchRet->setSuccessor(NewBlock);
1216       // Update the color mapping for the newly split edge.
1217       std::set<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock];
1218       BlockColors[NewBlock] = ColorsForPHIBlock;
1219       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1220         FuncletBlocks[FuncletPad].insert(NewBlock);
1221       // Treat the new block as incoming for load insertion.
1222       IncomingBlock = NewBlock;
1223     }
1224     Value *&Load = Loads[IncomingBlock];
1225     // Insert the load into the predecessor block
1226     if (!Load)
1227       Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1228                           /*Volatile=*/false, IncomingBlock->getTerminator());
1229
1230     U.set(Load);
1231   } else {
1232     // Reload right before the old use.
1233     auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1234                               /*Volatile=*/false, UsingInst);
1235     U.set(Load);
1236   }
1237 }
1238
1239 void WinEHFuncInfo::addIPToStateRange(const BasicBlock *PadBB,
1240                                       MCSymbol *InvokeBegin,
1241                                       MCSymbol *InvokeEnd) {
1242   assert(PadBB->isEHPad() && EHPadStateMap.count(PadBB->getFirstNonPHI()) &&
1243          "should get EH pad BB with precomputed state");
1244   InvokeToStateMap[InvokeBegin] =
1245       std::make_pair(EHPadStateMap[PadBB->getFirstNonPHI()], InvokeEnd);
1246 }