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