lib/CodeGen/WinEHPrepare.cpp

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