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