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

Generated by: LCOV version 1.13