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