LCOV - code coverage report
Current view: top level - lib/CodeGen - WinEHPrepare.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 413 428 96.5 %
Date: 2018-06-17 00:07:59 Functions: 34 35 97.1 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13