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