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