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