lib/CodeGen/WinEHPrepare.cpp

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