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