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