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