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/DenseMap.h"
  21 #include "llvm/ADT/MapVector.h"
  22 #include "llvm/ADT/STLExtras.h"
  23 #include "llvm/Analysis/CFG.h"
  24 #include "llvm/Analysis/EHPersonalities.h"
  25 #include "llvm/CodeGen/MachineBasicBlock.h"
  26 #include "llvm/CodeGen/WinEHFuncInfo.h"
  27 #include "llvm/IR/Verifier.h"
  28 #include "llvm/MC/MCSymbol.h"
  29 #include "llvm/Pass.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  33 #include "llvm/Transforms/Utils/Cloning.h"
  34 #include "llvm/Transforms/Utils/Local.h"
  35 #include "llvm/Transforms/Utils/SSAUpdater.h"
  36
  37 using namespace llvm;
  38
  39 #define DEBUG_TYPE "winehprepare"
  40
  41 static cl::opt<bool> DisableDemotion(
  42     "disable-demotion", cl::Hidden,
  43     cl::desc(
  44         "Clone multicolor basic blocks but do not demote cross funclet values"),
  45     cl::init(false));
  46
  47 static cl::opt<bool> DisableCleanups(
  48     "disable-cleanups", cl::Hidden,
  49     cl::desc("Do not remove implausible terminators or other similar cleanups"),
  50     cl::init(false));
  51
  52 namespace {
  53
  54 class WinEHPrepare : public FunctionPass {
  55 public:
  56   static char ID; // Pass identification, replacement for typeid.
  57   WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
  58
  59   bool runOnFunction(Function &Fn) override;
  60
  61   bool doFinalization(Module &M) override;
  62
  63   void getAnalysisUsage(AnalysisUsage &AU) const override;
  64
  65   const char *getPassName() const override {
  66     return "Windows exception handling preparation";
  67   }
  68
  69 private:
  70   void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
  71   void
  72   insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
  73                  SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
  74   AllocaInst *insertPHILoads(PHINode *PN, Function &F);
  75   void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
  76                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
  77   bool prepareExplicitEH(Function &F);
  78   void colorFunclets(Function &F);
  79
  80   void demotePHIsOnFunclets(Function &F);
  81   void cloneCommonBlocks(Function &F);
  82   void removeImplausibleInstructions(Function &F);
  83   void cleanupPreparedFunclets(Function &F);
  84   void verifyPreparedFunclets(Function &F);
  85
  86   // All fields are reset by runOnFunction.
  87   EHPersonality Personality = EHPersonality::Unknown;
  88
  89   DenseMap<BasicBlock *, ColorVector> BlockColors;
  90   MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
  91 };
  92
  93 } // end anonymous namespace
  94
  95 char WinEHPrepare::ID = 0;
  96 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
  97                    false, false)
  98
  99 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
 100   return new WinEHPrepare(TM);
 101 }
 102
 103 bool WinEHPrepare::runOnFunction(Function &Fn) {
 104   if (!Fn.hasPersonalityFn())
 105     return false;
 106
 107   // Classify the personality to see what kind of preparation we need.
 108   Personality = classifyEHPersonality(Fn.getPersonalityFn());
 109
 110   // Do nothing if this is not a funclet-based personality.
 111   if (!isFuncletEHPersonality(Personality))
 112     return false;
 113
 114   return prepareExplicitEH(Fn);
 115 }
 116
 117 bool WinEHPrepare::doFinalization(Module &M) { return false; }
 118
 119 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
 120
 121 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
 122                              const BasicBlock *BB) {
 123   CxxUnwindMapEntry UME;
 124   UME.ToState = ToState;
 125   UME.Cleanup = BB;
 126   FuncInfo.CxxUnwindMap.push_back(UME);
 127   return FuncInfo.getLastStateNumber();
 128 }
 129
 130 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
 131                                 int TryHigh, int CatchHigh,
 132                                 ArrayRef<const CatchPadInst *> Handlers) {
 133   WinEHTryBlockMapEntry TBME;
 134   TBME.TryLow = TryLow;
 135   TBME.TryHigh = TryHigh;
 136   TBME.CatchHigh = CatchHigh;
 137   assert(TBME.TryLow <= TBME.TryHigh);
 138   for (const CatchPadInst *CPI : Handlers) {
 139     WinEHHandlerType HT;
 140     Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
 141     if (TypeInfo->isNullValue())
 142       HT.TypeDescriptor = nullptr;
 143     else
 144       HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
 145     HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
 146     HT.Handler = CPI->getParent();
 147     if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
 148       HT.CatchObj.Alloca = nullptr;
 149     else
 150       HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
 151     TBME.HandlerArray.push_back(HT);
 152   }
 153   FuncInfo.TryBlockMap.push_back(TBME);
 154 }
 155
 156 static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
 157   for (const User *U : CleanupPad->users())
 158     if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
 159       return CRI->getUnwindDest();
 160   return nullptr;
 161 }
 162
 163 static void calculateStateNumbersForInvokes(const Function *Fn,
 164                                             WinEHFuncInfo &FuncInfo) {
 165   auto *F = const_cast<Function *>(Fn);
 166   DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
 167   for (BasicBlock &BB : *F) {
 168     auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
 169     if (!II)
 170       continue;
 171
 172     auto &BBColors = BlockColors[&BB];
 173     assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
 174     BasicBlock *FuncletEntryBB = BBColors.front();
 175
 176     BasicBlock *FuncletUnwindDest;
 177     auto *FuncletPad =
 178         dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
 179     assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
 180     if (!FuncletPad)
 181       FuncletUnwindDest = nullptr;
 182     else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
 183       FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
 184     else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
 185       FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
 186     else
 187       llvm_unreachable("unexpected funclet pad!");
 188
 189     BasicBlock *InvokeUnwindDest = II->getUnwindDest();
 190     int BaseState = -1;
 191     if (FuncletUnwindDest == InvokeUnwindDest) {
 192       auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
 193       if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
 194         BaseState = BaseStateI->second;
 195     }
 196
 197     if (BaseState != -1) {
 198       FuncInfo.InvokeStateMap[II] = BaseState;
 199     } else {
 200       Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
 201       assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
 202       FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
 203     }
 204   }
 205 }
 206
 207 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
 208 // to. If the unwind edge came from an invoke, return null.
 209 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
 210                                                  Value *ParentPad) {
 211   const TerminatorInst *TI = BB->getTerminator();
 212   if (isa<InvokeInst>(TI))
 213     return nullptr;
 214   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
 215     if (CatchSwitch->getParentPad() != ParentPad)
 216       return nullptr;
 217     return BB;
 218   }
 219   assert(!TI->isEHPad() && "unexpected EHPad!");
 220   auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
 221   if (CleanupPad->getParentPad() != ParentPad)
 222     return nullptr;
 223   return CleanupPad->getParent();
 224 }
 225
 226 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
 227                                      const Instruction *FirstNonPHI,
 228                                      int ParentState) {
 229   const BasicBlock *BB = FirstNonPHI->getParent();
 230   assert(BB->isEHPad() && "not a funclet!");
 231
 232   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
 233     assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
 234            "shouldn't revist catch funclets!");
 235
 236     SmallVector<const CatchPadInst *, 2> Handlers;
 237     for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
 238       auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
 239       Handlers.push_back(CatchPad);
 240     }
 241     int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
 242     FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
 243     for (const BasicBlock *PredBlock : predecessors(BB))
 244       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
 245                                                CatchSwitch->getParentPad())))
 246         calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 247                                  TryLow);
 248     int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
 249
 250     // catchpads are separate funclets in C++ EH due to the way rethrow works.
 251     int TryHigh = CatchLow - 1;
 252     for (const auto *CatchPad : Handlers) {
 253       FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
 254       for (const User *U : CatchPad->users()) {
 255         const auto *UserI = cast<Instruction>(U);
 256         if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
 257           if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
 258             calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
 259         if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
 260           if (getCleanupRetUnwindDest(InnerCleanupPad) ==
 261               CatchSwitch->getUnwindDest())
 262             calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
 263       }
 264     }
 265     int CatchHigh = FuncInfo.getLastStateNumber();
 266     addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
 267     DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
 268     DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh << '\n');
 269     DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
 270                  << '\n');
 271   } else {
 272     auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
 273
 274     // It's possible for a cleanup to be visited twice: it might have multiple
 275     // cleanupret instructions.
 276     if (FuncInfo.EHPadStateMap.count(CleanupPad))
 277       return;
 278
 279     int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
 280     FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
 281     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
 282                  << BB->getName() << '\n');
 283     for (const BasicBlock *PredBlock : predecessors(BB)) {
 284       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
 285                                                CleanupPad->getParentPad()))) {
 286         calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 287                                  CleanupState);
 288       }
 289     }
 290     for (const User *U : CleanupPad->users()) {
 291       const auto *UserI = cast<Instruction>(U);
 292       if (UserI->isEHPad())
 293         report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
 294                            "contain exceptional actions");
 295     }
 296   }
 297 }
 298
 299 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
 300                         const Function *Filter, const BasicBlock *Handler) {
 301   SEHUnwindMapEntry Entry;
 302   Entry.ToState = ParentState;
 303   Entry.IsFinally = false;
 304   Entry.Filter = Filter;
 305   Entry.Handler = Handler;
 306   FuncInfo.SEHUnwindMap.push_back(Entry);
 307   return FuncInfo.SEHUnwindMap.size() - 1;
 308 }
 309
 310 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
 311                          const BasicBlock *Handler) {
 312   SEHUnwindMapEntry Entry;
 313   Entry.ToState = ParentState;
 314   Entry.IsFinally = true;
 315   Entry.Filter = nullptr;
 316   Entry.Handler = Handler;
 317   FuncInfo.SEHUnwindMap.push_back(Entry);
 318   return FuncInfo.SEHUnwindMap.size() - 1;
 319 }
 320
 321 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
 322                                      const Instruction *FirstNonPHI,
 323                                      int ParentState) {
 324   const BasicBlock *BB = FirstNonPHI->getParent();
 325   assert(BB->isEHPad() && "no a funclet!");
 326
 327   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
 328     assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
 329            "shouldn't revist catch funclets!");
 330
 331     // Extract the filter function and the __except basic block and create a
 332     // state for them.
 333     assert(CatchSwitch->getNumHandlers() == 1 &&
 334            "SEH doesn't have multiple handlers per __try");
 335     const auto *CatchPad =
 336         cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
 337     const BasicBlock *CatchPadBB = CatchPad->getParent();
 338     const Constant *FilterOrNull =
 339         cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
 340     const Function *Filter = dyn_cast<Function>(FilterOrNull);
 341     assert((Filter || FilterOrNull->isNullValue()) &&
 342            "unexpected filter value");
 343     int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
 344
 345     // Everything in the __try block uses TryState as its parent state.
 346     FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
 347     DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
 348                  << CatchPadBB->getName() << '\n');
 349     for (const BasicBlock *PredBlock : predecessors(BB))
 350       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
 351                                                CatchSwitch->getParentPad())))
 352         calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 353                                  TryState);
 354
 355     // Everything in the __except block unwinds to ParentState, just like code
 356     // outside the __try.
 357     for (const User *U : CatchPad->users()) {
 358       const auto *UserI = cast<Instruction>(U);
 359       if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
 360         if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
 361           calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
 362       if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
 363         if (getCleanupRetUnwindDest(InnerCleanupPad) ==
 364             CatchSwitch->getUnwindDest())
 365           calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
 366     }
 367   } else {
 368     auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
 369
 370     // It's possible for a cleanup to be visited twice: it might have multiple
 371     // cleanupret instructions.
 372     if (FuncInfo.EHPadStateMap.count(CleanupPad))
 373       return;
 374
 375     int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
 376     FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
 377     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
 378                  << BB->getName() << '\n');
 379     for (const BasicBlock *PredBlock : predecessors(BB))
 380       if ((PredBlock =
 381                getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
 382         calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
 383                                  CleanupState);
 384     for (const User *U : CleanupPad->users()) {
 385       const auto *UserI = cast<Instruction>(U);
 386       if (UserI->isEHPad())
 387         report_fatal_error("Cleanup funclets for the SEH personality cannot "
 388                            "contain exceptional actions");
 389     }
 390   }
 391 }
 392
 393 static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
 394   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
 395     return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
 396            CatchSwitch->unwindsToCaller();
 397   if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
 398     return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
 399            getCleanupRetUnwindDest(CleanupPad) == nullptr;
 400   if (isa<CatchPadInst>(EHPad))
 401     return false;
 402   llvm_unreachable("unexpected EHPad!");
 403 }
 404
 405 void llvm::calculateSEHStateNumbers(const Function *Fn,
 406                                     WinEHFuncInfo &FuncInfo) {
 407   // Don't compute state numbers twice.
 408   if (!FuncInfo.SEHUnwindMap.empty())
 409     return;
 410
 411   for (const BasicBlock &BB : *Fn) {
 412     if (!BB.isEHPad())
 413       continue;
 414     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 415     if (!isTopLevelPadForMSVC(FirstNonPHI))
 416       continue;
 417     ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
 418   }
 419
 420   calculateStateNumbersForInvokes(Fn, FuncInfo);
 421 }
 422
 423 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
 424                                          WinEHFuncInfo &FuncInfo) {
 425   // Return if it's already been done.
 426   if (!FuncInfo.EHPadStateMap.empty())
 427     return;
 428
 429   for (const BasicBlock &BB : *Fn) {
 430     if (!BB.isEHPad())
 431       continue;
 432     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 433     if (!isTopLevelPadForMSVC(FirstNonPHI))
 434       continue;
 435     calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
 436   }
 437
 438   calculateStateNumbersForInvokes(Fn, FuncInfo);
 439 }
 440
 441 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int HandlerParentState,
 442                            int TryParentState, ClrHandlerType HandlerType,
 443                            uint32_t TypeToken, const BasicBlock *Handler) {
 444   ClrEHUnwindMapEntry Entry;
 445   Entry.HandlerParentState = HandlerParentState;
 446   Entry.TryParentState = TryParentState;
 447   Entry.Handler = Handler;
 448   Entry.HandlerType = HandlerType;
 449   Entry.TypeToken = TypeToken;
 450   FuncInfo.ClrEHUnwindMap.push_back(Entry);
 451   return FuncInfo.ClrEHUnwindMap.size() - 1;
 452 }
 453
 454 void llvm::calculateClrEHStateNumbers(const Function *Fn,
 455                                       WinEHFuncInfo &FuncInfo) {
 456   // Return if it's already been done.
 457   if (!FuncInfo.EHPadStateMap.empty())
 458     return;
 459
 460   // This numbering assigns one state number to each catchpad and cleanuppad.
 461   // It also computes two tree-like relations over states:
 462   // 1) Each state has a "HandlerParentState", which is the state of the next
 463   //    outer handler enclosing this state's handler (same as nearest ancestor
 464   //    per the ParentPad linkage on EH pads, but skipping over catchswitches).
 465   // 2) Each state has a "TryParentState", which:
 466   //    a) for a catchpad that's not the last handler on its catchswitch, is
 467   //       the state of the next catchpad on that catchswitch
 468   //    b) for all other pads, is the state of the pad whose try region is the
 469   //       next outer try region enclosing this state's try region.  The "try
 470   //       regions are not present as such in the IR, but will be inferred
 471   //       based on the placement of invokes and pads which reach each other
 472   //       by exceptional exits
 473   // Catchswitches do not get their own states, but each gets mapped to the
 474   // state of its first catchpad.
 475
 476   // Step one: walk down from outermost to innermost funclets, assigning each
 477   // catchpad and cleanuppad a state number.  Add an entry to the
 478   // ClrEHUnwindMap for each state, recording its HandlerParentState and
 479   // handler attributes.  Record the TryParentState as well for each catchpad
 480   // that's not the last on its catchswitch, but initialize all other entries'
 481   // TryParentStates to a sentinel -1 value that the next pass will update.
 482
 483   // Seed a worklist with pads that have no parent.
 484   SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
 485   for (const BasicBlock &BB : *Fn) {
 486     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
 487     const Value *ParentPad;
 488     if (const auto *CPI = dyn_cast<CleanupPadInst>(FirstNonPHI))
 489       ParentPad = CPI->getParentPad();
 490     else if (const auto *CSI = dyn_cast<CatchSwitchInst>(FirstNonPHI))
 491       ParentPad = CSI->getParentPad();
 492     else
 493       continue;
 494     if (isa<ConstantTokenNone>(ParentPad))
 495       Worklist.emplace_back(FirstNonPHI, -1);
 496   }
 497
 498   // Use the worklist to visit all pads, from outer to inner.  Record
 499   // HandlerParentState for all pads.  Record TryParentState only for catchpads
 500   // that aren't the last on their catchswitch (setting all other entries'
 501   // TryParentStates to an initial value of -1).  This loop is also responsible
 502   // for setting the EHPadStateMap entry for all catchpads, cleanuppads, and
 503   // catchswitches.
 504   while (!Worklist.empty()) {
 505     const Instruction *Pad;
 506     int HandlerParentState;
 507     std::tie(Pad, HandlerParentState) = Worklist.pop_back_val();
 508
 509     if (const auto *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
 510       // Create the entry for this cleanup with the appropriate handler
 511       // properties.  Finaly and fault handlers are distinguished by arity.
 512       ClrHandlerType HandlerType =
 513           (Cleanup->getNumArgOperands() ? ClrHandlerType::Fault
 514                                         : ClrHandlerType::Finally);
 515       int CleanupState = addClrEHHandler(FuncInfo, HandlerParentState, -1,
 516                                          HandlerType, 0, Pad->getParent());
 517       // Queue any child EH pads on the worklist.
 518       for (const User *U : Cleanup->users())
 519         if (const auto *I = dyn_cast<Instruction>(U))
 520           if (I->isEHPad())
 521             Worklist.emplace_back(I, CleanupState);
 522       // Remember this pad's state.
 523       FuncInfo.EHPadStateMap[Cleanup] = CleanupState;
 524     } else {
 525       // Walk the handlers of this catchswitch in reverse order since all but
 526       // the last need to set the following one as its TryParentState.
 527       const auto *CatchSwitch = cast<CatchSwitchInst>(Pad);
 528       int CatchState = -1, FollowerState = -1;
 529       SmallVector<const BasicBlock *, 4> CatchBlocks(CatchSwitch->handlers());
 530       for (auto CBI = CatchBlocks.rbegin(), CBE = CatchBlocks.rend();
 531            CBI != CBE; ++CBI, FollowerState = CatchState) {
 532         const BasicBlock *CatchBlock = *CBI;
 533         // Create the entry for this catch with the appropriate handler
 534         // properties.
 535         const auto *Catch = cast<CatchPadInst>(CatchBlock->getFirstNonPHI());
 536         uint32_t TypeToken = static_cast<uint32_t>(
 537             cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
 538         CatchState =
 539             addClrEHHandler(FuncInfo, HandlerParentState, FollowerState,
 540                             ClrHandlerType::Catch, TypeToken, CatchBlock);
 541         // Queue any child EH pads on the worklist.
 542         for (const User *U : Catch->users())
 543           if (const auto *I = dyn_cast<Instruction>(U))
 544             if (I->isEHPad())
 545               Worklist.emplace_back(I, CatchState);
 546         // Remember this catch's state.
 547         FuncInfo.EHPadStateMap[Catch] = CatchState;
 548       }
 549       // Associate the catchswitch with the state of its first catch.
 550       assert(CatchSwitch->getNumHandlers());
 551       FuncInfo.EHPadStateMap[CatchSwitch] = CatchState;
 552     }
 553   }
 554
 555   // Step two: record the TryParentState of each state.  For cleanuppads that
 556   // don't have cleanuprets, we may need to infer this from their child pads,
 557   // so visit pads in descendant-most to ancestor-most order.
 558   for (auto Entry = FuncInfo.ClrEHUnwindMap.rbegin(),
 559             End = FuncInfo.ClrEHUnwindMap.rend();
 560        Entry != End; ++Entry) {
 561     const Instruction *Pad =
 562         Entry->Handler.get<const BasicBlock *>()->getFirstNonPHI();
 563     // For most pads, the TryParentState is the state associated with the
 564     // unwind dest of exceptional exits from it.
 565     const BasicBlock *UnwindDest;
 566     if (const auto *Catch = dyn_cast<CatchPadInst>(Pad)) {
 567       // If a catch is not the last in its catchswitch, its TryParentState is
 568       // the state associated with the next catch in the switch, even though
 569       // that's not the unwind dest of exceptions escaping the catch.  Those
 570       // cases were already assigned a TryParentState in the first pass, so
 571       // skip them.
 572       if (Entry->TryParentState != -1)
 573         continue;
 574       // Otherwise, get the unwind dest from the catchswitch.
 575       UnwindDest = Catch->getCatchSwitch()->getUnwindDest();
 576     } else {
 577       const auto *Cleanup = cast<CleanupPadInst>(Pad);
 578       UnwindDest = nullptr;
 579       for (const User *U : Cleanup->users()) {
 580         if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {
 581           // Common and unambiguous case -- cleanupret indicates cleanup's
 582           // unwind dest.
 583           UnwindDest = CleanupRet->getUnwindDest();
 584           break;
 585         }
 586
 587         // Get an unwind dest for the user
 588         const BasicBlock *UserUnwindDest = nullptr;
 589         if (auto *Invoke = dyn_cast<InvokeInst>(U)) {
 590           UserUnwindDest = Invoke->getUnwindDest();
 591         } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(U)) {
 592           UserUnwindDest = CatchSwitch->getUnwindDest();
 593         } else if (auto *ChildCleanup = dyn_cast<CleanupPadInst>(U)) {
 594           int UserState = FuncInfo.EHPadStateMap[ChildCleanup];
 595           int UserUnwindState =
 596               FuncInfo.ClrEHUnwindMap[UserState].TryParentState;
 597           if (UserUnwindState != -1)
 598             UserUnwindDest = FuncInfo.ClrEHUnwindMap[UserUnwindState]
 599                                  .Handler.get<const BasicBlock *>();
 600         }
 601
 602         // Not having an unwind dest for this user might indicate that it
 603         // doesn't unwind, so can't be taken as proof that the cleanup itself
 604         // may unwind to caller (see e.g. SimplifyUnreachable and
 605         // RemoveUnwindEdge).
 606         if (!UserUnwindDest)
 607           continue;
 608
 609         // Now we have an unwind dest for the user, but we need to see if it
 610         // unwinds all the way out of the cleanup or if it stays within it.
 611         const Instruction *UserUnwindPad = UserUnwindDest->getFirstNonPHI();
 612         const Value *UserUnwindParent;
 613         if (auto *CSI = dyn_cast<CatchSwitchInst>(UserUnwindPad))
 614           UserUnwindParent = CSI->getParentPad();
 615         else
 616           UserUnwindParent =
 617               cast<CleanupPadInst>(UserUnwindPad)->getParentPad();
 618
 619         // The unwind stays within the cleanup iff it targets a child of the
 620         // cleanup.
 621         if (UserUnwindParent == Cleanup)
 622           continue;
 623
 624         // This unwind exits the cleanup, so its dest is the cleanup's dest.
 625         UnwindDest = UserUnwindDest;
 626         break;
 627       }
 628     }
 629
 630     // Record the state of the unwind dest as the TryParentState.
 631     int UnwindDestState;
 632
 633     // If UnwindDest is null at this point, either the pad in question can
 634     // be exited by unwind to caller, or it cannot be exited by unwind.  In
 635     // either case, reporting such cases as unwinding to caller is correct.
 636     // This can lead to EH tables that "look strange" -- if this pad's is in
 637     // a parent funclet which has other children that do unwind to an enclosing
 638     // pad, the try region for this pad will be missing the "duplicate" EH
 639     // clause entries that you'd expect to see covering the whole parent.  That
 640     // should be benign, since the unwind never actually happens.  If it were
 641     // an issue, we could add a subsequent pass that pushes unwind dests down
 642     // from parents that have them to children that appear to unwind to caller.
 643     if (!UnwindDest) {
 644       UnwindDestState = -1;
 645     } else {
 646       UnwindDestState = FuncInfo.EHPadStateMap[UnwindDest->getFirstNonPHI()];
 647     }
 648
 649     Entry->TryParentState = UnwindDestState;
 650   }
 651
 652   // Step three: transfer information from pads to invokes.
 653   calculateStateNumbersForInvokes(Fn, FuncInfo);
 654 }
 655
 656 void WinEHPrepare::colorFunclets(Function &F) {
 657   BlockColors = colorEHFunclets(F);
 658
 659   // Invert the map from BB to colors to color to BBs.
 660   for (BasicBlock &BB : F) {
 661     ColorVector &Colors = BlockColors[&BB];
 662     for (BasicBlock *Color : Colors)
 663       FuncletBlocks[Color].push_back(&BB);
 664   }
 665 }
 666
 667 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
 668   // Strip PHI nodes off of EH pads.
 669   SmallVector<PHINode *, 16> PHINodes;
 670   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 671     BasicBlock *BB = &*FI++;
 672     if (!BB->isEHPad())
 673       continue;
 674     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
 675       Instruction *I = &*BI++;
 676       auto *PN = dyn_cast<PHINode>(I);
 677       // Stop at the first non-PHI.
 678       if (!PN)
 679         break;
 680
 681       AllocaInst *SpillSlot = insertPHILoads(PN, F);
 682       if (SpillSlot)
 683         insertPHIStores(PN, SpillSlot);
 684
 685       PHINodes.push_back(PN);
 686     }
 687   }
 688
 689   for (auto *PN : PHINodes) {
 690     // There may be lingering uses on other EH PHIs being removed
 691     PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
 692     PN->eraseFromParent();
 693   }
 694 }
 695
 696 void WinEHPrepare::cloneCommonBlocks(Function &F) {
 697   // We need to clone all blocks which belong to multiple funclets.  Values are
 698   // remapped throughout the funclet to propogate both the new instructions
 699   // *and* the new basic blocks themselves.
 700   for (auto &Funclets : FuncletBlocks) {
 701     BasicBlock *FuncletPadBB = Funclets.first;
 702     std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
 703     Value *FuncletToken;
 704     if (FuncletPadBB == &F.getEntryBlock())
 705       FuncletToken = ConstantTokenNone::get(F.getContext());
 706     else
 707       FuncletToken = FuncletPadBB->getFirstNonPHI();
 708
 709     std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
 710     ValueToValueMapTy VMap;
 711     for (BasicBlock *BB : BlocksInFunclet) {
 712       ColorVector &ColorsForBB = BlockColors[BB];
 713       // We don't need to do anything if the block is monochromatic.
 714       size_t NumColorsForBB = ColorsForBB.size();
 715       if (NumColorsForBB == 1)
 716         continue;
 717
 718       DEBUG_WITH_TYPE("winehprepare-coloring",
 719                       dbgs() << "  Cloning block \'" << BB->getName()
 720                               << "\' for funclet \'" << FuncletPadBB->getName()
 721                               << "\'.\n");
 722
 723       // Create a new basic block and copy instructions into it!
 724       BasicBlock *CBB =
 725           CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
 726       // Insert the clone immediately after the original to ensure determinism
 727       // and to keep the same relative ordering of any funclet's blocks.
 728       CBB->insertInto(&F, BB->getNextNode());
 729
 730       // Add basic block mapping.
 731       VMap[BB] = CBB;
 732
 733       // Record delta operations that we need to perform to our color mappings.
 734       Orig2Clone.emplace_back(BB, CBB);
 735     }
 736
 737     // If nothing was cloned, we're done cloning in this funclet.
 738     if (Orig2Clone.empty())
 739       continue;
 740
 741     // Update our color mappings to reflect that one block has lost a color and
 742     // another has gained a color.
 743     for (auto &BBMapping : Orig2Clone) {
 744       BasicBlock *OldBlock = BBMapping.first;
 745       BasicBlock *NewBlock = BBMapping.second;
 746
 747       BlocksInFunclet.push_back(NewBlock);
 748       ColorVector &NewColors = BlockColors[NewBlock];
 749       assert(NewColors.empty() && "A new block should only have one color!");
 750       NewColors.push_back(FuncletPadBB);
 751
 752       DEBUG_WITH_TYPE("winehprepare-coloring",
 753                       dbgs() << "  Assigned color \'" << FuncletPadBB->getName()
 754                               << "\' to block \'" << NewBlock->getName()
 755                               << "\'.\n");
 756
 757       BlocksInFunclet.erase(
 758           std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
 759           BlocksInFunclet.end());
 760       ColorVector &OldColors = BlockColors[OldBlock];
 761       OldColors.erase(
 762           std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
 763           OldColors.end());
 764
 765       DEBUG_WITH_TYPE("winehprepare-coloring",
 766                       dbgs() << "  Removed color \'" << FuncletPadBB->getName()
 767                               << "\' from block \'" << OldBlock->getName()
 768                               << "\'.\n");
 769     }
 770
 771     // Loop over all of the instructions in this funclet, fixing up operand
 772     // references as we go.  This uses VMap to do all the hard work.
 773     for (BasicBlock *BB : BlocksInFunclet)
 774       // Loop over all instructions, fixing each one as we find it...
 775       for (Instruction &I : *BB)
 776         RemapInstruction(&I, VMap,
 777                          RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
 778
 779     // Catchrets targeting cloned blocks need to be updated separately from
 780     // the loop above because they are not in the current funclet.
 781     SmallVector<CatchReturnInst *, 2> FixupCatchrets;
 782     for (auto &BBMapping : Orig2Clone) {
 783       BasicBlock *OldBlock = BBMapping.first;
 784       BasicBlock *NewBlock = BBMapping.second;
 785
 786       FixupCatchrets.clear();
 787       for (BasicBlock *Pred : predecessors(OldBlock))
 788         if (auto *CatchRet = dyn_cast<CatchReturnInst>(Pred->getTerminator()))
 789           if (CatchRet->getParentPad() == FuncletToken)
 790             FixupCatchrets.push_back(CatchRet);
 791
 792       for (CatchReturnInst *CatchRet : FixupCatchrets)
 793         CatchRet->setSuccessor(NewBlock);
 794     }
 795
 796     auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
 797       unsigned NumPreds = PN->getNumIncomingValues();
 798       for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
 799            ++PredIdx) {
 800         BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
 801         bool EdgeTargetsFunclet;
 802         if (auto *CRI =
 803                 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
 804           EdgeTargetsFunclet = (CRI->getParentPad() == FuncletToken);
 805         } else {
 806           ColorVector &IncomingColors = BlockColors[IncomingBlock];
 807           assert(!IncomingColors.empty() && "Block not colored!");
 808           assert((IncomingColors.size() == 1 ||
 809                   llvm::all_of(IncomingColors,
 810                                [&](BasicBlock *Color) {
 811                                  return Color != FuncletPadBB;
 812                                })) &&
 813                  "Cloning should leave this funclet's blocks monochromatic");
 814           EdgeTargetsFunclet = (IncomingColors.front() == FuncletPadBB);
 815         }
 816         if (IsForOldBlock != EdgeTargetsFunclet)
 817           continue;
 818         PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
 819         // Revisit the next entry.
 820         --PredIdx;
 821         --PredEnd;
 822       }
 823     };
 824
 825     for (auto &BBMapping : Orig2Clone) {
 826       BasicBlock *OldBlock = BBMapping.first;
 827       BasicBlock *NewBlock = BBMapping.second;
 828       for (Instruction &OldI : *OldBlock) {
 829         auto *OldPN = dyn_cast<PHINode>(&OldI);
 830         if (!OldPN)
 831           break;
 832         UpdatePHIOnClonedBlock(OldPN, /*IsForOldBlock=*/true);
 833       }
 834       for (Instruction &NewI : *NewBlock) {
 835         auto *NewPN = dyn_cast<PHINode>(&NewI);
 836         if (!NewPN)
 837           break;
 838         UpdatePHIOnClonedBlock(NewPN, /*IsForOldBlock=*/false);
 839       }
 840     }
 841
 842     // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
 843     // the PHI nodes for NewBB now.
 844     for (auto &BBMapping : Orig2Clone) {
 845       BasicBlock *OldBlock = BBMapping.first;
 846       BasicBlock *NewBlock = BBMapping.second;
 847       for (BasicBlock *SuccBB : successors(NewBlock)) {
 848         for (Instruction &SuccI : *SuccBB) {
 849           auto *SuccPN = dyn_cast<PHINode>(&SuccI);
 850           if (!SuccPN)
 851             break;
 852
 853           // Ok, we have a PHI node.  Figure out what the incoming value was for
 854           // the OldBlock.
 855           int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
 856           if (OldBlockIdx == -1)
 857             break;
 858           Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
 859
 860           // Remap the value if necessary.
 861           if (auto *Inst = dyn_cast<Instruction>(IV)) {
 862             ValueToValueMapTy::iterator I = VMap.find(Inst);
 863             if (I != VMap.end())
 864               IV = I->second;
 865           }
 866
 867           SuccPN->addIncoming(IV, NewBlock);
 868         }
 869       }
 870     }
 871
 872     for (ValueToValueMapTy::value_type VT : VMap) {
 873       // If there were values defined in BB that are used outside the funclet,
 874       // then we now have to update all uses of the value to use either the
 875       // original value, the cloned value, or some PHI derived value.  This can
 876       // require arbitrary PHI insertion, of which we are prepared to do, clean
 877       // these up now.
 878       SmallVector<Use *, 16> UsesToRename;
 879
 880       auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
 881       if (!OldI)
 882         continue;
 883       auto *NewI = cast<Instruction>(VT.second);
 884       // Scan all uses of this instruction to see if it is used outside of its
 885       // funclet, and if so, record them in UsesToRename.
 886       for (Use &U : OldI->uses()) {
 887         Instruction *UserI = cast<Instruction>(U.getUser());
 888         BasicBlock *UserBB = UserI->getParent();
 889         ColorVector &ColorsForUserBB = BlockColors[UserBB];
 890         assert(!ColorsForUserBB.empty());
 891         if (ColorsForUserBB.size() > 1 ||
 892             *ColorsForUserBB.begin() != FuncletPadBB)
 893           UsesToRename.push_back(&U);
 894       }
 895
 896       // If there are no uses outside the block, we're done with this
 897       // instruction.
 898       if (UsesToRename.empty())
 899         continue;
 900
 901       // We found a use of OldI outside of the funclet.  Rename all uses of OldI
 902       // that are outside its funclet to be uses of the appropriate PHI node
 903       // etc.
 904       SSAUpdater SSAUpdate;
 905       SSAUpdate.Initialize(OldI->getType(), OldI->getName());
 906       SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
 907       SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
 908
 909       while (!UsesToRename.empty())
 910         SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
 911     }
 912   }
 913 }
 914
 915 void WinEHPrepare::removeImplausibleInstructions(Function &F) {
 916   // Remove implausible terminators and replace them with UnreachableInst.
 917   for (auto &Funclet : FuncletBlocks) {
 918     BasicBlock *FuncletPadBB = Funclet.first;
 919     std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
 920     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
 921     auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);
 922     auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);
 923     auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);
 924
 925     for (BasicBlock *BB : BlocksInFunclet) {
 926       for (Instruction &I : *BB) {
 927         CallSite CS(&I);
 928         if (!CS)
 929           continue;
 930
 931         Value *FuncletBundleOperand = nullptr;
 932         if (auto BU = CS.getOperandBundle(LLVMContext::OB_funclet))
 933           FuncletBundleOperand = BU->Inputs.front();
 934
 935         if (FuncletBundleOperand == FuncletPad)
 936           continue;
 937
 938         // Skip call sites which are nounwind intrinsics.
 939         auto *CalledFn =
 940             dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
 941         if (CalledFn && CalledFn->isIntrinsic() && CS.doesNotThrow())
 942           continue;
 943
 944         // This call site was not part of this funclet, remove it.
 945         if (CS.isInvoke()) {
 946           // Remove the unwind edge if it was an invoke.
 947           removeUnwindEdge(BB);
 948           // Get a pointer to the new call.
 949           BasicBlock::iterator CallI =
 950               std::prev(BB->getTerminator()->getIterator());
 951           auto *CI = cast<CallInst>(&*CallI);
 952           changeToUnreachable(CI, /*UseLLVMTrap=*/false);
 953         } else {
 954           changeToUnreachable(&I, /*UseLLVMTrap=*/false);
 955         }
 956
 957         // There are no more instructions in the block (except for unreachable),
 958         // we are done.
 959         break;
 960       }
 961
 962       TerminatorInst *TI = BB->getTerminator();
 963       // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
 964       bool IsUnreachableRet = isa<ReturnInst>(TI) && FuncletPad;
 965       // The token consumed by a CatchReturnInst must match the funclet token.
 966       bool IsUnreachableCatchret = false;
 967       if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
 968         IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
 969       // The token consumed by a CleanupReturnInst must match the funclet token.
 970       bool IsUnreachableCleanupret = false;
 971       if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
 972         IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
 973       if (IsUnreachableRet || IsUnreachableCatchret ||
 974           IsUnreachableCleanupret) {
 975         changeToUnreachable(TI, /*UseLLVMTrap=*/false);
 976       } else if (isa<InvokeInst>(TI)) {
 977         if (Personality == EHPersonality::MSVC_CXX && CleanupPad) {
 978           // Invokes within a cleanuppad for the MSVC++ personality never
 979           // transfer control to their unwind edge: the personality will
 980           // terminate the program.
 981           removeUnwindEdge(BB);
 982         }
 983       }
 984     }
 985   }
 986 }
 987
 988 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
 989   // Clean-up some of the mess we made by removing useles PHI nodes, trivial
 990   // branches, etc.
 991   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
 992     BasicBlock *BB = &*FI++;
 993     SimplifyInstructionsInBlock(BB);
 994     ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
 995     MergeBlockIntoPredecessor(BB);
 996   }
 997
 998   // We might have some unreachable blocks after cleaning up some impossible
 999   // control flow.
1000   removeUnreachableBlocks(F);
1001 }
1002
1003 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
1004   for (BasicBlock &BB : F) {
1005     size_t NumColors = BlockColors[&BB].size();
1006     assert(NumColors == 1 && "Expected monochromatic BB!");
1007     if (NumColors == 0)
1008       report_fatal_error("Uncolored BB!");
1009     if (NumColors > 1)
1010       report_fatal_error("Multicolor BB!");
1011     assert((DisableDemotion || !(BB.isEHPad() && isa<PHINode>(BB.begin()))) &&
1012            "EH Pad still has a PHI!");
1013   }
1014 }
1015
1016 bool WinEHPrepare::prepareExplicitEH(Function &F) {
1017   // Remove unreachable blocks.  It is not valuable to assign them a color and
1018   // their existence can trick us into thinking values are alive when they are
1019   // not.
1020   removeUnreachableBlocks(F);
1021
1022   // Determine which blocks are reachable from which funclet entries.
1023   colorFunclets(F);
1024
1025   cloneCommonBlocks(F);
1026
1027   if (!DisableDemotion)
1028     demotePHIsOnFunclets(F);
1029
1030   if (!DisableCleanups) {
1031     DEBUG(verifyFunction(F));
1032     removeImplausibleInstructions(F);
1033
1034     DEBUG(verifyFunction(F));
1035     cleanupPreparedFunclets(F);
1036   }
1037
1038   DEBUG(verifyPreparedFunclets(F));
1039   // Recolor the CFG to verify that all is well.
1040   DEBUG(colorFunclets(F));
1041   DEBUG(verifyPreparedFunclets(F));
1042
1043   BlockColors.clear();
1044   FuncletBlocks.clear();
1045
1046   return true;
1047 }
1048
1049 // TODO: Share loads when one use dominates another, or when a catchpad exit
1050 // dominates uses (needs dominators).
1051 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1052   BasicBlock *PHIBlock = PN->getParent();
1053   AllocaInst *SpillSlot = nullptr;
1054   Instruction *EHPad = PHIBlock->getFirstNonPHI();
1055
1056   if (!isa<TerminatorInst>(EHPad)) {
1057     // If the EHPad isn't a terminator, then we can insert a load in this block
1058     // that will dominate all uses.
1059     SpillSlot = new AllocaInst(PN->getType(), nullptr,
1060                                Twine(PN->getName(), ".wineh.spillslot"),
1061                                &F.getEntryBlock().front());
1062     Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
1063                             &*PHIBlock->getFirstInsertionPt());
1064     PN->replaceAllUsesWith(V);
1065     return SpillSlot;
1066   }
1067
1068   // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
1069   // loads of the slot before every use.
1070   DenseMap<BasicBlock *, Value *> Loads;
1071   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1072        UI != UE;) {
1073     Use &U = *UI++;
1074     auto *UsingInst = cast<Instruction>(U.getUser());
1075     if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
1076       // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
1077       // stores for it separately.
1078       continue;
1079     }
1080     replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1081   }
1082   return SpillSlot;
1083 }
1084
1085 // TODO: improve store placement.  Inserting at def is probably good, but need
1086 // to be careful not to introduce interfering stores (needs liveness analysis).
1087 // TODO: identify related phi nodes that can share spill slots, and share them
1088 // (also needs liveness).
1089 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1090                                    AllocaInst *SpillSlot) {
1091   // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1092   // stored to the spill slot by the end of the given Block.
1093   SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1094
1095   Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1096
1097   while (!Worklist.empty()) {
1098     BasicBlock *EHBlock;
1099     Value *InVal;
1100     std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1101
1102     PHINode *PN = dyn_cast<PHINode>(InVal);
1103     if (PN && PN->getParent() == EHBlock) {
1104       // The value is defined by another PHI we need to remove, with no room to
1105       // insert a store after the PHI, so each predecessor needs to store its
1106       // incoming value.
1107       for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1108         Value *PredVal = PN->getIncomingValue(i);
1109
1110         // Undef can safely be skipped.
1111         if (isa<UndefValue>(PredVal))
1112           continue;
1113
1114         insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1115       }
1116     } else {
1117       // We need to store InVal, which dominates EHBlock, but can't put a store
1118       // in EHBlock, so need to put stores in each predecessor.
1119       for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1120         insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1121       }
1122     }
1123   }
1124 }
1125
1126 void WinEHPrepare::insertPHIStore(
1127     BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1128     SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1129
1130   if (PredBlock->isEHPad() &&
1131       isa<TerminatorInst>(PredBlock->getFirstNonPHI())) {
1132     // Pred is unsplittable, so we need to queue it on the worklist.
1133     Worklist.push_back({PredBlock, PredVal});
1134     return;
1135   }
1136
1137   // Otherwise, insert the store at the end of the basic block.
1138   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1139 }
1140
1141 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1142                                       DenseMap<BasicBlock *, Value *> &Loads,
1143                                       Function &F) {
1144   // Lazilly create the spill slot.
1145   if (!SpillSlot)
1146     SpillSlot = new AllocaInst(V->getType(), nullptr,
1147                                Twine(V->getName(), ".wineh.spillslot"),
1148                                &F.getEntryBlock().front());
1149
1150   auto *UsingInst = cast<Instruction>(U.getUser());
1151   if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1152     // If this is a PHI node, we can't insert a load of the value before
1153     // the use.  Instead insert the load in the predecessor block
1154     // corresponding to the incoming value.
1155     //
1156     // Note that if there are multiple edges from a basic block to this
1157     // PHI node that we cannot have multiple loads.  The problem is that
1158     // the resulting PHI node will have multiple values (from each load)
1159     // coming in from the same block, which is illegal SSA form.
1160     // For this reason, we keep track of and reuse loads we insert.
1161     BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1162     if (auto *CatchRet =
1163             dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1164       // Putting a load above a catchret and use on the phi would still leave
1165       // a cross-funclet def/use.  We need to split the edge, change the
1166       // catchret to target the new block, and put the load there.
1167       BasicBlock *PHIBlock = UsingInst->getParent();
1168       BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1169       // SplitEdge gives us:
1170       //   IncomingBlock:
1171       //     ...
1172       //     br label %NewBlock
1173       //   NewBlock:
1174       //     catchret label %PHIBlock
1175       // But we need:
1176       //   IncomingBlock:
1177       //     ...
1178       //     catchret label %NewBlock
1179       //   NewBlock:
1180       //     br label %PHIBlock
1181       // So move the terminators to each others' blocks and swap their
1182       // successors.
1183       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1184       Goto->removeFromParent();
1185       CatchRet->removeFromParent();
1186       IncomingBlock->getInstList().push_back(CatchRet);
1187       NewBlock->getInstList().push_back(Goto);
1188       Goto->setSuccessor(0, PHIBlock);
1189       CatchRet->setSuccessor(NewBlock);
1190       // Update the color mapping for the newly split edge.
1191       ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1192       BlockColors[NewBlock] = ColorsForPHIBlock;
1193       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1194         FuncletBlocks[FuncletPad].push_back(NewBlock);
1195       // Treat the new block as incoming for load insertion.
1196       IncomingBlock = NewBlock;
1197     }
1198     Value *&Load = Loads[IncomingBlock];
1199     // Insert the load into the predecessor block
1200     if (!Load)
1201       Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1202                           /*Volatile=*/false, IncomingBlock->getTerminator());
1203
1204     U.set(Load);
1205   } else {
1206     // Reload right before the old use.
1207     auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1208                               /*Volatile=*/false, UsingInst);
1209     U.set(Load);
1210   }
1211 }
1212
1213 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1214                                       MCSymbol *InvokeBegin,
1215                                       MCSymbol *InvokeEnd) {
1216   assert(InvokeStateMap.count(II) &&
1217          "should get invoke with precomputed state");
1218   LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);
1219 }
1220
1221 WinEHFuncInfo::WinEHFuncInfo() {}