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