lib/CodeGen/WinEHPrepare.cpp

   1 //===-- WinEHPrepare - Prepare exception handling for code generation ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass lowers LLVM IR exception handling into something closer to what the
  11 // backend wants. It snifs the personality function to see which kind of
  12 // preparation is necessary. If the personality function uses the Itanium LSDA,
  13 // this pass delegates to the DWARF EH preparation pass.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/CodeGen/Passes.h"
  18 #include "llvm/ADT/MapVector.h"
  19 #include "llvm/ADT/STLExtras.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/ADT/TinyPtrVector.h"
  22 #include "llvm/Analysis/LibCallSemantics.h"
  23 #include "llvm/CodeGen/WinEHFuncInfo.h"
  24 #include "llvm/IR/Dominators.h"
  25 #include "llvm/IR/Function.h"
  26 #include "llvm/IR/IRBuilder.h"
  27 #include "llvm/IR/Instructions.h"
  28 #include "llvm/IR/IntrinsicInst.h"
  29 #include "llvm/IR/Module.h"
  30 #include "llvm/IR/PatternMatch.h"
  31 #include "llvm/Pass.h"
  32 #include "llvm/Support/CommandLine.h"
  33 #include "llvm/Support/Debug.h"
  34 #include "llvm/Support/raw_ostream.h"
  35 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  36 #include "llvm/Transforms/Utils/Cloning.h"
  37 #include "llvm/Transforms/Utils/Local.h"
  38 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
  39 #include <memory>
  40
  41 using namespace llvm;
  42 using namespace llvm::PatternMatch;
  43
  44 #define DEBUG_TYPE "winehprepare"
  45
  46 namespace {
  47
  48 // This map is used to model frame variable usage during outlining, to
  49 // construct a structure type to hold the frame variables in a frame
  50 // allocation block, and to remap the frame variable allocas (including
  51 // spill locations as needed) to GEPs that get the variable from the
  52 // frame allocation structure.
  53 typedef MapVector<Value *, TinyPtrVector<AllocaInst *>> FrameVarInfoMap;
  54
  55 // TinyPtrVector cannot hold nullptr, so we need our own sentinel that isn't
  56 // quite null.
  57 AllocaInst *getCatchObjectSentinel() {
  58   return static_cast<AllocaInst *>(nullptr) + 1;
  59 }
  60
  61 typedef SmallSet<BasicBlock *, 4> VisitedBlockSet;
  62
  63 class LandingPadActions;
  64 class LandingPadMap;
  65
  66 typedef DenseMap<const BasicBlock *, CatchHandler *> CatchHandlerMapTy;
  67 typedef DenseMap<const BasicBlock *, CleanupHandler *> CleanupHandlerMapTy;
  68
  69 class WinEHPrepare : public FunctionPass {
  70 public:
  71   static char ID; // Pass identification, replacement for typeid.
  72   WinEHPrepare(const TargetMachine *TM = nullptr)
  73       : FunctionPass(ID), DT(nullptr) {}
  74
  75   bool runOnFunction(Function &Fn) override;
  76
  77   bool doFinalization(Module &M) override;
  78
  79   void getAnalysisUsage(AnalysisUsage &AU) const override;
  80
  81   const char *getPassName() const override {
  82     return "Windows exception handling preparation";
  83   }
  84
  85 private:
  86   bool prepareExceptionHandlers(Function &F,
  87                                 SmallVectorImpl<LandingPadInst *> &LPads);
  88   void promoteLandingPadValues(LandingPadInst *LPad);
  89   void completeNestedLandingPad(Function *ParentFn,
  90                                 LandingPadInst *OutlinedLPad,
  91                                 const LandingPadInst *OriginalLPad,
  92                                 FrameVarInfoMap &VarInfo);
  93   bool outlineHandler(ActionHandler *Action, Function *SrcFn,
  94                       LandingPadInst *LPad, BasicBlock *StartBB,
  95                       FrameVarInfoMap &VarInfo);
  96   void addStubInvokeToHandlerIfNeeded(Function *Handler, Value *PersonalityFn);
  97
  98   void mapLandingPadBlocks(LandingPadInst *LPad, LandingPadActions &Actions);
  99   CatchHandler *findCatchHandler(BasicBlock *BB, BasicBlock *&NextBB,
 100                                  VisitedBlockSet &VisitedBlocks);
 101   void findCleanupHandlers(LandingPadActions &Actions, BasicBlock *StartBB,
 102                            BasicBlock *EndBB);
 103
 104   void processSEHCatchHandler(CatchHandler *Handler, BasicBlock *StartBB);
 105
 106   // All fields are reset by runOnFunction.
 107   DominatorTree *DT;
 108   EHPersonality Personality;
 109   CatchHandlerMapTy CatchHandlerMap;
 110   CleanupHandlerMapTy CleanupHandlerMap;
 111   DenseMap<const LandingPadInst *, LandingPadMap> LPadMaps;
 112
 113   // This maps landing pad instructions found in outlined handlers to
 114   // the landing pad instruction in the parent function from which they
 115   // were cloned.  The cloned/nested landing pad is used as the key
 116   // because the landing pad may be cloned into multiple handlers.
 117   // This map will be used to add the llvm.eh.actions call to the nested
 118   // landing pads after all handlers have been outlined.
 119   DenseMap<LandingPadInst *, const LandingPadInst *> NestedLPtoOriginalLP;
 120
 121   // This maps blocks in the parent function which are destinations of
 122   // catch handlers to cloned blocks in (other) outlined handlers. This
 123   // handles the case where a nested landing pads has a catch handler that
 124   // returns to a handler function rather than the parent function.
 125   // The original block is used as the key here because there should only
 126   // ever be one handler function from which the cloned block is not pruned.
 127   // The original block will be pruned from the parent function after all
 128   // handlers have been outlined.  This map will be used to adjust the
 129   // return instructions of handlers which return to the block that was
 130   // outlined into a handler.  This is done after all handlers have been
 131   // outlined but before the outlined code is pruned from the parent function.
 132   DenseMap<const BasicBlock *, BasicBlock *> LPadTargetBlocks;
 133 };
 134
 135 class WinEHFrameVariableMaterializer : public ValueMaterializer {
 136 public:
 137   WinEHFrameVariableMaterializer(Function *OutlinedFn,
 138                                  FrameVarInfoMap &FrameVarInfo);
 139   ~WinEHFrameVariableMaterializer() override {}
 140
 141   Value *materializeValueFor(Value *V) override;
 142
 143   void escapeCatchObject(Value *V);
 144
 145 private:
 146   FrameVarInfoMap &FrameVarInfo;
 147   IRBuilder<> Builder;
 148 };
 149
 150 class LandingPadMap {
 151 public:
 152   LandingPadMap() : OriginLPad(nullptr) {}
 153   void mapLandingPad(const LandingPadInst *LPad);
 154
 155   bool isInitialized() { return OriginLPad != nullptr; }
 156
 157   bool isOriginLandingPadBlock(const BasicBlock *BB) const;
 158   bool isLandingPadSpecificInst(const Instruction *Inst) const;
 159
 160   void remapEHValues(ValueToValueMapTy &VMap, Value *EHPtrValue,
 161                      Value *SelectorValue) const;
 162
 163 private:
 164   const LandingPadInst *OriginLPad;
 165   // We will normally only see one of each of these instructions, but
 166   // if more than one occurs for some reason we can handle that.
 167   TinyPtrVector<const ExtractValueInst *> ExtractedEHPtrs;
 168   TinyPtrVector<const ExtractValueInst *> ExtractedSelectors;
 169 };
 170
 171 class WinEHCloningDirectorBase : public CloningDirector {
 172 public:
 173   WinEHCloningDirectorBase(Function *HandlerFn, FrameVarInfoMap &VarInfo,
 174                            LandingPadMap &LPadMap)
 175       : Materializer(HandlerFn, VarInfo),
 176         SelectorIDType(Type::getInt32Ty(HandlerFn->getContext())),
 177         Int8PtrType(Type::getInt8PtrTy(HandlerFn->getContext())),
 178         LPadMap(LPadMap) {}
 179
 180   CloningAction handleInstruction(ValueToValueMapTy &VMap,
 181                                   const Instruction *Inst,
 182                                   BasicBlock *NewBB) override;
 183
 184   virtual CloningAction handleBeginCatch(ValueToValueMapTy &VMap,
 185                                          const Instruction *Inst,
 186                                          BasicBlock *NewBB) = 0;
 187   virtual CloningAction handleEndCatch(ValueToValueMapTy &VMap,
 188                                        const Instruction *Inst,
 189                                        BasicBlock *NewBB) = 0;
 190   virtual CloningAction handleTypeIdFor(ValueToValueMapTy &VMap,
 191                                         const Instruction *Inst,
 192                                         BasicBlock *NewBB) = 0;
 193   virtual CloningAction handleInvoke(ValueToValueMapTy &VMap,
 194                                      const InvokeInst *Invoke,
 195                                      BasicBlock *NewBB) = 0;
 196   virtual CloningAction handleResume(ValueToValueMapTy &VMap,
 197                                      const ResumeInst *Resume,
 198                                      BasicBlock *NewBB) = 0;
 199   virtual CloningAction handleCompare(ValueToValueMapTy &VMap,
 200                                       const CmpInst *Compare,
 201                                       BasicBlock *NewBB) = 0;
 202   virtual CloningAction handleLandingPad(ValueToValueMapTy &VMap,
 203                                          const LandingPadInst *LPad,
 204                                          BasicBlock *NewBB) = 0;
 205
 206   ValueMaterializer *getValueMaterializer() override { return &Materializer; }
 207
 208 protected:
 209   WinEHFrameVariableMaterializer Materializer;
 210   Type *SelectorIDType;
 211   Type *Int8PtrType;
 212   LandingPadMap &LPadMap;
 213 };
 214
 215 class WinEHCatchDirector : public WinEHCloningDirectorBase {
 216 public:
 217   WinEHCatchDirector(
 218       Function *CatchFn, Value *Selector, FrameVarInfoMap &VarInfo,
 219       LandingPadMap &LPadMap,
 220       DenseMap<LandingPadInst *, const LandingPadInst *> &NestedLPads)
 221       : WinEHCloningDirectorBase(CatchFn, VarInfo, LPadMap),
 222         CurrentSelector(Selector->stripPointerCasts()),
 223         ExceptionObjectVar(nullptr), NestedLPtoOriginalLP(NestedLPads) {}
 224
 225   CloningAction handleBeginCatch(ValueToValueMapTy &VMap,
 226                                  const Instruction *Inst,
 227                                  BasicBlock *NewBB) override;
 228   CloningAction handleEndCatch(ValueToValueMapTy &VMap, const Instruction *Inst,
 229                                BasicBlock *NewBB) override;
 230   CloningAction handleTypeIdFor(ValueToValueMapTy &VMap,
 231                                 const Instruction *Inst,
 232                                 BasicBlock *NewBB) override;
 233   CloningAction handleInvoke(ValueToValueMapTy &VMap, const InvokeInst *Invoke,
 234                              BasicBlock *NewBB) override;
 235   CloningAction handleResume(ValueToValueMapTy &VMap, const ResumeInst *Resume,
 236                              BasicBlock *NewBB) override;
 237   CloningAction handleCompare(ValueToValueMapTy &VMap,
 238                               const CmpInst *Compare, BasicBlock *NewBB) override;
 239   CloningAction handleLandingPad(ValueToValueMapTy &VMap,
 240                                  const LandingPadInst *LPad,
 241                                  BasicBlock *NewBB) override;
 242
 243   Value *getExceptionVar() { return ExceptionObjectVar; }
 244   TinyPtrVector<BasicBlock *> &getReturnTargets() { return ReturnTargets; }
 245
 246 private:
 247   Value *CurrentSelector;
 248
 249   Value *ExceptionObjectVar;
 250   TinyPtrVector<BasicBlock *> ReturnTargets;
 251
 252   // This will be a reference to the field of the same name in the WinEHPrepare
 253   // object which instantiates this WinEHCatchDirector object.
 254   DenseMap<LandingPadInst *, const LandingPadInst *> &NestedLPtoOriginalLP;
 255 };
 256
 257 class WinEHCleanupDirector : public WinEHCloningDirectorBase {
 258 public:
 259   WinEHCleanupDirector(Function *CleanupFn, FrameVarInfoMap &VarInfo,
 260                        LandingPadMap &LPadMap)
 261       : WinEHCloningDirectorBase(CleanupFn, VarInfo, LPadMap) {}
 262
 263   CloningAction handleBeginCatch(ValueToValueMapTy &VMap,
 264                                  const Instruction *Inst,
 265                                  BasicBlock *NewBB) override;
 266   CloningAction handleEndCatch(ValueToValueMapTy &VMap, const Instruction *Inst,
 267                                BasicBlock *NewBB) override;
 268   CloningAction handleTypeIdFor(ValueToValueMapTy &VMap,
 269                                 const Instruction *Inst,
 270                                 BasicBlock *NewBB) override;
 271   CloningAction handleInvoke(ValueToValueMapTy &VMap, const InvokeInst *Invoke,
 272                              BasicBlock *NewBB) override;
 273   CloningAction handleResume(ValueToValueMapTy &VMap, const ResumeInst *Resume,
 274                              BasicBlock *NewBB) override;
 275   CloningAction handleCompare(ValueToValueMapTy &VMap,
 276                               const CmpInst *Compare, BasicBlock *NewBB) override;
 277   CloningAction handleLandingPad(ValueToValueMapTy &VMap,
 278                                  const LandingPadInst *LPad,
 279                                  BasicBlock *NewBB) override;
 280 };
 281
 282 class LandingPadActions {
 283 public:
 284   LandingPadActions() : HasCleanupHandlers(false) {}
 285
 286   void insertCatchHandler(CatchHandler *Action) { Actions.push_back(Action); }
 287   void insertCleanupHandler(CleanupHandler *Action) {
 288     Actions.push_back(Action);
 289     HasCleanupHandlers = true;
 290   }
 291
 292   bool includesCleanup() const { return HasCleanupHandlers; }
 293
 294   SmallVectorImpl<ActionHandler *> &actions() { return Actions; }
 295   SmallVectorImpl<ActionHandler *>::iterator begin() { return Actions.begin(); }
 296   SmallVectorImpl<ActionHandler *>::iterator end() { return Actions.end(); }
 297
 298 private:
 299   // Note that this class does not own the ActionHandler objects in this vector.
 300   // The ActionHandlers are owned by the CatchHandlerMap and CleanupHandlerMap
 301   // in the WinEHPrepare class.
 302   SmallVector<ActionHandler *, 4> Actions;
 303   bool HasCleanupHandlers;
 304 };
 305
 306 } // end anonymous namespace
 307
 308 char WinEHPrepare::ID = 0;
 309 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
 310                    false, false)
 311
 312 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
 313   return new WinEHPrepare(TM);
 314 }
 315
 316 // FIXME: Remove this once the backend can handle the prepared IR.
 317 static cl::opt<bool>
 318     SEHPrepare("sehprepare", cl::Hidden,
 319                cl::desc("Prepare functions with SEH personalities"));
 320
 321 bool WinEHPrepare::runOnFunction(Function &Fn) {
 322   SmallVector<LandingPadInst *, 4> LPads;
 323   SmallVector<ResumeInst *, 4> Resumes;
 324   for (BasicBlock &BB : Fn) {
 325     if (auto *LP = BB.getLandingPadInst())
 326       LPads.push_back(LP);
 327     if (auto *Resume = dyn_cast<ResumeInst>(BB.getTerminator()))
 328       Resumes.push_back(Resume);
 329   }
 330
 331   // No need to prepare functions that lack landing pads.
 332   if (LPads.empty())
 333     return false;
 334
 335   // Classify the personality to see what kind of preparation we need.
 336   Personality = classifyEHPersonality(LPads.back()->getPersonalityFn());
 337
 338   // Do nothing if this is not an MSVC personality.
 339   if (!isMSVCEHPersonality(Personality))
 340     return false;
 341
 342   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 343
 344   if (isAsynchronousEHPersonality(Personality) && !SEHPrepare) {
 345     // Replace all resume instructions with unreachable.
 346     // FIXME: Remove this once the backend can handle the prepared IR.
 347     for (ResumeInst *Resume : Resumes) {
 348       IRBuilder<>(Resume).CreateUnreachable();
 349       Resume->eraseFromParent();
 350     }
 351     return true;
 352   }
 353
 354   // If there were any landing pads, prepareExceptionHandlers will make changes.
 355   prepareExceptionHandlers(Fn, LPads);
 356   return true;
 357 }
 358
 359 bool WinEHPrepare::doFinalization(Module &M) { return false; }
 360
 361 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
 362   AU.addRequired<DominatorTreeWrapperPass>();
 363 }
 364
 365 bool WinEHPrepare::prepareExceptionHandlers(
 366     Function &F, SmallVectorImpl<LandingPadInst *> &LPads) {
 367   // These containers are used to re-map frame variables that are used in
 368   // outlined catch and cleanup handlers.  They will be populated as the
 369   // handlers are outlined.
 370   FrameVarInfoMap FrameVarInfo;
 371
 372   bool HandlersOutlined = false;
 373
 374   Module *M = F.getParent();
 375   LLVMContext &Context = M->getContext();
 376
 377   // Create a new function to receive the handler contents.
 378   PointerType *Int8PtrType = Type::getInt8PtrTy(Context);
 379   Type *Int32Type = Type::getInt32Ty(Context);
 380   Function *ActionIntrin = Intrinsic::getDeclaration(M, Intrinsic::eh_actions);
 381
 382   for (LandingPadInst *LPad : LPads) {
 383     // Look for evidence that this landingpad has already been processed.
 384     bool LPadHasActionList = false;
 385     BasicBlock *LPadBB = LPad->getParent();
 386     for (Instruction &Inst : *LPadBB) {
 387       if (auto *IntrinCall = dyn_cast<IntrinsicInst>(&Inst)) {
 388         if (IntrinCall->getIntrinsicID() == Intrinsic::eh_actions) {
 389           LPadHasActionList = true;
 390           break;
 391         }
 392       }
 393       // FIXME: This is here to help with the development of nested landing pad
 394       //        outlining.  It should be removed when that is finished.
 395       if (isa<UnreachableInst>(Inst)) {
 396         LPadHasActionList = true;
 397         break;
 398       }
 399     }
 400
 401     // If we've already outlined the handlers for this landingpad,
 402     // there's nothing more to do here.
 403     if (LPadHasActionList)
 404       continue;
 405
 406     // If either of the values in the aggregate returned by the landing pad is
 407     // extracted and stored to memory, promote the stored value to a register.
 408     promoteLandingPadValues(LPad);
 409
 410     LandingPadActions Actions;
 411     mapLandingPadBlocks(LPad, Actions);
 412
 413     HandlersOutlined |= !Actions.actions().empty();
 414     for (ActionHandler *Action : Actions) {
 415       if (Action->hasBeenProcessed())
 416         continue;
 417       BasicBlock *StartBB = Action->getStartBlock();
 418
 419       // SEH doesn't do any outlining for catches. Instead, pass the handler
 420       // basic block addr to llvm.eh.actions and list the block as a return
 421       // target.
 422       if (isAsynchronousEHPersonality(Personality)) {
 423         if (auto *CatchAction = dyn_cast<CatchHandler>(Action)) {
 424           processSEHCatchHandler(CatchAction, StartBB);
 425           continue;
 426         }
 427       }
 428
 429       outlineHandler(Action, &F, LPad, StartBB, FrameVarInfo);
 430     }
 431
 432     // Replace the landing pad with a new llvm.eh.action based landing pad.
 433     BasicBlock *NewLPadBB = BasicBlock::Create(Context, "lpad", &F, LPadBB);
 434     assert(!isa<PHINode>(LPadBB->begin()));
 435     auto *NewLPad = cast<LandingPadInst>(LPad->clone());
 436     NewLPadBB->getInstList().push_back(NewLPad);
 437     while (!pred_empty(LPadBB)) {
 438       auto *pred = *pred_begin(LPadBB);
 439       InvokeInst *Invoke = cast<InvokeInst>(pred->getTerminator());
 440       Invoke->setUnwindDest(NewLPadBB);
 441     }
 442
 443     // If anyone is still using the old landingpad value, just give them undef
 444     // instead. The eh pointer and selector values are not real.
 445     LPad->replaceAllUsesWith(UndefValue::get(LPad->getType()));
 446
 447     // Replace the mapping of any nested landing pad that previously mapped
 448     // to this landing pad with a referenced to the cloned version.
 449     for (auto &LPadPair : NestedLPtoOriginalLP) {
 450       const LandingPadInst *OriginalLPad = LPadPair.second;
 451       if (OriginalLPad == LPad) {
 452         LPadPair.second = NewLPad;
 453       }
 454     }
 455
 456     // Replace uses of the old lpad in phis with this block and delete the old
 457     // block.
 458     LPadBB->replaceSuccessorsPhiUsesWith(NewLPadBB);
 459     LPadBB->getTerminator()->eraseFromParent();
 460     new UnreachableInst(LPadBB->getContext(), LPadBB);
 461
 462     // Add a call to describe the actions for this landing pad.
 463     std::vector<Value *> ActionArgs;
 464     for (ActionHandler *Action : Actions) {
 465       // Action codes from docs are: 0 cleanup, 1 catch.
 466       if (auto *CatchAction = dyn_cast<CatchHandler>(Action)) {
 467         ActionArgs.push_back(ConstantInt::get(Int32Type, 1));
 468         ActionArgs.push_back(CatchAction->getSelector());
 469         // Find the frame escape index of the exception object alloca in the
 470         // parent.
 471         int FrameEscapeIdx = -1;
 472         Value *EHObj = const_cast<Value *>(CatchAction->getExceptionVar());
 473         if (EHObj && !isa<ConstantPointerNull>(EHObj)) {
 474           auto I = FrameVarInfo.find(EHObj);
 475           assert(I != FrameVarInfo.end() &&
 476                  "failed to map llvm.eh.begincatch var");
 477           FrameEscapeIdx = std::distance(FrameVarInfo.begin(), I);
 478         }
 479         ActionArgs.push_back(ConstantInt::get(Int32Type, FrameEscapeIdx));
 480       } else {
 481         ActionArgs.push_back(ConstantInt::get(Int32Type, 0));
 482       }
 483       ActionArgs.push_back(Action->getHandlerBlockOrFunc());
 484     }
 485     CallInst *Recover =
 486         CallInst::Create(ActionIntrin, ActionArgs, "recover", NewLPadBB);
 487
 488     // Add an indirect branch listing possible successors of the catch handlers.
 489     IndirectBrInst *Branch = IndirectBrInst::Create(Recover, 0, NewLPadBB);
 490     for (ActionHandler *Action : Actions) {
 491       if (auto *CatchAction = dyn_cast<CatchHandler>(Action)) {
 492         for (auto *Target : CatchAction->getReturnTargets()) {
 493           Branch->addDestination(Target);
 494         }
 495       }
 496     }
 497   } // End for each landingpad
 498
 499   // If nothing got outlined, there is no more processing to be done.
 500   if (!HandlersOutlined)
 501     return false;
 502
 503   // Replace any nested landing pad stubs with the correct action handler.
 504   // This must be done before we remove unreachable blocks because it
 505   // cleans up references to outlined blocks that will be deleted.
 506   for (auto &LPadPair : NestedLPtoOriginalLP)
 507     completeNestedLandingPad(&F, LPadPair.first, LPadPair.second, FrameVarInfo);
 508   NestedLPtoOriginalLP.clear();
 509
 510   F.addFnAttr("wineh-parent", F.getName());
 511
 512   // Delete any blocks that were only used by handlers that were outlined above.
 513   removeUnreachableBlocks(F);
 514
 515   BasicBlock *Entry = &F.getEntryBlock();
 516   IRBuilder<> Builder(F.getParent()->getContext());
 517   Builder.SetInsertPoint(Entry->getFirstInsertionPt());
 518
 519   Function *FrameEscapeFn =
 520       Intrinsic::getDeclaration(M, Intrinsic::frameescape);
 521   Function *RecoverFrameFn =
 522       Intrinsic::getDeclaration(M, Intrinsic::framerecover);
 523
 524   // Finally, replace all of the temporary allocas for frame variables used in
 525   // the outlined handlers with calls to llvm.framerecover.
 526   BasicBlock::iterator II = Entry->getFirstInsertionPt();
 527   Instruction *AllocaInsertPt = II;
 528   SmallVector<Value *, 8> AllocasToEscape;
 529   for (auto &VarInfoEntry : FrameVarInfo) {
 530     Value *ParentVal = VarInfoEntry.first;
 531     TinyPtrVector<AllocaInst *> &Allocas = VarInfoEntry.second;
 532
 533     // If the mapped value isn't already an alloca, we need to spill it if it
 534     // is a computed value or copy it if it is an argument.
 535     AllocaInst *ParentAlloca = dyn_cast<AllocaInst>(ParentVal);
 536     if (!ParentAlloca) {
 537       if (auto *Arg = dyn_cast<Argument>(ParentVal)) {
 538         // Lower this argument to a copy and then demote that to the stack.
 539         // We can't just use the argument location because the handler needs
 540         // it to be in the frame allocation block.
 541         // Use 'select i8 true, %arg, undef' to simulate a 'no-op' instruction.
 542         Value *TrueValue = ConstantInt::getTrue(Context);
 543         Value *UndefValue = UndefValue::get(Arg->getType());
 544         Instruction *SI =
 545             SelectInst::Create(TrueValue, Arg, UndefValue,
 546                                Arg->getName() + ".tmp", AllocaInsertPt);
 547         Arg->replaceAllUsesWith(SI);
 548         // Reset the select operand, because it was clobbered by the RAUW above.
 549         SI->setOperand(1, Arg);
 550         ParentAlloca = DemoteRegToStack(*SI, true, SI);
 551       } else if (auto *PN = dyn_cast<PHINode>(ParentVal)) {
 552         ParentAlloca = DemotePHIToStack(PN, AllocaInsertPt);
 553       } else {
 554         Instruction *ParentInst = cast<Instruction>(ParentVal);
 555         // FIXME: This is a work-around to temporarily handle the case where an
 556         //        instruction that is only used in handlers is not sunk.
 557         //        Without uses, DemoteRegToStack would just eliminate the value.
 558         //        This will fail if ParentInst is an invoke.
 559         if (ParentInst->getNumUses() == 0) {
 560           BasicBlock::iterator InsertPt = ParentInst;
 561           ++InsertPt;
 562           ParentAlloca =
 563               new AllocaInst(ParentInst->getType(), nullptr,
 564                              ParentInst->getName() + ".reg2mem",
 565                              AllocaInsertPt);
 566           new StoreInst(ParentInst, ParentAlloca, InsertPt);
 567         } else {
 568           ParentAlloca = DemoteRegToStack(*ParentInst, true, AllocaInsertPt);
 569         }
 570       }
 571     }
 572
 573     // FIXME: We should try to sink unescaped allocas from the parent frame into
 574     // the child frame. If the alloca is escaped, we have to use the lifetime
 575     // markers to ensure that the alloca is only live within the child frame.
 576
 577     // Add this alloca to the list of things to escape.
 578     AllocasToEscape.push_back(ParentAlloca);
 579
 580     // Next replace all outlined allocas that are mapped to it.
 581     for (AllocaInst *TempAlloca : Allocas) {
 582       if (TempAlloca == getCatchObjectSentinel())
 583         continue; // Skip catch parameter sentinels.
 584       Function *HandlerFn = TempAlloca->getParent()->getParent();
 585       // FIXME: Sink this GEP into the blocks where it is used.
 586       Builder.SetInsertPoint(TempAlloca);
 587       Builder.SetCurrentDebugLocation(TempAlloca->getDebugLoc());
 588       Value *RecoverArgs[] = {
 589           Builder.CreateBitCast(&F, Int8PtrType, ""),
 590           &(HandlerFn->getArgumentList().back()),
 591           llvm::ConstantInt::get(Int32Type, AllocasToEscape.size() - 1)};
 592       Value *RecoveredAlloca = Builder.CreateCall(RecoverFrameFn, RecoverArgs);
 593       // Add a pointer bitcast if the alloca wasn't an i8.
 594       if (RecoveredAlloca->getType() != TempAlloca->getType()) {
 595         RecoveredAlloca->setName(Twine(TempAlloca->getName()) + ".i8");
 596         RecoveredAlloca =
 597             Builder.CreateBitCast(RecoveredAlloca, TempAlloca->getType());
 598       }
 599       TempAlloca->replaceAllUsesWith(RecoveredAlloca);
 600       TempAlloca->removeFromParent();
 601       RecoveredAlloca->takeName(TempAlloca);
 602       delete TempAlloca;
 603     }
 604   } // End for each FrameVarInfo entry.
 605
 606   // Insert 'call void (...)* @llvm.frameescape(...)' at the end of the entry
 607   // block.
 608   Builder.SetInsertPoint(&F.getEntryBlock().back());
 609   Builder.CreateCall(FrameEscapeFn, AllocasToEscape);
 610
 611   // Clean up the handler action maps we created for this function
 612   DeleteContainerSeconds(CatchHandlerMap);
 613   CatchHandlerMap.clear();
 614   DeleteContainerSeconds(CleanupHandlerMap);
 615   CleanupHandlerMap.clear();
 616
 617   return HandlersOutlined;
 618 }
 619
 620 void WinEHPrepare::promoteLandingPadValues(LandingPadInst *LPad) {
 621   // If the return values of the landing pad instruction are extracted and
 622   // stored to memory, we want to promote the store locations to reg values.
 623   SmallVector<AllocaInst *, 2> EHAllocas;
 624
 625   // The landingpad instruction returns an aggregate value.  Typically, its
 626   // value will be passed to a pair of extract value instructions and the
 627   // results of those extracts are often passed to store instructions.
 628   // In unoptimized code the stored value will often be loaded and then stored
 629   // again.
 630   for (auto *U : LPad->users()) {
 631     ExtractValueInst *Extract = dyn_cast<ExtractValueInst>(U);
 632     if (!Extract)
 633       continue;
 634
 635     for (auto *EU : Extract->users()) {
 636       if (auto *Store = dyn_cast<StoreInst>(EU)) {
 637         auto *AV = cast<AllocaInst>(Store->getPointerOperand());
 638         EHAllocas.push_back(AV);
 639       }
 640     }
 641   }
 642
 643   // We can't do this without a dominator tree.
 644   assert(DT);
 645
 646   if (!EHAllocas.empty()) {
 647     PromoteMemToReg(EHAllocas, *DT);
 648     EHAllocas.clear();
 649   }
 650
 651   // After promotion, some extracts may be trivially dead. Remove them.
 652   SmallVector<Value *, 4> Users(LPad->user_begin(), LPad->user_end());
 653   for (auto *U : Users)
 654     RecursivelyDeleteTriviallyDeadInstructions(U);
 655 }
 656
 657 void WinEHPrepare::completeNestedLandingPad(Function *ParentFn,
 658                                             LandingPadInst *OutlinedLPad,
 659                                             const LandingPadInst *OriginalLPad,
 660                                             FrameVarInfoMap &FrameVarInfo) {
 661   // Get the nested block and erase the unreachable instruction that was
 662   // temporarily inserted as its terminator.
 663   LLVMContext &Context = ParentFn->getContext();
 664   BasicBlock *OutlinedBB = OutlinedLPad->getParent();
 665   assert(isa<UnreachableInst>(OutlinedBB->getTerminator()));
 666   OutlinedBB->getTerminator()->eraseFromParent();
 667   // That should leave OutlinedLPad as the last instruction in its block.
 668   assert(&OutlinedBB->back() == OutlinedLPad);
 669
 670   // The original landing pad will have already had its action intrinsic
 671   // built by the outlining loop.  We need to clone that into the outlined
 672   // location.  It may also be necessary to add references to the exception
 673   // variables to the outlined handler in which this landing pad is nested
 674   // and remap return instructions in the nested handlers that should return
 675   // to an address in the outlined handler.
 676   Function *OutlinedHandlerFn = OutlinedBB->getParent();
 677   BasicBlock::const_iterator II = OriginalLPad;
 678   ++II;
 679   // The instruction after the landing pad should now be a call to eh.actions.
 680   const Instruction *Recover = II;
 681   assert(match(Recover, m_Intrinsic<Intrinsic::eh_actions>()));
 682   IntrinsicInst *EHActions = cast<IntrinsicInst>(Recover->clone());
 683
 684   // Remap the exception variables into the outlined function.
 685   WinEHFrameVariableMaterializer Materializer(OutlinedHandlerFn, FrameVarInfo);
 686   SmallVector<BlockAddress *, 4> ActionTargets;
 687   SmallVector<ActionHandler *, 4> ActionList;
 688   parseEHActions(EHActions, ActionList);
 689   for (auto *Action : ActionList) {
 690     auto *Catch = dyn_cast<CatchHandler>(Action);
 691     if (!Catch)
 692       continue;
 693     // The dyn_cast to function here selects C++ catch handlers and skips
 694     // SEH catch handlers.
 695     auto *Handler = dyn_cast<Function>(Catch->getHandlerBlockOrFunc());
 696     if (!Handler)
 697       continue;
 698     // Visit all the return instructions, looking for places that return
 699     // to a location within OutlinedHandlerFn.
 700     for (BasicBlock &NestedHandlerBB : *Handler) {
 701       auto *Ret = dyn_cast<ReturnInst>(NestedHandlerBB.getTerminator());
 702       if (!Ret)
 703         continue;
 704
 705       // Handler functions must always return a block address.
 706       BlockAddress *BA = cast<BlockAddress>(Ret->getReturnValue());
 707       // The original target will have been in the main parent function,
 708       // but if it is the address of a block that has been outlined, it
 709       // should be a block that was outlined into OutlinedHandlerFn.
 710       assert(BA->getFunction() == ParentFn);
 711
 712       // Ignore targets that aren't part of OutlinedHandlerFn.
 713       if (!LPadTargetBlocks.count(BA->getBasicBlock()))
 714         continue;
 715
 716       // If the return value is the address ofF a block that we
 717       // previously outlined into the parent handler function, replace
 718       // the return instruction and add the mapped target to the list
 719       // of possible return addresses.
 720       BasicBlock *MappedBB = LPadTargetBlocks[BA->getBasicBlock()];
 721       assert(MappedBB->getParent() == OutlinedHandlerFn);
 722       BlockAddress *NewBA = BlockAddress::get(OutlinedHandlerFn, MappedBB);
 723       Ret->eraseFromParent();
 724       ReturnInst::Create(Context, NewBA, &NestedHandlerBB);
 725       ActionTargets.push_back(NewBA);
 726     }
 727   }
 728   DeleteContainerPointers(ActionList);
 729   ActionList.clear();
 730   OutlinedBB->getInstList().push_back(EHActions);
 731
 732   // Insert an indirect branch into the outlined landing pad BB.
 733   IndirectBrInst *IBr = IndirectBrInst::Create(EHActions, 0, OutlinedBB);
 734   // Add the previously collected action targets.
 735   for (auto *Target : ActionTargets)
 736     IBr->addDestination(Target->getBasicBlock());
 737 }
 738
 739 // This function examines a block to determine whether the block ends with a
 740 // conditional branch to a catch handler based on a selector comparison.
 741 // This function is used both by the WinEHPrepare::findSelectorComparison() and
 742 // WinEHCleanupDirector::handleTypeIdFor().
 743 static bool isSelectorDispatch(BasicBlock *BB, BasicBlock *&CatchHandler,
 744                                Constant *&Selector, BasicBlock *&NextBB) {
 745   ICmpInst::Predicate Pred;
 746   BasicBlock *TBB, *FBB;
 747   Value *LHS, *RHS;
 748
 749   if (!match(BB->getTerminator(),
 750              m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), TBB, FBB)))
 751     return false;
 752
 753   if (!match(LHS,
 754              m_Intrinsic<Intrinsic::eh_typeid_for>(m_Constant(Selector))) &&
 755       !match(RHS, m_Intrinsic<Intrinsic::eh_typeid_for>(m_Constant(Selector))))
 756     return false;
 757
 758   if (Pred == CmpInst::ICMP_EQ) {
 759     CatchHandler = TBB;
 760     NextBB = FBB;
 761     return true;
 762   }
 763
 764   if (Pred == CmpInst::ICMP_NE) {
 765     CatchHandler = FBB;
 766     NextBB = TBB;
 767     return true;
 768   }
 769
 770   return false;
 771 }
 772
 773 static bool isCatchBlock(BasicBlock *BB) {
 774   for (BasicBlock::iterator II = BB->getFirstNonPHIOrDbg(), IE = BB->end();
 775        II != IE; ++II) {
 776     if (match(cast<Value>(II), m_Intrinsic<Intrinsic::eh_begincatch>()))
 777       return true;
 778   }
 779   return false;
 780 }
 781
 782 static BasicBlock *createStubLandingPad(Function *Handler,
 783                                         Value *PersonalityFn) {
 784   // FIXME: Finish this!
 785   LLVMContext &Context = Handler->getContext();
 786   BasicBlock *StubBB = BasicBlock::Create(Context, "stub");
 787   Handler->getBasicBlockList().push_back(StubBB);
 788   IRBuilder<> Builder(StubBB);
 789   LandingPadInst *LPad = Builder.CreateLandingPad(
 790       llvm::StructType::get(Type::getInt8PtrTy(Context),
 791                             Type::getInt32Ty(Context), nullptr),
 792       PersonalityFn, 0);
 793   LPad->setCleanup(true);
 794   Builder.CreateUnreachable();
 795   return StubBB;
 796 }
 797
 798 // Cycles through the blocks in an outlined handler function looking for an
 799 // invoke instruction and inserts an invoke of llvm.donothing with an empty
 800 // landing pad if none is found.  The code that generates the .xdata tables for
 801 // the handler needs at least one landing pad to identify the parent function's
 802 // personality.
 803 void WinEHPrepare::addStubInvokeToHandlerIfNeeded(Function *Handler,
 804                                                   Value *PersonalityFn) {
 805   ReturnInst *Ret = nullptr;
 806   for (BasicBlock &BB : *Handler) {
 807     TerminatorInst *Terminator = BB.getTerminator();
 808     // If we find an invoke, there is nothing to be done.
 809     auto *II = dyn_cast<InvokeInst>(Terminator);
 810     if (II)
 811       return;
 812     // If we've already recorded a return instruction, keep looking for invokes.
 813     if (Ret)
 814       continue;
 815     // If we haven't recorded a return instruction yet, try this terminator.
 816     Ret = dyn_cast<ReturnInst>(Terminator);
 817   }
 818
 819   // If we got this far, the handler contains no invokes.  We should have seen
 820   // at least one return.  We'll insert an invoke of llvm.donothing ahead of
 821   // that return.
 822   assert(Ret);
 823   BasicBlock *OldRetBB = Ret->getParent();
 824   BasicBlock *NewRetBB = SplitBlock(OldRetBB, Ret);
 825   // SplitBlock adds an unconditional branch instruction at the end of the
 826   // parent block.  We want to replace that with an invoke call, so we can
 827   // erase it now.
 828   OldRetBB->getTerminator()->eraseFromParent();
 829   BasicBlock *StubLandingPad = createStubLandingPad(Handler, PersonalityFn);
 830   Function *F =
 831       Intrinsic::getDeclaration(Handler->getParent(), Intrinsic::donothing);
 832   InvokeInst::Create(F, NewRetBB, StubLandingPad, None, "", OldRetBB);
 833 }
 834
 835 bool WinEHPrepare::outlineHandler(ActionHandler *Action, Function *SrcFn,
 836                                   LandingPadInst *LPad, BasicBlock *StartBB,
 837                                   FrameVarInfoMap &VarInfo) {
 838   Module *M = SrcFn->getParent();
 839   LLVMContext &Context = M->getContext();
 840
 841   // Create a new function to receive the handler contents.
 842   Type *Int8PtrType = Type::getInt8PtrTy(Context);
 843   std::vector<Type *> ArgTys;
 844   ArgTys.push_back(Int8PtrType);
 845   ArgTys.push_back(Int8PtrType);
 846   Function *Handler;
 847   if (Action->getType() == Catch) {
 848     FunctionType *FnType = FunctionType::get(Int8PtrType, ArgTys, false);
 849     Handler = Function::Create(FnType, GlobalVariable::InternalLinkage,
 850                                SrcFn->getName() + ".catch", M);
 851   } else {
 852     FunctionType *FnType =
 853         FunctionType::get(Type::getVoidTy(Context), ArgTys, false);
 854     Handler = Function::Create(FnType, GlobalVariable::InternalLinkage,
 855                                SrcFn->getName() + ".cleanup", M);
 856   }
 857
 858   Handler->addFnAttr("wineh-parent", SrcFn->getName());
 859
 860   // Generate a standard prolog to setup the frame recovery structure.
 861   IRBuilder<> Builder(Context);
 862   BasicBlock *Entry = BasicBlock::Create(Context, "entry");
 863   Handler->getBasicBlockList().push_front(Entry);
 864   Builder.SetInsertPoint(Entry);
 865   Builder.SetCurrentDebugLocation(LPad->getDebugLoc());
 866
 867   std::unique_ptr<WinEHCloningDirectorBase> Director;
 868
 869   ValueToValueMapTy VMap;
 870
 871   LandingPadMap &LPadMap = LPadMaps[LPad];
 872   if (!LPadMap.isInitialized())
 873     LPadMap.mapLandingPad(LPad);
 874   if (auto *CatchAction = dyn_cast<CatchHandler>(Action)) {
 875     Constant *Sel = CatchAction->getSelector();
 876     Director.reset(new WinEHCatchDirector(Handler, Sel, VarInfo, LPadMap,
 877                                           NestedLPtoOriginalLP));
 878     LPadMap.remapEHValues(VMap, UndefValue::get(Int8PtrType),
 879                           ConstantInt::get(Type::getInt32Ty(Context), 1));
 880   } else {
 881     Director.reset(new WinEHCleanupDirector(Handler, VarInfo, LPadMap));
 882     LPadMap.remapEHValues(VMap, UndefValue::get(Int8PtrType),
 883                           UndefValue::get(Type::getInt32Ty(Context)));
 884   }
 885
 886   SmallVector<ReturnInst *, 8> Returns;
 887   ClonedCodeInfo OutlinedFunctionInfo;
 888
 889   // If the start block contains PHI nodes, we need to map them.
 890   BasicBlock::iterator II = StartBB->begin();
 891   while (auto *PN = dyn_cast<PHINode>(II)) {
 892     bool Mapped = false;
 893     // Look for PHI values that we have already mapped (such as the selector).
 894     for (Value *Val : PN->incoming_values()) {
 895       if (VMap.count(Val)) {
 896         VMap[PN] = VMap[Val];
 897         Mapped = true;
 898       }
 899     }
 900     // If we didn't find a match for this value, map it as an undef.
 901     if (!Mapped) {
 902       VMap[PN] = UndefValue::get(PN->getType());
 903     }
 904     ++II;
 905   }
 906
 907   // Skip over PHIs and, if applicable, landingpad instructions.
 908   II = StartBB->getFirstInsertionPt();
 909
 910   CloneAndPruneIntoFromInst(Handler, SrcFn, II, VMap,
 911                             /*ModuleLevelChanges=*/false, Returns, "",
 912                             &OutlinedFunctionInfo, Director.get());
 913
 914   // Move all the instructions in the first cloned block into our entry block.
 915   BasicBlock *FirstClonedBB = std::next(Function::iterator(Entry));
 916   Entry->getInstList().splice(Entry->end(), FirstClonedBB->getInstList());
 917   FirstClonedBB->eraseFromParent();
 918
 919   // Make sure we can identify the handler's personality later.
 920   addStubInvokeToHandlerIfNeeded(Handler, LPad->getPersonalityFn());
 921
 922   if (auto *CatchAction = dyn_cast<CatchHandler>(Action)) {
 923     WinEHCatchDirector *CatchDirector =
 924         reinterpret_cast<WinEHCatchDirector *>(Director.get());
 925     CatchAction->setExceptionVar(CatchDirector->getExceptionVar());
 926     CatchAction->setReturnTargets(CatchDirector->getReturnTargets());
 927
 928     // Look for blocks that are not part of the landing pad that we just
 929     // outlined but terminate with a call to llvm.eh.endcatch and a
 930     // branch to a block that is in the handler we just outlined.
 931     // These blocks will be part of a nested landing pad that intends to
 932     // return to an address in this handler.  This case is best handled
 933     // after both landing pads have been outlined, so for now we'll just
 934     // save the association of the blocks in LPadTargetBlocks.  The
 935     // return instructions which are created from these branches will be
 936     // replaced after all landing pads have been outlined.
 937     for (const auto MapEntry : VMap) {
 938       // VMap maps all values and blocks that were just cloned, but dead
 939       // blocks which were pruned will map to nullptr.
 940       if (!isa<BasicBlock>(MapEntry.first) || MapEntry.second == nullptr)
 941         continue;
 942       const BasicBlock *MappedBB = cast<BasicBlock>(MapEntry.first);
 943       for (auto *Pred : predecessors(const_cast<BasicBlock *>(MappedBB))) {
 944         auto *Branch = dyn_cast<BranchInst>(Pred->getTerminator());
 945         if (!Branch || !Branch->isUnconditional() || Pred->size() <= 1)
 946           continue;
 947         BasicBlock::iterator II = const_cast<BranchInst *>(Branch);
 948         --II;
 949         if (match(cast<Value>(II), m_Intrinsic<Intrinsic::eh_endcatch>())) {
 950           // This would indicate that a nested landing pad wants to return
 951           // to a block that is outlined into two different handlers.
 952           assert(!LPadTargetBlocks.count(MappedBB));
 953           LPadTargetBlocks[MappedBB] = cast<BasicBlock>(MapEntry.second);
 954         }
 955       }
 956     }
 957   } // End if (CatchAction)
 958
 959   Action->setHandlerBlockOrFunc(Handler);
 960
 961   return true;
 962 }
 963
 964 /// This BB must end in a selector dispatch. All we need to do is pass the
 965 /// handler block to llvm.eh.actions and list it as a possible indirectbr
 966 /// target.
 967 void WinEHPrepare::processSEHCatchHandler(CatchHandler *CatchAction,
 968                                           BasicBlock *StartBB) {
 969   BasicBlock *HandlerBB;
 970   BasicBlock *NextBB;
 971   Constant *Selector;
 972   bool Res = isSelectorDispatch(StartBB, HandlerBB, Selector, NextBB);
 973   if (Res) {
 974     // If this was EH dispatch, this must be a conditional branch to the handler
 975     // block.
 976     // FIXME: Handle instructions in the dispatch block. Currently we drop them,
 977     // leading to crashes if some optimization hoists stuff here.
 978     assert(CatchAction->getSelector() && HandlerBB &&
 979            "expected catch EH dispatch");
 980   } else {
 981     // This must be a catch-all. Split the block after the landingpad.
 982     assert(CatchAction->getSelector()->isNullValue() && "expected catch-all");
 983     HandlerBB =
 984         StartBB->splitBasicBlock(StartBB->getFirstInsertionPt(), "catch.all");
 985   }
 986   CatchAction->setHandlerBlockOrFunc(BlockAddress::get(HandlerBB));
 987   TinyPtrVector<BasicBlock *> Targets(HandlerBB);
 988   CatchAction->setReturnTargets(Targets);
 989 }
 990
 991 void LandingPadMap::mapLandingPad(const LandingPadInst *LPad) {
 992   // Each instance of this class should only ever be used to map a single
 993   // landing pad.
 994   assert(OriginLPad == nullptr || OriginLPad == LPad);
 995
 996   // If the landing pad has already been mapped, there's nothing more to do.
 997   if (OriginLPad == LPad)
 998     return;
 999
1000   OriginLPad = LPad;
1001
1002   // The landingpad instruction returns an aggregate value.  Typically, its
1003   // value will be passed to a pair of extract value instructions and the
1004   // results of those extracts will have been promoted to reg values before
1005   // this routine is called.
1006   for (auto *U : LPad->users()) {
1007     const ExtractValueInst *Extract = dyn_cast<ExtractValueInst>(U);
1008     if (!Extract)
1009       continue;
1010     assert(Extract->getNumIndices() == 1 &&
1011            "Unexpected operation: extracting both landing pad values");
1012     unsigned int Idx = *(Extract->idx_begin());
1013     assert((Idx == 0 || Idx == 1) &&
1014            "Unexpected operation: extracting an unknown landing pad element");
1015     if (Idx == 0) {
1016       ExtractedEHPtrs.push_back(Extract);
1017     } else if (Idx == 1) {
1018       ExtractedSelectors.push_back(Extract);
1019     }
1020   }
1021 }
1022
1023 bool LandingPadMap::isOriginLandingPadBlock(const BasicBlock *BB) const {
1024   return BB->getLandingPadInst() == OriginLPad;
1025 }
1026
1027 bool LandingPadMap::isLandingPadSpecificInst(const Instruction *Inst) const {
1028   if (Inst == OriginLPad)
1029     return true;
1030   for (auto *Extract : ExtractedEHPtrs) {
1031     if (Inst == Extract)
1032       return true;
1033   }
1034   for (auto *Extract : ExtractedSelectors) {
1035     if (Inst == Extract)
1036       return true;
1037   }
1038   return false;
1039 }
1040
1041 void LandingPadMap::remapEHValues(ValueToValueMapTy &VMap, Value *EHPtrValue,
1042                                   Value *SelectorValue) const {
1043   // Remap all landing pad extract instructions to the specified values.
1044   for (auto *Extract : ExtractedEHPtrs)
1045     VMap[Extract] = EHPtrValue;
1046   for (auto *Extract : ExtractedSelectors)
1047     VMap[Extract] = SelectorValue;
1048 }
1049
1050 CloningDirector::CloningAction WinEHCloningDirectorBase::handleInstruction(
1051     ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) {
1052   // If this is one of the boilerplate landing pad instructions, skip it.
1053   // The instruction will have already been remapped in VMap.
1054   if (LPadMap.isLandingPadSpecificInst(Inst))
1055     return CloningDirector::SkipInstruction;
1056
1057   // Nested landing pads will be cloned as stubs, with just the
1058   // landingpad instruction and an unreachable instruction. When
1059   // all landingpads have been outlined, we'll replace this with the
1060   // llvm.eh.actions call and indirect branch created when the
1061   // landing pad was outlined.
1062   if (auto *LPad = dyn_cast<LandingPadInst>(Inst)) {
1063     return handleLandingPad(VMap, LPad, NewBB);
1064   }
1065
1066   if (auto *Invoke = dyn_cast<InvokeInst>(Inst))
1067     return handleInvoke(VMap, Invoke, NewBB);
1068
1069   if (auto *Resume = dyn_cast<ResumeInst>(Inst))
1070     return handleResume(VMap, Resume, NewBB);
1071
1072   if (auto *Cmp = dyn_cast<CmpInst>(Inst))
1073     return handleCompare(VMap, Cmp, NewBB);
1074
1075   if (match(Inst, m_Intrinsic<Intrinsic::eh_begincatch>()))
1076     return handleBeginCatch(VMap, Inst, NewBB);
1077   if (match(Inst, m_Intrinsic<Intrinsic::eh_endcatch>()))
1078     return handleEndCatch(VMap, Inst, NewBB);
1079   if (match(Inst, m_Intrinsic<Intrinsic::eh_typeid_for>()))
1080     return handleTypeIdFor(VMap, Inst, NewBB);
1081
1082   // Continue with the default cloning behavior.
1083   return CloningDirector::CloneInstruction;
1084 }
1085
1086 CloningDirector::CloningAction WinEHCatchDirector::handleLandingPad(
1087     ValueToValueMapTy &VMap, const LandingPadInst *LPad, BasicBlock *NewBB) {
1088   Instruction *NewInst = LPad->clone();
1089   if (LPad->hasName())
1090     NewInst->setName(LPad->getName());
1091   // Save this correlation for later processing.
1092   NestedLPtoOriginalLP[cast<LandingPadInst>(NewInst)] = LPad;
1093   VMap[LPad] = NewInst;
1094   BasicBlock::InstListType &InstList = NewBB->getInstList();
1095   InstList.push_back(NewInst);
1096   InstList.push_back(new UnreachableInst(NewBB->getContext()));
1097   return CloningDirector::StopCloningBB;
1098 }
1099
1100 CloningDirector::CloningAction WinEHCatchDirector::handleBeginCatch(
1101     ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) {
1102   // The argument to the call is some form of the first element of the
1103   // landingpad aggregate value, but that doesn't matter.  It isn't used
1104   // here.
1105   // The second argument is an outparameter where the exception object will be
1106   // stored. Typically the exception object is a scalar, but it can be an
1107   // aggregate when catching by value.
1108   // FIXME: Leave something behind to indicate where the exception object lives
1109   // for this handler. Should it be part of llvm.eh.actions?
1110   assert(ExceptionObjectVar == nullptr && "Multiple calls to "
1111                                           "llvm.eh.begincatch found while "
1112                                           "outlining catch handler.");
1113   ExceptionObjectVar = Inst->getOperand(1)->stripPointerCasts();
1114   if (isa<ConstantPointerNull>(ExceptionObjectVar))
1115     return CloningDirector::SkipInstruction;
1116   assert(cast<AllocaInst>(ExceptionObjectVar)->isStaticAlloca() &&
1117          "catch parameter is not static alloca");
1118   Materializer.escapeCatchObject(ExceptionObjectVar);
1119   return CloningDirector::SkipInstruction;
1120 }
1121
1122 CloningDirector::CloningAction
1123 WinEHCatchDirector::handleEndCatch(ValueToValueMapTy &VMap,
1124                                    const Instruction *Inst, BasicBlock *NewBB) {
1125   auto *IntrinCall = dyn_cast<IntrinsicInst>(Inst);
1126   // It might be interesting to track whether or not we are inside a catch
1127   // function, but that might make the algorithm more brittle than it needs
1128   // to be.
1129
1130   // The end catch call can occur in one of two places: either in a
1131   // landingpad block that is part of the catch handlers exception mechanism,
1132   // or at the end of the catch block.  However, a catch-all handler may call
1133   // end catch from the original landing pad.  If the call occurs in a nested
1134   // landing pad block, we must skip it and continue so that the landing pad
1135   // gets cloned.
1136   auto *ParentBB = IntrinCall->getParent();
1137   if (ParentBB->isLandingPad() && !LPadMap.isOriginLandingPadBlock(ParentBB))
1138     return CloningDirector::SkipInstruction;
1139
1140   // If an end catch occurs anywhere else we want to terminate the handler
1141   // with a return to the code that follows the endcatch call.  If the
1142   // next instruction is not an unconditional branch, we need to split the
1143   // block to provide a clear target for the return instruction.
1144   BasicBlock *ContinueBB;
1145   auto Next = std::next(BasicBlock::const_iterator(IntrinCall));
1146   const BranchInst *Branch = dyn_cast<BranchInst>(Next);
1147   if (!Branch || !Branch->isUnconditional()) {
1148     // We're interrupting the cloning process at this location, so the
1149     // const_cast we're doing here will not cause a problem.
1150     ContinueBB = SplitBlock(const_cast<BasicBlock *>(ParentBB),
1151                             const_cast<Instruction *>(cast<Instruction>(Next)));
1152   } else {
1153     ContinueBB = Branch->getSuccessor(0);
1154   }
1155
1156   ReturnInst::Create(NewBB->getContext(), BlockAddress::get(ContinueBB), NewBB);
1157   ReturnTargets.push_back(ContinueBB);
1158
1159   // We just added a terminator to the cloned block.
1160   // Tell the caller to stop processing the current basic block so that
1161   // the branch instruction will be skipped.
1162   return CloningDirector::StopCloningBB;
1163 }
1164
1165 CloningDirector::CloningAction WinEHCatchDirector::handleTypeIdFor(
1166     ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) {
1167   auto *IntrinCall = dyn_cast<IntrinsicInst>(Inst);
1168   Value *Selector = IntrinCall->getArgOperand(0)->stripPointerCasts();
1169   // This causes a replacement that will collapse the landing pad CFG based
1170   // on the filter function we intend to match.
1171   if (Selector == CurrentSelector)
1172     VMap[Inst] = ConstantInt::get(SelectorIDType, 1);
1173   else
1174     VMap[Inst] = ConstantInt::get(SelectorIDType, 0);
1175   // Tell the caller not to clone this instruction.
1176   return CloningDirector::SkipInstruction;
1177 }
1178
1179 CloningDirector::CloningAction
1180 WinEHCatchDirector::handleInvoke(ValueToValueMapTy &VMap,
1181                                  const InvokeInst *Invoke, BasicBlock *NewBB) {
1182   return CloningDirector::CloneInstruction;
1183 }
1184
1185 CloningDirector::CloningAction
1186 WinEHCatchDirector::handleResume(ValueToValueMapTy &VMap,
1187                                  const ResumeInst *Resume, BasicBlock *NewBB) {
1188   // Resume instructions shouldn't be reachable from catch handlers.
1189   // We still need to handle it, but it will be pruned.
1190   BasicBlock::InstListType &InstList = NewBB->getInstList();
1191   InstList.push_back(new UnreachableInst(NewBB->getContext()));
1192   return CloningDirector::StopCloningBB;
1193 }
1194
1195 CloningDirector::CloningAction
1196 WinEHCatchDirector::handleCompare(ValueToValueMapTy &VMap,
1197                                   const CmpInst *Compare, BasicBlock *NewBB) {
1198   const IntrinsicInst *IntrinCall = nullptr;
1199   if (match(Compare->getOperand(0), m_Intrinsic<Intrinsic::eh_typeid_for>())) {
1200     IntrinCall = dyn_cast<IntrinsicInst>(Compare->getOperand(0));
1201   } else if (match(Compare->getOperand(1), m_Intrinsic<Intrinsic::eh_typeid_for>())) {
1202     IntrinCall = dyn_cast<IntrinsicInst>(Compare->getOperand(1));
1203   }
1204   if (IntrinCall) {
1205     Value *Selector = IntrinCall->getArgOperand(0)->stripPointerCasts();
1206     // This causes a replacement that will collapse the landing pad CFG based
1207     // on the filter function we intend to match.
1208     if (Selector == CurrentSelector->stripPointerCasts()) {
1209       VMap[Compare] = ConstantInt::get(SelectorIDType, 1);
1210     }
1211     else {
1212       VMap[Compare] = ConstantInt::get(SelectorIDType, 0);
1213     }
1214     return CloningDirector::SkipInstruction;
1215   }
1216   return CloningDirector::CloneInstruction;
1217 }
1218
1219 CloningDirector::CloningAction WinEHCleanupDirector::handleLandingPad(
1220     ValueToValueMapTy &VMap, const LandingPadInst *LPad, BasicBlock *NewBB) {
1221   // The MS runtime will terminate the process if an exception occurs in a
1222   // cleanup handler, so we shouldn't encounter landing pads in the actual
1223   // cleanup code, but they may appear in catch blocks.  Depending on where
1224   // we started cloning we may see one, but it will get dropped during dead
1225   // block pruning.
1226   Instruction *NewInst = new UnreachableInst(NewBB->getContext());
1227   VMap[LPad] = NewInst;
1228   BasicBlock::InstListType &InstList = NewBB->getInstList();
1229   InstList.push_back(NewInst);
1230   return CloningDirector::StopCloningBB;
1231 }
1232
1233 CloningDirector::CloningAction WinEHCleanupDirector::handleBeginCatch(
1234     ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) {
1235   // Cleanup code may flow into catch blocks or the catch block may be part
1236   // of a branch that will be optimized away.  We'll insert a return
1237   // instruction now, but it may be pruned before the cloning process is
1238   // complete.
1239   ReturnInst::Create(NewBB->getContext(), nullptr, NewBB);
1240   return CloningDirector::StopCloningBB;
1241 }
1242
1243 CloningDirector::CloningAction WinEHCleanupDirector::handleEndCatch(
1244     ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) {
1245   // Cleanup handlers nested within catch handlers may begin with a call to
1246   // eh.endcatch.  We can just ignore that instruction.
1247   return CloningDirector::SkipInstruction;
1248 }
1249
1250 CloningDirector::CloningAction WinEHCleanupDirector::handleTypeIdFor(
1251     ValueToValueMapTy &VMap, const Instruction *Inst, BasicBlock *NewBB) {
1252   // If we encounter a selector comparison while cloning a cleanup handler,
1253   // we want to stop cloning immediately.  Anything after the dispatch
1254   // will be outlined into a different handler.
1255   BasicBlock *CatchHandler;
1256   Constant *Selector;
1257   BasicBlock *NextBB;
1258   if (isSelectorDispatch(const_cast<BasicBlock *>(Inst->getParent()),
1259                          CatchHandler, Selector, NextBB)) {
1260     ReturnInst::Create(NewBB->getContext(), nullptr, NewBB);
1261     return CloningDirector::StopCloningBB;
1262   }
1263   // If eg.typeid.for is called for any other reason, it can be ignored.
1264   VMap[Inst] = ConstantInt::get(SelectorIDType, 0);
1265   return CloningDirector::SkipInstruction;
1266 }
1267
1268 CloningDirector::CloningAction WinEHCleanupDirector::handleInvoke(
1269     ValueToValueMapTy &VMap, const InvokeInst *Invoke, BasicBlock *NewBB) {
1270   // All invokes in cleanup handlers can be replaced with calls.
1271   SmallVector<Value *, 16> CallArgs(Invoke->op_begin(), Invoke->op_end() - 3);
1272   // Insert a normal call instruction...
1273   CallInst *NewCall =
1274       CallInst::Create(const_cast<Value *>(Invoke->getCalledValue()), CallArgs,
1275                        Invoke->getName(), NewBB);
1276   NewCall->setCallingConv(Invoke->getCallingConv());
1277   NewCall->setAttributes(Invoke->getAttributes());
1278   NewCall->setDebugLoc(Invoke->getDebugLoc());
1279   VMap[Invoke] = NewCall;
1280
1281   // Remap the operands.
1282   llvm::RemapInstruction(NewCall, VMap, RF_None, nullptr, &Materializer);
1283
1284   // Insert an unconditional branch to the normal destination.
1285   BranchInst::Create(Invoke->getNormalDest(), NewBB);
1286
1287   // The unwind destination won't be cloned into the new function, so
1288   // we don't need to clean up its phi nodes.
1289
1290   // We just added a terminator to the cloned block.
1291   // Tell the caller to stop processing the current basic block.
1292   return CloningDirector::CloneSuccessors;
1293 }
1294
1295 CloningDirector::CloningAction WinEHCleanupDirector::handleResume(
1296     ValueToValueMapTy &VMap, const ResumeInst *Resume, BasicBlock *NewBB) {
1297   ReturnInst::Create(NewBB->getContext(), nullptr, NewBB);
1298
1299   // We just added a terminator to the cloned block.
1300   // Tell the caller to stop processing the current basic block so that
1301   // the branch instruction will be skipped.
1302   return CloningDirector::StopCloningBB;
1303 }
1304
1305 CloningDirector::CloningAction
1306 WinEHCleanupDirector::handleCompare(ValueToValueMapTy &VMap,
1307                                     const CmpInst *Compare, BasicBlock *NewBB) {
1308   if (match(Compare->getOperand(0), m_Intrinsic<Intrinsic::eh_typeid_for>()) ||
1309       match(Compare->getOperand(1), m_Intrinsic<Intrinsic::eh_typeid_for>())) {
1310     VMap[Compare] = ConstantInt::get(SelectorIDType, 1);
1311     return CloningDirector::SkipInstruction;
1312   }
1313   return CloningDirector::CloneInstruction;
1314
1315 }
1316
1317 WinEHFrameVariableMaterializer::WinEHFrameVariableMaterializer(
1318     Function *OutlinedFn, FrameVarInfoMap &FrameVarInfo)
1319     : FrameVarInfo(FrameVarInfo), Builder(OutlinedFn->getContext()) {
1320   BasicBlock *EntryBB = &OutlinedFn->getEntryBlock();
1321   Builder.SetInsertPoint(EntryBB, EntryBB->getFirstInsertionPt());
1322 }
1323
1324 Value *WinEHFrameVariableMaterializer::materializeValueFor(Value *V) {
1325   // If we're asked to materialize a value that is an instruction, we
1326   // temporarily create an alloca in the outlined function and add this
1327   // to the FrameVarInfo map.  When all the outlining is complete, we'll
1328   // collect these into a structure, spilling non-alloca values in the
1329   // parent frame as necessary, and replace these temporary allocas with
1330   // GEPs referencing the frame allocation block.
1331
1332   // If the value is an alloca, the mapping is direct.
1333   if (auto *AV = dyn_cast<AllocaInst>(V)) {
1334     AllocaInst *NewAlloca = dyn_cast<AllocaInst>(AV->clone());
1335     Builder.Insert(NewAlloca, AV->getName());
1336     FrameVarInfo[AV].push_back(NewAlloca);
1337     return NewAlloca;
1338   }
1339
1340   // For other types of instructions or arguments, we need an alloca based on
1341   // the value's type and a load of the alloca.  The alloca will be replaced
1342   // by a GEP, but the load will stay.  In the parent function, the value will
1343   // be spilled to a location in the frame allocation block.
1344   if (isa<Instruction>(V) || isa<Argument>(V)) {
1345     AllocaInst *NewAlloca =
1346         Builder.CreateAlloca(V->getType(), nullptr, "eh.temp.alloca");
1347     FrameVarInfo[V].push_back(NewAlloca);
1348     LoadInst *NewLoad = Builder.CreateLoad(NewAlloca, V->getName() + ".reload");
1349     return NewLoad;
1350   }
1351
1352   // Don't materialize other values.
1353   return nullptr;
1354 }
1355
1356 void WinEHFrameVariableMaterializer::escapeCatchObject(Value *V) {
1357   // Catch parameter objects have to live in the parent frame. When we see a use
1358   // of a catch parameter, add a sentinel to the multimap to indicate that it's
1359   // used from another handler. This will prevent us from trying to sink the
1360   // alloca into the handler and ensure that the catch parameter is present in
1361   // the call to llvm.frameescape.
1362   FrameVarInfo[V].push_back(getCatchObjectSentinel());
1363 }
1364
1365 // This function maps the catch and cleanup handlers that are reachable from the
1366 // specified landing pad. The landing pad sequence will have this basic shape:
1367 //
1368 //  <cleanup handler>
1369 //  <selector comparison>
1370 //  <catch handler>
1371 //  <cleanup handler>
1372 //  <selector comparison>
1373 //  <catch handler>
1374 //  <cleanup handler>
1375 //  ...
1376 //
1377 // Any of the cleanup slots may be absent.  The cleanup slots may be occupied by
1378 // any arbitrary control flow, but all paths through the cleanup code must
1379 // eventually reach the next selector comparison and no path can skip to a
1380 // different selector comparisons, though some paths may terminate abnormally.
1381 // Therefore, we will use a depth first search from the start of any given
1382 // cleanup block and stop searching when we find the next selector comparison.
1383 //
1384 // If the landingpad instruction does not have a catch clause, we will assume
1385 // that any instructions other than selector comparisons and catch handlers can
1386 // be ignored.  In practice, these will only be the boilerplate instructions.
1387 //
1388 // The catch handlers may also have any control structure, but we are only
1389 // interested in the start of the catch handlers, so we don't need to actually
1390 // follow the flow of the catch handlers.  The start of the catch handlers can
1391 // be located from the compare instructions, but they can be skipped in the
1392 // flow by following the contrary branch.
1393 void WinEHPrepare::mapLandingPadBlocks(LandingPadInst *LPad,
1394                                        LandingPadActions &Actions) {
1395   unsigned int NumClauses = LPad->getNumClauses();
1396   unsigned int HandlersFound = 0;
1397   BasicBlock *BB = LPad->getParent();
1398
1399   DEBUG(dbgs() << "Mapping landing pad: " << BB->getName() << "\n");
1400
1401   if (NumClauses == 0) {
1402     findCleanupHandlers(Actions, BB, nullptr);
1403     return;
1404   }
1405
1406   VisitedBlockSet VisitedBlocks;
1407
1408   while (HandlersFound != NumClauses) {
1409     BasicBlock *NextBB = nullptr;
1410
1411     // See if the clause we're looking for is a catch-all.
1412     // If so, the catch begins immediately.
1413     Constant *ExpectedSelector = LPad->getClause(HandlersFound)->stripPointerCasts();
1414     if (isa<ConstantPointerNull>(ExpectedSelector)) {
1415       // The catch all must occur last.
1416       assert(HandlersFound == NumClauses - 1);
1417
1418       // There can be additional selector dispatches in the call chain that we
1419       // need to ignore.
1420       BasicBlock *CatchBlock = nullptr;
1421       Constant *Selector;
1422       while (BB && isSelectorDispatch(BB, CatchBlock, Selector, NextBB)) {
1423         DEBUG(dbgs() << "  Found extra catch dispatch in block "
1424           << CatchBlock->getName() << "\n");
1425         BB = NextBB;
1426       }
1427
1428       // For C++ EH, check if there is any interesting cleanup code before we
1429       // begin the catch. This is important because cleanups cannot rethrow
1430       // exceptions but code called from catches can. For SEH, it isn't
1431       // important if some finally code before a catch-all is executed out of
1432       // line or after recovering from the exception.
1433       if (Personality == EHPersonality::MSVC_CXX)
1434         findCleanupHandlers(Actions, BB, BB);
1435
1436       // Add the catch handler to the action list.
1437       CatchHandler *Action = nullptr;
1438       if (CatchHandlerMap.count(BB) && CatchHandlerMap[BB] != nullptr) {
1439         // If the CatchHandlerMap already has an entry for this BB, re-use it.
1440         Action = CatchHandlerMap[BB];
1441         assert(Action->getSelector() == ExpectedSelector);
1442       } else {
1443         // Since this is a catch-all handler, the selector won't actually appear
1444         // in the code anywhere.  ExpectedSelector here is the constant null ptr
1445         // that we got from the landing pad instruction.
1446         Action = new CatchHandler(BB, ExpectedSelector, nullptr);
1447         CatchHandlerMap[BB] = Action;
1448       }
1449       Actions.insertCatchHandler(Action);
1450       DEBUG(dbgs() << "  Catch all handler at block " << BB->getName() << "\n");
1451       ++HandlersFound;
1452
1453       // Once we reach a catch-all, don't expect to hit a resume instruction.
1454       BB = nullptr;
1455       break;
1456     }
1457
1458     CatchHandler *CatchAction = findCatchHandler(BB, NextBB, VisitedBlocks);
1459     assert(CatchAction);
1460
1461     // See if there is any interesting code executed before the dispatch.
1462     findCleanupHandlers(Actions, BB, CatchAction->getStartBlock());
1463
1464     // When the source program contains multiple nested try blocks the catch
1465     // handlers can get strung together in such a way that we can encounter
1466     // a dispatch for a selector that we've already had a handler for.
1467     if (CatchAction->getSelector()->stripPointerCasts() == ExpectedSelector) {
1468       ++HandlersFound;
1469
1470       // Add the catch handler to the action list.
1471       DEBUG(dbgs() << "  Found catch dispatch in block "
1472                    << CatchAction->getStartBlock()->getName() << "\n");
1473       Actions.insertCatchHandler(CatchAction);
1474     } else {
1475       // Under some circumstances optimized IR will flow unconditionally into a
1476       // handler block without checking the selector.  This can only happen if
1477       // the landing pad has a catch-all handler and the handler for the
1478       // preceeding catch clause is identical to the catch-call handler
1479       // (typically an empty catch).  In this case, the handler must be shared
1480       // by all remaining clauses.
1481       if (isa<ConstantPointerNull>(
1482               CatchAction->getSelector()->stripPointerCasts())) {
1483         DEBUG(dbgs() << "  Applying early catch-all handler in block "
1484                      << CatchAction->getStartBlock()->getName()
1485                      << "  to all remaining clauses.\n");
1486         Actions.insertCatchHandler(CatchAction);
1487         return;
1488       }
1489
1490       DEBUG(dbgs() << "  Found extra catch dispatch in block "
1491                    << CatchAction->getStartBlock()->getName() << "\n");
1492     }
1493
1494     // Move on to the block after the catch handler.
1495     BB = NextBB;
1496   }
1497
1498   // If we didn't wind up in a catch-all, see if there is any interesting code
1499   // executed before the resume.
1500   findCleanupHandlers(Actions, BB, BB);
1501
1502   // It's possible that some optimization moved code into a landingpad that
1503   // wasn't
1504   // previously being used for cleanup.  If that happens, we need to execute
1505   // that
1506   // extra code from a cleanup handler.
1507   if (Actions.includesCleanup() && !LPad->isCleanup())
1508     LPad->setCleanup(true);
1509 }
1510
1511 // This function searches starting with the input block for the next
1512 // block that terminates with a branch whose condition is based on a selector
1513 // comparison.  This may be the input block.  See the mapLandingPadBlocks
1514 // comments for a discussion of control flow assumptions.
1515 //
1516 CatchHandler *WinEHPrepare::findCatchHandler(BasicBlock *BB,
1517                                              BasicBlock *&NextBB,
1518                                              VisitedBlockSet &VisitedBlocks) {
1519   // See if we've already found a catch handler use it.
1520   // Call count() first to avoid creating a null entry for blocks
1521   // we haven't seen before.
1522   if (CatchHandlerMap.count(BB) && CatchHandlerMap[BB] != nullptr) {
1523     CatchHandler *Action = cast<CatchHandler>(CatchHandlerMap[BB]);
1524     NextBB = Action->getNextBB();
1525     return Action;
1526   }
1527
1528   // VisitedBlocks applies only to the current search.  We still
1529   // need to consider blocks that we've visited while mapping other
1530   // landing pads.
1531   VisitedBlocks.insert(BB);
1532
1533   BasicBlock *CatchBlock = nullptr;
1534   Constant *Selector = nullptr;
1535
1536   // If this is the first time we've visited this block from any landing pad
1537   // look to see if it is a selector dispatch block.
1538   if (!CatchHandlerMap.count(BB)) {
1539     if (isSelectorDispatch(BB, CatchBlock, Selector, NextBB)) {
1540       CatchHandler *Action = new CatchHandler(BB, Selector, NextBB);
1541       CatchHandlerMap[BB] = Action;
1542       return Action;
1543     }
1544     // If we encounter a block containing an llvm.eh.begincatch before we
1545     // find a selector dispatch block, the handler is assumed to be
1546     // reached unconditionally.  This happens for catch-all blocks, but
1547     // it can also happen for other catch handlers that have been combined
1548     // with the catch-all handler during optimization.
1549     if (isCatchBlock(BB)) {
1550       PointerType *Int8PtrTy = Type::getInt8PtrTy(BB->getContext());
1551       Constant *NullSelector = ConstantPointerNull::get(Int8PtrTy);
1552       CatchHandler *Action = new CatchHandler(BB, NullSelector, nullptr);
1553       CatchHandlerMap[BB] = Action;
1554       return Action;
1555     }
1556   }
1557
1558   // Visit each successor, looking for the dispatch.
1559   // FIXME: We expect to find the dispatch quickly, so this will probably
1560   //        work better as a breadth first search.
1561   for (BasicBlock *Succ : successors(BB)) {
1562     if (VisitedBlocks.count(Succ))
1563       continue;
1564
1565     CatchHandler *Action = findCatchHandler(Succ, NextBB, VisitedBlocks);
1566     if (Action)
1567       return Action;
1568   }
1569   return nullptr;
1570 }
1571
1572 // These are helper functions to combine repeated code from findCleanupHandlers.
1573 static void createCleanupHandler(LandingPadActions &Actions,
1574                                  CleanupHandlerMapTy &CleanupHandlerMap,
1575                                  BasicBlock *BB) {
1576   CleanupHandler *Action = new CleanupHandler(BB);
1577   CleanupHandlerMap[BB] = Action;
1578   Actions.insertCleanupHandler(Action);
1579   DEBUG(dbgs() << "  Found cleanup code in block "
1580                << Action->getStartBlock()->getName() << "\n");
1581 }
1582
1583 static bool isFrameAddressCall(Value *V) {
1584   return match(V, m_Intrinsic<Intrinsic::frameaddress>(m_SpecificInt(0)));
1585 }
1586
1587 static CallSite matchOutlinedFinallyCall(BasicBlock *BB,
1588                                          Instruction *MaybeCall) {
1589   // Look for finally blocks that Clang has already outlined for us.
1590   //   %fp = call i8* @llvm.frameaddress(i32 0)
1591   //   call void @"fin$parent"(iN 1, i8* %fp)
1592   if (isFrameAddressCall(MaybeCall) && MaybeCall != BB->getTerminator())
1593     MaybeCall = MaybeCall->getNextNode();
1594   CallSite FinallyCall(MaybeCall);
1595   if (!FinallyCall || FinallyCall.arg_size() != 2)
1596     return CallSite();
1597   if (!match(FinallyCall.getArgument(0), m_SpecificInt(1)))
1598     return CallSite();
1599   if (!isFrameAddressCall(FinallyCall.getArgument(1)))
1600     return CallSite();
1601   return FinallyCall;
1602 }
1603
1604 static BasicBlock *followSingleUnconditionalBranches(BasicBlock *BB) {
1605   // Skip single ubr blocks.
1606   while (BB->getFirstNonPHIOrDbg() == BB->getTerminator()) {
1607     auto *Br = dyn_cast<BranchInst>(BB->getTerminator());
1608     if (Br && Br->isUnconditional())
1609       BB = Br->getSuccessor(0);
1610     else
1611       return BB;
1612   }
1613   return BB;
1614 }
1615
1616 // This function searches starting with the input block for the next block that
1617 // contains code that is not part of a catch handler and would not be eliminated
1618 // during handler outlining.
1619 //
1620 void WinEHPrepare::findCleanupHandlers(LandingPadActions &Actions,
1621                                        BasicBlock *StartBB, BasicBlock *EndBB) {
1622   // Here we will skip over the following:
1623   //
1624   // landing pad prolog:
1625   //
1626   // Unconditional branches
1627   //
1628   // Selector dispatch
1629   //
1630   // Resume pattern
1631   //
1632   // Anything else marks the start of an interesting block
1633
1634   BasicBlock *BB = StartBB;
1635   // Anything other than an unconditional branch will kick us out of this loop
1636   // one way or another.
1637   while (BB) {
1638     BB = followSingleUnconditionalBranches(BB);
1639     // If we've already scanned this block, don't scan it again.  If it is
1640     // a cleanup block, there will be an action in the CleanupHandlerMap.
1641     // If we've scanned it and it is not a cleanup block, there will be a
1642     // nullptr in the CleanupHandlerMap.  If we have not scanned it, there will
1643     // be no entry in the CleanupHandlerMap.  We must call count() first to
1644     // avoid creating a null entry for blocks we haven't scanned.
1645     if (CleanupHandlerMap.count(BB)) {
1646       if (auto *Action = CleanupHandlerMap[BB]) {
1647         Actions.insertCleanupHandler(Action);
1648         DEBUG(dbgs() << "  Found cleanup code in block "
1649               << Action->getStartBlock()->getName() << "\n");
1650         // FIXME: This cleanup might chain into another, and we need to discover
1651         // that.
1652         return;
1653       } else {
1654         // Here we handle the case where the cleanup handler map contains a
1655         // value for this block but the value is a nullptr.  This means that
1656         // we have previously analyzed the block and determined that it did
1657         // not contain any cleanup code.  Based on the earlier analysis, we
1658         // know the the block must end in either an unconditional branch, a
1659         // resume or a conditional branch that is predicated on a comparison
1660         // with a selector.  Either the resume or the selector dispatch
1661         // would terminate the search for cleanup code, so the unconditional
1662         // branch is the only case for which we might need to continue
1663         // searching.
1664         BasicBlock *SuccBB = followSingleUnconditionalBranches(BB);
1665         if (SuccBB == BB || SuccBB == EndBB)
1666           return;
1667         BB = SuccBB;
1668         continue;
1669       }
1670     }
1671
1672     // Create an entry in the cleanup handler map for this block.  Initially
1673     // we create an entry that says this isn't a cleanup block.  If we find
1674     // cleanup code, the caller will replace this entry.
1675     CleanupHandlerMap[BB] = nullptr;
1676
1677     TerminatorInst *Terminator = BB->getTerminator();
1678
1679     // Landing pad blocks have extra instructions we need to accept.
1680     LandingPadMap *LPadMap = nullptr;
1681     if (BB->isLandingPad()) {
1682       LandingPadInst *LPad = BB->getLandingPadInst();
1683       LPadMap = &LPadMaps[LPad];
1684       if (!LPadMap->isInitialized())
1685         LPadMap->mapLandingPad(LPad);
1686     }
1687
1688     // Look for the bare resume pattern:
1689     //   %lpad.val1 = insertvalue { i8*, i32 } undef, i8* %exn, 0
1690     //   %lpad.val2 = insertvalue { i8*, i32 } %lpad.val1, i32 %sel, 1
1691     //   resume { i8*, i32 } %lpad.val2
1692     if (auto *Resume = dyn_cast<ResumeInst>(Terminator)) {
1693       InsertValueInst *Insert1 = nullptr;
1694       InsertValueInst *Insert2 = nullptr;
1695       Value *ResumeVal = Resume->getOperand(0);
1696       // If the resume value isn't a phi or landingpad value, it should be a
1697       // series of insertions. Identify them so we can avoid them when scanning
1698       // for cleanups.
1699       if (!isa<PHINode>(ResumeVal) && !isa<LandingPadInst>(ResumeVal)) {
1700         Insert2 = dyn_cast<InsertValueInst>(ResumeVal);
1701         if (!Insert2)
1702           return createCleanupHandler(Actions, CleanupHandlerMap, BB);
1703         Insert1 = dyn_cast<InsertValueInst>(Insert2->getAggregateOperand());
1704         if (!Insert1)
1705           return createCleanupHandler(Actions, CleanupHandlerMap, BB);
1706       }
1707       for (BasicBlock::iterator II = BB->getFirstNonPHIOrDbg(), IE = BB->end();
1708            II != IE; ++II) {
1709         Instruction *Inst = II;
1710         if (LPadMap && LPadMap->isLandingPadSpecificInst(Inst))
1711           continue;
1712         if (Inst == Insert1 || Inst == Insert2 || Inst == Resume)
1713           continue;
1714         if (!Inst->hasOneUse() ||
1715             (Inst->user_back() != Insert1 && Inst->user_back() != Insert2)) {
1716           return createCleanupHandler(Actions, CleanupHandlerMap, BB);
1717         }
1718       }
1719       return;
1720     }
1721
1722     BranchInst *Branch = dyn_cast<BranchInst>(Terminator);
1723     if (Branch && Branch->isConditional()) {
1724       // Look for the selector dispatch.
1725       //   %2 = call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIf to i8*))
1726       //   %matches = icmp eq i32 %sel, %2
1727       //   br i1 %matches, label %catch14, label %eh.resume
1728       CmpInst *Compare = dyn_cast<CmpInst>(Branch->getCondition());
1729       if (!Compare || !Compare->isEquality())
1730         return createCleanupHandler(Actions, CleanupHandlerMap, BB);
1731       for (BasicBlock::iterator II = BB->getFirstNonPHIOrDbg(), IE = BB->end();
1732            II != IE; ++II) {
1733         Instruction *Inst = II;
1734         if (LPadMap && LPadMap->isLandingPadSpecificInst(Inst))
1735           continue;
1736         if (Inst == Compare || Inst == Branch)
1737           continue;
1738         if (match(Inst, m_Intrinsic<Intrinsic::eh_typeid_for>()))
1739           continue;
1740         return createCleanupHandler(Actions, CleanupHandlerMap, BB);
1741       }
1742       // The selector dispatch block should always terminate our search.
1743       assert(BB == EndBB);
1744       return;
1745     }
1746
1747     if (isAsynchronousEHPersonality(Personality)) {
1748       // If this is a landingpad block, split the block at the first non-landing
1749       // pad instruction.
1750       Instruction *MaybeCall = BB->getFirstNonPHIOrDbg();
1751       if (LPadMap) {
1752         while (MaybeCall != BB->getTerminator() &&
1753                LPadMap->isLandingPadSpecificInst(MaybeCall))
1754           MaybeCall = MaybeCall->getNextNode();
1755       }
1756
1757       // Look for outlined finally calls.
1758       if (CallSite FinallyCall = matchOutlinedFinallyCall(BB, MaybeCall)) {
1759         Function *Fin = FinallyCall.getCalledFunction();
1760         assert(Fin && "outlined finally call should be direct");
1761         auto *Action = new CleanupHandler(BB);
1762         Action->setHandlerBlockOrFunc(Fin);
1763         Actions.insertCleanupHandler(Action);
1764         CleanupHandlerMap[BB] = Action;
1765         DEBUG(dbgs() << "  Found frontend-outlined finally call to "
1766                      << Fin->getName() << " in block "
1767                      << Action->getStartBlock()->getName() << "\n");
1768
1769         // Split the block if there were more interesting instructions and look
1770         // for finally calls in the normal successor block.
1771         BasicBlock *SuccBB = BB;
1772         if (FinallyCall.getInstruction() != BB->getTerminator() &&
1773             FinallyCall.getInstruction()->getNextNode() != BB->getTerminator()) {
1774           SuccBB = BB->splitBasicBlock(FinallyCall.getInstruction()->getNextNode());
1775         } else {
1776           if (FinallyCall.isInvoke()) {
1777             SuccBB = cast<InvokeInst>(FinallyCall.getInstruction())->getNormalDest();
1778           } else {
1779             SuccBB = BB->getUniqueSuccessor();
1780             assert(SuccBB && "splitOutlinedFinallyCalls didn't insert a branch");
1781           }
1782         }
1783         BB = SuccBB;
1784         if (BB == EndBB)
1785           return;
1786         continue;
1787       }
1788     }
1789
1790     // Anything else is either a catch block or interesting cleanup code.
1791     for (BasicBlock::iterator II = BB->getFirstNonPHIOrDbg(), IE = BB->end();
1792          II != IE; ++II) {
1793       Instruction *Inst = II;
1794       if (LPadMap && LPadMap->isLandingPadSpecificInst(Inst))
1795         continue;
1796       // Unconditional branches fall through to this loop.
1797       if (Inst == Branch)
1798         continue;
1799       // If this is a catch block, there is no cleanup code to be found.
1800       if (match(Inst, m_Intrinsic<Intrinsic::eh_begincatch>()))
1801         return;
1802       // If this a nested landing pad, it may contain an endcatch call.
1803       if (match(Inst, m_Intrinsic<Intrinsic::eh_endcatch>()))
1804         return;
1805       // Anything else makes this interesting cleanup code.
1806       return createCleanupHandler(Actions, CleanupHandlerMap, BB);
1807     }
1808
1809     // Only unconditional branches in empty blocks should get this far.
1810     assert(Branch && Branch->isUnconditional());
1811     if (BB == EndBB)
1812       return;
1813     BB = Branch->getSuccessor(0);
1814   }
1815 }
1816
1817 // This is a public function, declared in WinEHFuncInfo.h and is also
1818 // referenced by WinEHNumbering in FunctionLoweringInfo.cpp.
1819 void llvm::parseEHActions(const IntrinsicInst *II,
1820                           SmallVectorImpl<ActionHandler *> &Actions) {
1821   for (unsigned I = 0, E = II->getNumArgOperands(); I != E;) {
1822     uint64_t ActionKind =
1823         cast<ConstantInt>(II->getArgOperand(I))->getZExtValue();
1824     if (ActionKind == /*catch=*/1) {
1825       auto *Selector = cast<Constant>(II->getArgOperand(I + 1));
1826       ConstantInt *EHObjIndex = cast<ConstantInt>(II->getArgOperand(I + 2));
1827       int64_t EHObjIndexVal = EHObjIndex->getSExtValue();
1828       Constant *Handler = cast<Constant>(II->getArgOperand(I + 3));
1829       I += 4;
1830       auto *CH = new CatchHandler(/*BB=*/nullptr, Selector, /*NextBB=*/nullptr);
1831       CH->setHandlerBlockOrFunc(Handler);
1832       CH->setExceptionVarIndex(EHObjIndexVal);
1833       Actions.push_back(CH);
1834     } else if (ActionKind == 0) {
1835       Constant *Handler = cast<Constant>(II->getArgOperand(I + 1));
1836       I += 2;
1837       auto *CH = new CleanupHandler(/*BB=*/nullptr);
1838       CH->setHandlerBlockOrFunc(Handler);
1839       Actions.push_back(CH);
1840     } else {
1841       llvm_unreachable("Expected either a catch or cleanup handler!");
1842     }
1843   }
1844   std::reverse(Actions.begin(), Actions.end());
1845 }