lib/CodeGen/WinEHPrepare.cpp

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