1 //===-- X86WinEHState - Insert EH state updates for win32 exceptions ------===//
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 // All functions using an MSVC EH personality use an explicitly updated state
11 // number stored in an exception registration stack object. The registration
12 // object is linked into a thread-local chain of registrations stored at fs:00.
13 // This pass adds the registration object and EH state updates.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "X86.h"
18 #include "llvm/ADT/PostOrderIterator.h"
19 #include "llvm/Analysis/CFG.h"
20 #include "llvm/Analysis/EHPersonalities.h"
21 #include "llvm/CodeGen/MachineModuleInfo.h"
22 #include "llvm/CodeGen/WinEHFuncInfo.h"
23 #include "llvm/IR/CallSite.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/Instructions.h"
26 #include "llvm/IR/IntrinsicInst.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Support/Debug.h"
31 #include <deque>
32 
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "winehstate"
36 
37 namespace llvm {
38 void initializeWinEHStatePassPass(PassRegistry &);
39 }
40 
41 namespace {
42 const int OverdefinedState = INT_MIN;
43 
44 class WinEHStatePass : public FunctionPass {
45 public:
46   static char ID; // Pass identification, replacement for typeid.
47 
48   WinEHStatePass() : FunctionPass(ID) {
49     initializeWinEHStatePassPass(*PassRegistry::getPassRegistry());
50   }
51 
52   bool runOnFunction(Function &Fn) override;
53 
54   bool doInitialization(Module &M) override;
55 
56   bool doFinalization(Module &M) override;
57 
58   void getAnalysisUsage(AnalysisUsage &AU) const override;
59 
60   const char *getPassName() const override {
61     return "Windows 32-bit x86 EH state insertion";
62   }
63 
64 private:
65   void emitExceptionRegistrationRecord(Function *F);
66 
67   void linkExceptionRegistration(IRBuilder<> &Builder, Function *Handler);
68   void unlinkExceptionRegistration(IRBuilder<> &Builder);
69   void addStateStores(Function &F, WinEHFuncInfo &FuncInfo);
70   void insertStateNumberStore(Instruction *IP, int State);
71 
72   Value *emitEHLSDA(IRBuilder<> &Builder, Function *F);
73 
74   Function *generateLSDAInEAXThunk(Function *ParentFunc);
75 
76   bool isStateStoreNeeded(EHPersonality Personality, CallSite CS);
77   void rewriteSetJmpCallSite(IRBuilder<> &Builder, Function &F, CallSite CS,
78                              Value *State);
79   int getBaseStateForBB(DenseMap<BasicBlock *, ColorVector> &BlockColors,
80                         WinEHFuncInfo &FuncInfo, BasicBlock *BB);
81   int getStateForCallSite(DenseMap<BasicBlock *, ColorVector> &BlockColors,
82                           WinEHFuncInfo &FuncInfo, CallSite CS);
83 
84   // Module-level type getters.
85   Type *getEHLinkRegistrationType();
86   Type *getSEHRegistrationType();
87   Type *getCXXEHRegistrationType();
88 
89   // Per-module data.
90   Module *TheModule = nullptr;
91   StructType *EHLinkRegistrationTy = nullptr;
92   StructType *CXXEHRegistrationTy = nullptr;
93   StructType *SEHRegistrationTy = nullptr;
94   Constant *SetJmp3 = nullptr;
95   Constant *CxxLongjmpUnwind = nullptr;
96 
97   // Per-function state
98   EHPersonality Personality = EHPersonality::Unknown;
99   Function *PersonalityFn = nullptr;
100   bool UseStackGuard = false;
101   int ParentBaseState;
102   Constant *SehLongjmpUnwind = nullptr;
103   Constant *Cookie = nullptr;
104 
105   /// The stack allocation containing all EH data, including the link in the
106   /// fs:00 chain and the current state.
107   AllocaInst *RegNode = nullptr;
108 
109   /// The index of the state field of RegNode.
110   int StateFieldIndex = ~0U;
111 
112   /// The linked list node subobject inside of RegNode.
113   Value *Link = nullptr;
114 };
115 }
116 
117 FunctionPass *llvm::createX86WinEHStatePass() { return new WinEHStatePass(); }
118 
119 char WinEHStatePass::ID = 0;
120 
121 INITIALIZE_PASS(WinEHStatePass, "x86-winehstate",
122                 "Insert stores for EH state numbers", false, false)
123 
124 bool WinEHStatePass::doInitialization(Module &M) {
125   TheModule = &M;
126   return false;
127 }
128 
129 bool WinEHStatePass::doFinalization(Module &M) {
130   assert(TheModule == &M);
131   TheModule = nullptr;
132   EHLinkRegistrationTy = nullptr;
133   CXXEHRegistrationTy = nullptr;
134   SEHRegistrationTy = nullptr;
135   SetJmp3 = nullptr;
136   CxxLongjmpUnwind = nullptr;
137   SehLongjmpUnwind = nullptr;
138   Cookie = nullptr;
139   return false;
140 }
141 
142 void WinEHStatePass::getAnalysisUsage(AnalysisUsage &AU) const {
143   // This pass should only insert a stack allocation, memory accesses, and
144   // localrecovers.
145   AU.setPreservesCFG();
146 }
147 
148 bool WinEHStatePass::runOnFunction(Function &F) {
149   // Check the personality. Do nothing if this personality doesn't use funclets.
150   if (!F.hasPersonalityFn())
151     return false;
152   PersonalityFn =
153       dyn_cast<Function>(F.getPersonalityFn()->stripPointerCasts());
154   if (!PersonalityFn)
155     return false;
156   Personality = classifyEHPersonality(PersonalityFn);
157   if (!isFuncletEHPersonality(Personality))
158     return false;
159 
160   // Skip this function if there are no EH pads and we aren't using IR-level
161   // outlining.
162   bool HasPads = false;
163   for (BasicBlock &BB : F) {
164     if (BB.isEHPad()) {
165       HasPads = true;
166       break;
167     }
168   }
169   if (!HasPads)
170     return false;
171 
172   Type *Int8PtrType = Type::getInt8PtrTy(TheModule->getContext());
173   SetJmp3 = TheModule->getOrInsertFunction(
174       "_setjmp3", FunctionType::get(
175                       Type::getInt32Ty(TheModule->getContext()),
176                       {Int8PtrType, Type::getInt32Ty(TheModule->getContext())},
177                       /*isVarArg=*/true));
178 
179   // Disable frame pointer elimination in this function.
180   // FIXME: Do the nested handlers need to keep the parent ebp in ebp, or can we
181   // use an arbitrary register?
182   F.addFnAttr("no-frame-pointer-elim", "true");
183 
184   emitExceptionRegistrationRecord(&F);
185 
186   // The state numbers calculated here in IR must agree with what we calculate
187   // later on for the MachineFunction. In particular, if an IR pass deletes an
188   // unreachable EH pad after this point before machine CFG construction, we
189   // will be in trouble. If this assumption is ever broken, we should turn the
190   // numbers into an immutable analysis pass.
191   WinEHFuncInfo FuncInfo;
192   addStateStores(F, FuncInfo);
193 
194   // Reset per-function state.
195   PersonalityFn = nullptr;
196   Personality = EHPersonality::Unknown;
197   UseStackGuard = false;
198   return true;
199 }
200 
201 /// Get the common EH registration subobject:
202 ///   typedef _EXCEPTION_DISPOSITION (*PEXCEPTION_ROUTINE)(
203 ///       _EXCEPTION_RECORD *, void *, _CONTEXT *, void *);
204 ///   struct EHRegistrationNode {
205 ///     EHRegistrationNode *Next;
206 ///     PEXCEPTION_ROUTINE Handler;
207 ///   };
208 Type *WinEHStatePass::getEHLinkRegistrationType() {
209   if (EHLinkRegistrationTy)
210     return EHLinkRegistrationTy;
211   LLVMContext &Context = TheModule->getContext();
212   EHLinkRegistrationTy = StructType::create(Context, "EHRegistrationNode");
213   Type *FieldTys[] = {
214       EHLinkRegistrationTy->getPointerTo(0), // EHRegistrationNode *Next
215       Type::getInt8PtrTy(Context) // EXCEPTION_DISPOSITION (*Handler)(...)
216   };
217   EHLinkRegistrationTy->setBody(FieldTys, false);
218   return EHLinkRegistrationTy;
219 }
220 
221 /// The __CxxFrameHandler3 registration node:
222 ///   struct CXXExceptionRegistration {
223 ///     void *SavedESP;
224 ///     EHRegistrationNode SubRecord;
225 ///     int32_t TryLevel;
226 ///   };
227 Type *WinEHStatePass::getCXXEHRegistrationType() {
228   if (CXXEHRegistrationTy)
229     return CXXEHRegistrationTy;
230   LLVMContext &Context = TheModule->getContext();
231   Type *FieldTys[] = {
232       Type::getInt8PtrTy(Context), // void *SavedESP
233       getEHLinkRegistrationType(), // EHRegistrationNode SubRecord
234       Type::getInt32Ty(Context)    // int32_t TryLevel
235   };
236   CXXEHRegistrationTy =
237       StructType::create(FieldTys, "CXXExceptionRegistration");
238   return CXXEHRegistrationTy;
239 }
240 
241 /// The _except_handler3/4 registration node:
242 ///   struct EH4ExceptionRegistration {
243 ///     void *SavedESP;
244 ///     _EXCEPTION_POINTERS *ExceptionPointers;
245 ///     EHRegistrationNode SubRecord;
246 ///     int32_t EncodedScopeTable;
247 ///     int32_t TryLevel;
248 ///   };
249 Type *WinEHStatePass::getSEHRegistrationType() {
250   if (SEHRegistrationTy)
251     return SEHRegistrationTy;
252   LLVMContext &Context = TheModule->getContext();
253   Type *FieldTys[] = {
254       Type::getInt8PtrTy(Context), // void *SavedESP
255       Type::getInt8PtrTy(Context), // void *ExceptionPointers
256       getEHLinkRegistrationType(), // EHRegistrationNode SubRecord
257       Type::getInt32Ty(Context),   // int32_t EncodedScopeTable
258       Type::getInt32Ty(Context)    // int32_t TryLevel
259   };
260   SEHRegistrationTy = StructType::create(FieldTys, "SEHExceptionRegistration");
261   return SEHRegistrationTy;
262 }
263 
264 // Emit an exception registration record. These are stack allocations with the
265 // common subobject of two pointers: the previous registration record (the old
266 // fs:00) and the personality function for the current frame. The data before
267 // and after that is personality function specific.
268 void WinEHStatePass::emitExceptionRegistrationRecord(Function *F) {
269   assert(Personality == EHPersonality::MSVC_CXX ||
270          Personality == EHPersonality::MSVC_X86SEH);
271 
272   // Struct type of RegNode. Used for GEPing.
273   Type *RegNodeTy;
274 
275   IRBuilder<> Builder(&F->getEntryBlock(), F->getEntryBlock().begin());
276   Type *Int8PtrType = Builder.getInt8PtrTy();
277   if (Personality == EHPersonality::MSVC_CXX) {
278     RegNodeTy = getCXXEHRegistrationType();
279     RegNode = Builder.CreateAlloca(RegNodeTy);
280     // SavedESP = llvm.stacksave()
281     Value *SP = Builder.CreateCall(
282         Intrinsic::getDeclaration(TheModule, Intrinsic::stacksave), {});
283     Builder.CreateStore(SP, Builder.CreateStructGEP(RegNodeTy, RegNode, 0));
284     // TryLevel = -1
285     StateFieldIndex = 2;
286     ParentBaseState = -1;
287     insertStateNumberStore(&*Builder.GetInsertPoint(), ParentBaseState);
288     // Handler = __ehhandler$F
289     Function *Trampoline = generateLSDAInEAXThunk(F);
290     Link = Builder.CreateStructGEP(RegNodeTy, RegNode, 1);
291     linkExceptionRegistration(Builder, Trampoline);
292 
293     CxxLongjmpUnwind = TheModule->getOrInsertFunction(
294         "__CxxLongjmpUnwind",
295         FunctionType::get(Type::getVoidTy(TheModule->getContext()), Int8PtrType,
296                           /*isVarArg=*/false));
297     cast<Function>(CxxLongjmpUnwind->stripPointerCasts())
298         ->setCallingConv(CallingConv::X86_StdCall);
299   } else if (Personality == EHPersonality::MSVC_X86SEH) {
300     // If _except_handler4 is in use, some additional guard checks and prologue
301     // stuff is required.
302     RegNodeTy = getSEHRegistrationType();
303     RegNode = Builder.CreateAlloca(RegNodeTy);
304     // SavedESP = llvm.stacksave()
305     Value *SP = Builder.CreateCall(
306         Intrinsic::getDeclaration(TheModule, Intrinsic::stacksave), {});
307     Builder.CreateStore(SP, Builder.CreateStructGEP(RegNodeTy, RegNode, 0));
308     // TryLevel = -2 / -1
309     StateFieldIndex = 4;
310     StringRef PersonalityName = PersonalityFn->getName();
311     UseStackGuard = (PersonalityName == "_except_handler4");
312     ParentBaseState = UseStackGuard ? -2 : -1;
313     insertStateNumberStore(&*Builder.GetInsertPoint(), ParentBaseState);
314     // ScopeTable = llvm.x86.seh.lsda(F)
315     Value *LSDA = emitEHLSDA(Builder, F);
316     Type *Int32Ty = Type::getInt32Ty(TheModule->getContext());
317     LSDA = Builder.CreatePtrToInt(LSDA, Int32Ty);
318     // If using _except_handler4, xor the address of the table with
319     // __security_cookie.
320     if (UseStackGuard) {
321       Cookie = TheModule->getOrInsertGlobal("__security_cookie", Int32Ty);
322       Value *Val = Builder.CreateLoad(Int32Ty, Cookie);
323       LSDA = Builder.CreateXor(LSDA, Val);
324     }
325     Builder.CreateStore(LSDA, Builder.CreateStructGEP(RegNodeTy, RegNode, 3));
326     Link = Builder.CreateStructGEP(RegNodeTy, RegNode, 2);
327     linkExceptionRegistration(Builder, PersonalityFn);
328 
329     SehLongjmpUnwind = TheModule->getOrInsertFunction(
330         UseStackGuard ? "_seh_longjmp_unwind4" : "_seh_longjmp_unwind",
331         FunctionType::get(Type::getVoidTy(TheModule->getContext()), Int8PtrType,
332                           /*isVarArg=*/false));
333     cast<Function>(SehLongjmpUnwind->stripPointerCasts())
334         ->setCallingConv(CallingConv::X86_StdCall);
335   } else {
336     llvm_unreachable("unexpected personality function");
337   }
338 
339   // Insert an unlink before all returns.
340   for (BasicBlock &BB : *F) {
341     TerminatorInst *T = BB.getTerminator();
342     if (!isa<ReturnInst>(T))
343       continue;
344     Builder.SetInsertPoint(T);
345     unlinkExceptionRegistration(Builder);
346   }
347 }
348 
349 Value *WinEHStatePass::emitEHLSDA(IRBuilder<> &Builder, Function *F) {
350   Value *FI8 = Builder.CreateBitCast(F, Type::getInt8PtrTy(F->getContext()));
351   return Builder.CreateCall(
352       Intrinsic::getDeclaration(TheModule, Intrinsic::x86_seh_lsda), FI8);
353 }
354 
355 /// Generate a thunk that puts the LSDA of ParentFunc in EAX and then calls
356 /// PersonalityFn, forwarding the parameters passed to PEXCEPTION_ROUTINE:
357 ///   typedef _EXCEPTION_DISPOSITION (*PEXCEPTION_ROUTINE)(
358 ///       _EXCEPTION_RECORD *, void *, _CONTEXT *, void *);
359 /// We essentially want this code:
360 ///   movl $lsda, %eax
361 ///   jmpl ___CxxFrameHandler3
362 Function *WinEHStatePass::generateLSDAInEAXThunk(Function *ParentFunc) {
363   LLVMContext &Context = ParentFunc->getContext();
364   Type *Int32Ty = Type::getInt32Ty(Context);
365   Type *Int8PtrType = Type::getInt8PtrTy(Context);
366   Type *ArgTys[5] = {Int8PtrType, Int8PtrType, Int8PtrType, Int8PtrType,
367                      Int8PtrType};
368   FunctionType *TrampolineTy =
369       FunctionType::get(Int32Ty, makeArrayRef(&ArgTys[0], 4),
370                         /*isVarArg=*/false);
371   FunctionType *TargetFuncTy =
372       FunctionType::get(Int32Ty, makeArrayRef(&ArgTys[0], 5),
373                         /*isVarArg=*/false);
374   Function *Trampoline =
375       Function::Create(TrampolineTy, GlobalValue::InternalLinkage,
376                        Twine("__ehhandler$") + GlobalValue::getRealLinkageName(
377                                                    ParentFunc->getName()),
378                        TheModule);
379   BasicBlock *EntryBB = BasicBlock::Create(Context, "entry", Trampoline);
380   IRBuilder<> Builder(EntryBB);
381   Value *LSDA = emitEHLSDA(Builder, ParentFunc);
382   Value *CastPersonality =
383       Builder.CreateBitCast(PersonalityFn, TargetFuncTy->getPointerTo());
384   auto AI = Trampoline->arg_begin();
385   Value *Args[5] = {LSDA, &*AI++, &*AI++, &*AI++, &*AI++};
386   CallInst *Call = Builder.CreateCall(CastPersonality, Args);
387   // Can't use musttail due to prototype mismatch, but we can use tail.
388   Call->setTailCall(true);
389   // Set inreg so we pass it in EAX.
390   Call->addAttribute(1, Attribute::InReg);
391   Builder.CreateRet(Call);
392   return Trampoline;
393 }
394 
395 void WinEHStatePass::linkExceptionRegistration(IRBuilder<> &Builder,
396                                                Function *Handler) {
397   // Emit the .safeseh directive for this function.
398   Handler->addFnAttr("safeseh");
399 
400   Type *LinkTy = getEHLinkRegistrationType();
401   // Handler = Handler
402   Value *HandlerI8 = Builder.CreateBitCast(Handler, Builder.getInt8PtrTy());
403   Builder.CreateStore(HandlerI8, Builder.CreateStructGEP(LinkTy, Link, 1));
404   // Next = [fs:00]
405   Constant *FSZero =
406       Constant::getNullValue(LinkTy->getPointerTo()->getPointerTo(257));
407   Value *Next = Builder.CreateLoad(FSZero);
408   Builder.CreateStore(Next, Builder.CreateStructGEP(LinkTy, Link, 0));
409   // [fs:00] = Link
410   Builder.CreateStore(Link, FSZero);
411 }
412 
413 void WinEHStatePass::unlinkExceptionRegistration(IRBuilder<> &Builder) {
414   // Clone Link into the current BB for better address mode folding.
415   if (auto *GEP = dyn_cast<GetElementPtrInst>(Link)) {
416     GEP = cast<GetElementPtrInst>(GEP->clone());
417     Builder.Insert(GEP);
418     Link = GEP;
419   }
420   Type *LinkTy = getEHLinkRegistrationType();
421   // [fs:00] = Link->Next
422   Value *Next =
423       Builder.CreateLoad(Builder.CreateStructGEP(LinkTy, Link, 0));
424   Constant *FSZero =
425       Constant::getNullValue(LinkTy->getPointerTo()->getPointerTo(257));
426   Builder.CreateStore(Next, FSZero);
427 }
428 
429 // Calls to setjmp(p) are lowered to _setjmp3(p, 0) by the frontend.
430 // The idea behind _setjmp3 is that it takes an optional number of personality
431 // specific parameters to indicate how to restore the personality-specific frame
432 // state when longjmp is initiated.  Typically, the current TryLevel is saved.
433 void WinEHStatePass::rewriteSetJmpCallSite(IRBuilder<> &Builder, Function &F,
434                                            CallSite CS, Value *State) {
435   // Don't rewrite calls with a weird number of arguments.
436   if (CS.getNumArgOperands() != 2)
437     return;
438 
439   Instruction *Inst = CS.getInstruction();
440 
441   SmallVector<OperandBundleDef, 1> OpBundles;
442   CS.getOperandBundlesAsDefs(OpBundles);
443 
444   SmallVector<Value *, 3> OptionalArgs;
445   if (Personality == EHPersonality::MSVC_CXX) {
446     OptionalArgs.push_back(CxxLongjmpUnwind);
447     OptionalArgs.push_back(State);
448     OptionalArgs.push_back(emitEHLSDA(Builder, &F));
449   } else if (Personality == EHPersonality::MSVC_X86SEH) {
450     OptionalArgs.push_back(SehLongjmpUnwind);
451     OptionalArgs.push_back(State);
452     if (UseStackGuard)
453       OptionalArgs.push_back(Cookie);
454   } else {
455     llvm_unreachable("unhandled personality!");
456   }
457 
458   SmallVector<Value *, 5> Args;
459   Args.push_back(
460       Builder.CreateBitCast(CS.getArgOperand(0), Builder.getInt8PtrTy()));
461   Args.push_back(Builder.getInt32(OptionalArgs.size()));
462   Args.append(OptionalArgs.begin(), OptionalArgs.end());
463 
464   CallSite NewCS;
465   if (CS.isCall()) {
466     auto *CI = cast<CallInst>(Inst);
467     CallInst *NewCI = Builder.CreateCall(SetJmp3, Args, OpBundles);
468     NewCI->setTailCallKind(CI->getTailCallKind());
469     NewCS = NewCI;
470   } else {
471     auto *II = cast<InvokeInst>(Inst);
472     NewCS = Builder.CreateInvoke(
473         SetJmp3, II->getNormalDest(), II->getUnwindDest(), Args, OpBundles);
474   }
475   NewCS.setCallingConv(CS.getCallingConv());
476   NewCS.setAttributes(CS.getAttributes());
477   NewCS->setDebugLoc(CS->getDebugLoc());
478 
479   Instruction *NewInst = NewCS.getInstruction();
480   NewInst->takeName(Inst);
481   Inst->replaceAllUsesWith(NewInst);
482   Inst->eraseFromParent();
483 }
484 
485 // Figure out what state we should assign calls in this block.
486 int WinEHStatePass::getBaseStateForBB(
487     DenseMap<BasicBlock *, ColorVector> &BlockColors, WinEHFuncInfo &FuncInfo,
488     BasicBlock *BB) {
489   int BaseState = ParentBaseState;
490   auto &BBColors = BlockColors[BB];
491 
492   assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
493   BasicBlock *FuncletEntryBB = BBColors.front();
494   if (auto *FuncletPad =
495           dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI())) {
496     auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
497     if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
498       BaseState = BaseStateI->second;
499   }
500 
501   return BaseState;
502 }
503 
504 // Calculate the state a call-site is in.
505 int WinEHStatePass::getStateForCallSite(
506     DenseMap<BasicBlock *, ColorVector> &BlockColors, WinEHFuncInfo &FuncInfo,
507     CallSite CS) {
508   if (auto *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
509     // Look up the state number of the EH pad this unwinds to.
510     assert(FuncInfo.InvokeStateMap.count(II) && "invoke has no state!");
511     return FuncInfo.InvokeStateMap[II];
512   }
513   // Possibly throwing call instructions have no actions to take after
514   // an unwind. Ensure they are in the -1 state.
515   return getBaseStateForBB(BlockColors, FuncInfo, CS.getParent());
516 }
517 
518 // Calculate the intersection of all the FinalStates for a BasicBlock's
519 // predecessors.
520 static int getPredState(DenseMap<BasicBlock *, int> &FinalStates, Function &F,
521                         int ParentBaseState, BasicBlock *BB) {
522   // The entry block has no predecessors but we know that the prologue always
523   // sets us up with a fixed state.
524   if (&F.getEntryBlock() == BB)
525     return ParentBaseState;
526 
527   // This is an EH Pad, conservatively report this basic block as overdefined.
528   if (BB->isEHPad())
529     return OverdefinedState;
530 
531   int CommonState = OverdefinedState;
532   for (BasicBlock *PredBB : predecessors(BB)) {
533     // We didn't manage to get a state for one of these predecessors,
534     // conservatively report this basic block as overdefined.
535     auto PredEndState = FinalStates.find(PredBB);
536     if (PredEndState == FinalStates.end())
537       return OverdefinedState;
538 
539     // This code is reachable via exceptional control flow,
540     // conservatively report this basic block as overdefined.
541     if (isa<CatchReturnInst>(PredBB->getTerminator()))
542       return OverdefinedState;
543 
544     int PredState = PredEndState->second;
545     assert(PredState != OverdefinedState &&
546            "overdefined BBs shouldn't be in FinalStates");
547     if (CommonState == OverdefinedState)
548       CommonState = PredState;
549 
550     // At least two predecessors have different FinalStates,
551     // conservatively report this basic block as overdefined.
552     if (CommonState != PredState)
553       return OverdefinedState;
554   }
555 
556   return CommonState;
557 }
558 
559 // Calculate the intersection of all the InitialStates for a BasicBlock's
560 // successors.
561 static int getSuccState(DenseMap<BasicBlock *, int> &InitialStates, Function &F,
562                         int ParentBaseState, BasicBlock *BB) {
563   // This block rejoins normal control flow,
564   // conservatively report this basic block as overdefined.
565   if (isa<CatchReturnInst>(BB->getTerminator()))
566     return OverdefinedState;
567 
568   int CommonState = OverdefinedState;
569   for (BasicBlock *SuccBB : successors(BB)) {
570     // We didn't manage to get a state for one of these predecessors,
571     // conservatively report this basic block as overdefined.
572     auto SuccStartState = InitialStates.find(SuccBB);
573     if (SuccStartState == InitialStates.end())
574       return OverdefinedState;
575 
576     // This is an EH Pad, conservatively report this basic block as overdefined.
577     if (SuccBB->isEHPad())
578       return OverdefinedState;
579 
580     int SuccState = SuccStartState->second;
581     assert(SuccState != OverdefinedState &&
582            "overdefined BBs shouldn't be in FinalStates");
583     if (CommonState == OverdefinedState)
584       CommonState = SuccState;
585 
586     // At least two successors have different InitialStates,
587     // conservatively report this basic block as overdefined.
588     if (CommonState != SuccState)
589       return OverdefinedState;
590   }
591 
592   return CommonState;
593 }
594 
595 bool WinEHStatePass::isStateStoreNeeded(EHPersonality Personality,
596                                         CallSite CS) {
597   if (!CS)
598     return false;
599 
600   // If the function touches memory, it needs a state store.
601   if (isAsynchronousEHPersonality(Personality))
602     return !CS.doesNotAccessMemory();
603 
604   // If the function throws, it needs a state store.
605   return !CS.doesNotThrow();
606 }
607 
608 void WinEHStatePass::addStateStores(Function &F, WinEHFuncInfo &FuncInfo) {
609   // Mark the registration node. The backend needs to know which alloca it is so
610   // that it can recover the original frame pointer.
611   IRBuilder<> Builder(RegNode->getParent(), std::next(RegNode->getIterator()));
612   Value *RegNodeI8 = Builder.CreateBitCast(RegNode, Builder.getInt8PtrTy());
613   Builder.CreateCall(
614       Intrinsic::getDeclaration(TheModule, Intrinsic::x86_seh_ehregnode),
615       {RegNodeI8});
616 
617   // Calculate state numbers.
618   if (isAsynchronousEHPersonality(Personality))
619     calculateSEHStateNumbers(&F, FuncInfo);
620   else
621     calculateWinCXXEHStateNumbers(&F, FuncInfo);
622 
623   // Iterate all the instructions and emit state number stores.
624   DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(F);
625   ReversePostOrderTraversal<Function *> RPOT(&F);
626 
627   // InitialStates yields the state of the first call-site for a BasicBlock.
628   DenseMap<BasicBlock *, int> InitialStates;
629   // FinalStates yields the state of the last call-site for a BasicBlock.
630   DenseMap<BasicBlock *, int> FinalStates;
631   // Worklist used to revisit BasicBlocks with indeterminate
632   // Initial/Final-States.
633   std::deque<BasicBlock *> Worklist;
634   // Fill in InitialStates and FinalStates for BasicBlocks with call-sites.
635   for (BasicBlock *BB : RPOT) {
636     int InitialState = OverdefinedState;
637     int FinalState;
638     if (&F.getEntryBlock() == BB)
639       InitialState = FinalState = ParentBaseState;
640     for (Instruction &I : *BB) {
641       CallSite CS(&I);
642       if (!isStateStoreNeeded(Personality, CS))
643         continue;
644 
645       int State = getStateForCallSite(BlockColors, FuncInfo, CS);
646       if (InitialState == OverdefinedState)
647         InitialState = State;
648       FinalState = State;
649     }
650     // No call-sites in this basic block? That's OK, we will come back to these
651     // in a later pass.
652     if (InitialState == OverdefinedState) {
653       Worklist.push_back(BB);
654       continue;
655     }
656     DEBUG(dbgs() << "X86WinEHState: " << BB->getName()
657                  << " InitialState=" << InitialState << '\n');
658     DEBUG(dbgs() << "X86WinEHState: " << BB->getName()
659                  << " FinalState=" << FinalState << '\n');
660     InitialStates.insert({BB, InitialState});
661     FinalStates.insert({BB, FinalState});
662   }
663 
664   // Try to fill-in InitialStates and FinalStates which have no call-sites.
665   while (!Worklist.empty()) {
666     BasicBlock *BB = Worklist.front();
667     Worklist.pop_front();
668     // This BasicBlock has already been figured out, nothing more we can do.
669     if (InitialStates.count(BB) != 0)
670       continue;
671 
672     int PredState = getPredState(FinalStates, F, ParentBaseState, BB);
673     if (PredState == OverdefinedState)
674       continue;
675 
676     // We successfully inferred this BasicBlock's state via it's predecessors;
677     // enqueue it's successors to see if we can infer their states.
678     InitialStates.insert({BB, PredState});
679     FinalStates.insert({BB, PredState});
680     for (BasicBlock *SuccBB : successors(BB))
681       Worklist.push_back(SuccBB);
682   }
683 
684   // Try to hoist stores from successors.
685   for (BasicBlock *BB : RPOT) {
686     int SuccState = getSuccState(InitialStates, F, ParentBaseState, BB);
687     if (SuccState == OverdefinedState)
688       continue;
689 
690     // Update our FinalState to reflect the common InitialState of our
691     // successors.
692     FinalStates.insert({BB, SuccState});
693   }
694 
695   // Finally, insert state stores before call-sites which transition us to a new
696   // state.
697   for (BasicBlock *BB : RPOT) {
698     auto &BBColors = BlockColors[BB];
699     BasicBlock *FuncletEntryBB = BBColors.front();
700     if (isa<CleanupPadInst>(FuncletEntryBB->getFirstNonPHI()))
701       continue;
702 
703     int PrevState = getPredState(FinalStates, F, ParentBaseState, BB);
704     DEBUG(dbgs() << "X86WinEHState: " << BB->getName()
705                  << " PrevState=" << PrevState << '\n');
706 
707     for (Instruction &I : *BB) {
708       CallSite CS(&I);
709       if (!isStateStoreNeeded(Personality, CS))
710         continue;
711 
712       int State = getStateForCallSite(BlockColors, FuncInfo, CS);
713       if (State != PrevState)
714         insertStateNumberStore(&I, State);
715       PrevState = State;
716     }
717 
718     // We might have hoisted a state store into this block, emit it now.
719     auto EndState = FinalStates.find(BB);
720     if (EndState != FinalStates.end())
721       if (EndState->second != PrevState)
722         insertStateNumberStore(BB->getTerminator(), EndState->second);
723   }
724 
725   SmallVector<CallSite, 1> SetJmp3CallSites;
726   for (BasicBlock *BB : RPOT) {
727     for (Instruction &I : *BB) {
728       CallSite CS(&I);
729       if (!CS)
730         continue;
731       if (CS.getCalledValue()->stripPointerCasts() !=
732           SetJmp3->stripPointerCasts())
733         continue;
734 
735       SetJmp3CallSites.push_back(CS);
736     }
737   }
738 
739   for (CallSite CS : SetJmp3CallSites) {
740     auto &BBColors = BlockColors[CS->getParent()];
741     BasicBlock *FuncletEntryBB = BBColors.front();
742     bool InCleanup = isa<CleanupPadInst>(FuncletEntryBB->getFirstNonPHI());
743 
744     IRBuilder<> Builder(CS.getInstruction());
745     Value *State;
746     if (InCleanup) {
747       Value *StateField =
748           Builder.CreateStructGEP(nullptr, RegNode, StateFieldIndex);
749       State = Builder.CreateLoad(StateField);
750     } else {
751       State = Builder.getInt32(getStateForCallSite(BlockColors, FuncInfo, CS));
752     }
753     rewriteSetJmpCallSite(Builder, F, CS, State);
754   }
755 }
756 
757 void WinEHStatePass::insertStateNumberStore(Instruction *IP, int State) {
758   IRBuilder<> Builder(IP);
759   Value *StateField =
760       Builder.CreateStructGEP(nullptr, RegNode, StateFieldIndex);
761   Builder.CreateStore(Builder.getInt32(State), StateField);
762 }
763