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