xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/WinEHPrepare.cpp (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
1 //===-- WinEHPrepare - Prepare exception handling for code generation ---===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass lowers LLVM IR exception handling into something closer to what the
10 // backend wants for functions using a personality function from a runtime
11 // provided by MSVC. Functions with other personality functions are left alone
12 // and may be prepared by other passes. In particular, all supported MSVC
13 // personality functions require cleanup code to be outlined, and the C++
14 // personality requires catch handler code to be outlined.
15 //
16 //===----------------------------------------------------------------------===//
17 
18 #include "llvm/CodeGen/WinEHPrepare.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/MapVector.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/Passes.h"
24 #include "llvm/CodeGen/WinEHFuncInfo.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/EHPersonalities.h"
27 #include "llvm/IR/Instructions.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/IR/Verifier.h"
30 #include "llvm/InitializePasses.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Support/CommandLine.h"
33 #include "llvm/Support/Debug.h"
34 #include "llvm/Support/raw_ostream.h"
35 #include "llvm/TargetParser/Triple.h"
36 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
37 #include "llvm/Transforms/Utils/Cloning.h"
38 #include "llvm/Transforms/Utils/Local.h"
39 #include "llvm/Transforms/Utils/SSAUpdater.h"
40 
41 using namespace llvm;
42 
43 #define DEBUG_TYPE "win-eh-prepare"
44 
45 static cl::opt<bool> DisableDemotion(
46     "disable-demotion", cl::Hidden,
47     cl::desc(
48         "Clone multicolor basic blocks but do not demote cross scopes"),
49     cl::init(false));
50 
51 static cl::opt<bool> DisableCleanups(
52     "disable-cleanups", cl::Hidden,
53     cl::desc("Do not remove implausible terminators or other similar cleanups"),
54     cl::init(false));
55 
56 // TODO: Remove this option when we fully migrate to new pass manager
57 static cl::opt<bool> DemoteCatchSwitchPHIOnlyOpt(
58     "demote-catchswitch-only", cl::Hidden,
59     cl::desc("Demote catchswitch BBs only (for wasm EH)"), cl::init(false));
60 
61 namespace {
62 
63 class WinEHPrepareImpl {
64 public:
WinEHPrepareImpl(bool DemoteCatchSwitchPHIOnly)65   WinEHPrepareImpl(bool DemoteCatchSwitchPHIOnly)
66       : DemoteCatchSwitchPHIOnly(DemoteCatchSwitchPHIOnly) {}
67 
68   bool runOnFunction(Function &Fn);
69 
70 private:
71   void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
72   void
73   insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
74                  SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
75   AllocaInst *insertPHILoads(PHINode *PN, Function &F);
76   void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
77                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
78   bool prepareExplicitEH(Function &F);
79   void colorFunclets(Function &F);
80 
81   void demotePHIsOnFunclets(Function &F, bool DemoteCatchSwitchPHIOnly);
82   void cloneCommonBlocks(Function &F);
83   void removeImplausibleInstructions(Function &F);
84   void cleanupPreparedFunclets(Function &F);
85   void verifyPreparedFunclets(Function &F);
86 
87   bool DemoteCatchSwitchPHIOnly;
88 
89   // All fields are reset by runOnFunction.
90   EHPersonality Personality = EHPersonality::Unknown;
91 
92   const DataLayout *DL = nullptr;
93   DenseMap<BasicBlock *, ColorVector> BlockColors;
94   MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
95 };
96 
97 class WinEHPrepare : public FunctionPass {
98   bool DemoteCatchSwitchPHIOnly;
99 
100 public:
101   static char ID; // Pass identification, replacement for typeid.
102 
WinEHPrepare(bool DemoteCatchSwitchPHIOnly=false)103   WinEHPrepare(bool DemoteCatchSwitchPHIOnly = false)
104       : FunctionPass(ID), DemoteCatchSwitchPHIOnly(DemoteCatchSwitchPHIOnly) {}
105 
getPassName() const106   StringRef getPassName() const override {
107     return "Windows exception handling preparation";
108   }
109 
runOnFunction(Function & Fn)110   bool runOnFunction(Function &Fn) override {
111     return WinEHPrepareImpl(DemoteCatchSwitchPHIOnly).runOnFunction(Fn);
112   }
113 };
114 
115 } // end anonymous namespace
116 
run(Function & F,FunctionAnalysisManager &)117 PreservedAnalyses WinEHPreparePass::run(Function &F,
118                                         FunctionAnalysisManager &) {
119   bool Changed = WinEHPrepareImpl(DemoteCatchSwitchPHIOnly).runOnFunction(F);
120   return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
121 }
122 
123 char WinEHPrepare::ID = 0;
124 INITIALIZE_PASS(WinEHPrepare, DEBUG_TYPE, "Prepare Windows exceptions", false,
125                 false)
126 
createWinEHPass(bool DemoteCatchSwitchPHIOnly)127 FunctionPass *llvm::createWinEHPass(bool DemoteCatchSwitchPHIOnly) {
128   return new WinEHPrepare(DemoteCatchSwitchPHIOnly);
129 }
130 
runOnFunction(Function & Fn)131 bool WinEHPrepareImpl::runOnFunction(Function &Fn) {
132   if (!Fn.hasPersonalityFn())
133     return false;
134 
135   // Classify the personality to see what kind of preparation we need.
136   Personality = classifyEHPersonality(Fn.getPersonalityFn());
137 
138   // Do nothing if this is not a scope-based personality.
139   if (!isScopedEHPersonality(Personality))
140     return false;
141 
142   DL = &Fn.getDataLayout();
143   return prepareExplicitEH(Fn);
144 }
145 
addUnwindMapEntry(WinEHFuncInfo & FuncInfo,int ToState,const BasicBlock * BB)146 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
147                              const BasicBlock *BB) {
148   CxxUnwindMapEntry UME;
149   UME.ToState = ToState;
150   UME.Cleanup = BB;
151   FuncInfo.CxxUnwindMap.push_back(UME);
152   return FuncInfo.getLastStateNumber();
153 }
154 
addTryBlockMapEntry(WinEHFuncInfo & FuncInfo,int TryLow,int TryHigh,int CatchHigh,ArrayRef<const CatchPadInst * > Handlers)155 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
156                                 int TryHigh, int CatchHigh,
157                                 ArrayRef<const CatchPadInst *> Handlers) {
158   WinEHTryBlockMapEntry TBME;
159   TBME.TryLow = TryLow;
160   TBME.TryHigh = TryHigh;
161   TBME.CatchHigh = CatchHigh;
162   assert(TBME.TryLow <= TBME.TryHigh);
163   for (const CatchPadInst *CPI : Handlers) {
164     WinEHHandlerType HT;
165     Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
166     if (TypeInfo->isNullValue())
167       HT.TypeDescriptor = nullptr;
168     else
169       HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
170     HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
171     HT.Handler = CPI->getParent();
172     if (auto *AI =
173             dyn_cast<AllocaInst>(CPI->getArgOperand(2)->stripPointerCasts()))
174       HT.CatchObj.Alloca = AI;
175     else
176       HT.CatchObj.Alloca = nullptr;
177     TBME.HandlerArray.push_back(HT);
178   }
179   FuncInfo.TryBlockMap.push_back(TBME);
180 }
181 
getCleanupRetUnwindDest(const CleanupPadInst * CleanupPad)182 static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
183   for (const User *U : CleanupPad->users())
184     if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
185       return CRI->getUnwindDest();
186   return nullptr;
187 }
188 
calculateStateNumbersForInvokes(const Function * Fn,WinEHFuncInfo & FuncInfo)189 static void calculateStateNumbersForInvokes(const Function *Fn,
190                                             WinEHFuncInfo &FuncInfo) {
191   auto *F = const_cast<Function *>(Fn);
192   DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
193   for (BasicBlock &BB : *F) {
194     auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
195     if (!II)
196       continue;
197 
198     auto &BBColors = BlockColors[&BB];
199     assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
200     BasicBlock *FuncletEntryBB = BBColors.front();
201 
202     BasicBlock *FuncletUnwindDest;
203     auto *FuncletPad =
204         dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
205     assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
206     if (!FuncletPad)
207       FuncletUnwindDest = nullptr;
208     else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
209       FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
210     else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
211       FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
212     else
213       llvm_unreachable("unexpected funclet pad!");
214 
215     BasicBlock *InvokeUnwindDest = II->getUnwindDest();
216     int BaseState = -1;
217     if (FuncletUnwindDest == InvokeUnwindDest) {
218       auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
219       if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
220         BaseState = BaseStateI->second;
221     }
222 
223     if (BaseState != -1) {
224       FuncInfo.InvokeStateMap[II] = BaseState;
225     } else {
226       Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
227       assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
228       FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
229     }
230   }
231 }
232 
233 // See comments below for calculateSEHStateForAsynchEH().
234 // State - incoming State of normal paths
235 struct WorkItem {
236   const BasicBlock *Block;
237   int State;
WorkItemWorkItem238   WorkItem(const BasicBlock *BB, int St) {
239     Block = BB;
240     State = St;
241   }
242 };
calculateCXXStateForAsynchEH(const BasicBlock * BB,int State,WinEHFuncInfo & EHInfo)243 void llvm::calculateCXXStateForAsynchEH(const BasicBlock *BB, int State,
244                                         WinEHFuncInfo &EHInfo) {
245   SmallVector<struct WorkItem *, 8> WorkList;
246   struct WorkItem *WI = new WorkItem(BB, State);
247   WorkList.push_back(WI);
248 
249   while (!WorkList.empty()) {
250     WI = WorkList.pop_back_val();
251     const BasicBlock *BB = WI->Block;
252     int State = WI->State;
253     delete WI;
254     if (EHInfo.BlockToStateMap.count(BB) && EHInfo.BlockToStateMap[BB] <= State)
255       continue; // skip blocks already visited by lower State
256 
257     const llvm::Instruction *I = BB->getFirstNonPHI();
258     const llvm::Instruction *TI = BB->getTerminator();
259     if (I->isEHPad())
260       State = EHInfo.EHPadStateMap[I];
261     EHInfo.BlockToStateMap[BB] = State; // Record state, also flag visiting
262 
263     if ((isa<CleanupReturnInst>(TI) || isa<CatchReturnInst>(TI)) && State > 0) {
264       // Retrive the new State
265       State = EHInfo.CxxUnwindMap[State].ToState; // Retrive next State
266     } else if (isa<InvokeInst>(TI)) {
267       auto *Call = cast<CallBase>(TI);
268       const Function *Fn = Call->getCalledFunction();
269       if (Fn && Fn->isIntrinsic() &&
270           (Fn->getIntrinsicID() == Intrinsic::seh_scope_begin ||
271            Fn->getIntrinsicID() == Intrinsic::seh_try_begin))
272         // Retrive the new State from seh_scope_begin
273         State = EHInfo.InvokeStateMap[cast<InvokeInst>(TI)];
274       else if (Fn && Fn->isIntrinsic() &&
275                (Fn->getIntrinsicID() == Intrinsic::seh_scope_end ||
276                 Fn->getIntrinsicID() == Intrinsic::seh_try_end)) {
277         // In case of conditional ctor, let's retrieve State from Invoke
278         State = EHInfo.InvokeStateMap[cast<InvokeInst>(TI)];
279         // end of current state, retrive new state from UnwindMap
280         State = EHInfo.CxxUnwindMap[State].ToState;
281       }
282     }
283     // Continue push successors into worklist
284     for (auto *SuccBB : successors(BB)) {
285       WI = new WorkItem(SuccBB, State);
286       WorkList.push_back(WI);
287     }
288   }
289 }
290 
291 // The central theory of this routine is based on the following:
292 //   A _try scope is always a SEME (Single Entry Multiple Exits) region
293 //     as jumping into a _try is not allowed
294 //   The single entry must start with a seh_try_begin() invoke with a
295 //     correct State number that is the initial state of the SEME.
296 //   Through control-flow, state number is propagated into all blocks.
297 //   Side exits marked by seh_try_end() will unwind to parent state via
298 //     existing SEHUnwindMap[].
299 //   Side exits can ONLY jump into parent scopes (lower state number).
300 //   Thus, when a block succeeds various states from its predecessors,
301 //     the lowest State trumphs others.
302 //   If some exits flow to unreachable, propagation on those paths terminate,
303 //     not affecting remaining blocks.
calculateSEHStateForAsynchEH(const BasicBlock * BB,int State,WinEHFuncInfo & EHInfo)304 void llvm::calculateSEHStateForAsynchEH(const BasicBlock *BB, int State,
305                                         WinEHFuncInfo &EHInfo) {
306   SmallVector<struct WorkItem *, 8> WorkList;
307   struct WorkItem *WI = new WorkItem(BB, State);
308   WorkList.push_back(WI);
309 
310   while (!WorkList.empty()) {
311     WI = WorkList.pop_back_val();
312     const BasicBlock *BB = WI->Block;
313     int State = WI->State;
314     delete WI;
315     if (EHInfo.BlockToStateMap.count(BB) && EHInfo.BlockToStateMap[BB] <= State)
316       continue; // skip blocks already visited by lower State
317 
318     const llvm::Instruction *I = BB->getFirstNonPHI();
319     const llvm::Instruction *TI = BB->getTerminator();
320     if (I->isEHPad())
321       State = EHInfo.EHPadStateMap[I];
322     EHInfo.BlockToStateMap[BB] = State; // Record state
323 
324     if (isa<CatchPadInst>(I) && isa<CatchReturnInst>(TI)) {
325       const Constant *FilterOrNull = cast<Constant>(
326           cast<CatchPadInst>(I)->getArgOperand(0)->stripPointerCasts());
327       const Function *Filter = dyn_cast<Function>(FilterOrNull);
328       if (!Filter || !Filter->getName().starts_with("__IsLocalUnwind"))
329         State = EHInfo.SEHUnwindMap[State].ToState; // Retrive next State
330     } else if ((isa<CleanupReturnInst>(TI) || isa<CatchReturnInst>(TI)) &&
331                State > 0) {
332       // Retrive the new State.
333       State = EHInfo.SEHUnwindMap[State].ToState; // Retrive next State
334     } else if (isa<InvokeInst>(TI)) {
335       auto *Call = cast<CallBase>(TI);
336       const Function *Fn = Call->getCalledFunction();
337       if (Fn && Fn->isIntrinsic() &&
338           Fn->getIntrinsicID() == Intrinsic::seh_try_begin)
339         // Retrive the new State from seh_try_begin
340         State = EHInfo.InvokeStateMap[cast<InvokeInst>(TI)];
341       else if (Fn && Fn->isIntrinsic() &&
342                Fn->getIntrinsicID() == Intrinsic::seh_try_end)
343         // end of current state, retrive new state from UnwindMap
344         State = EHInfo.SEHUnwindMap[State].ToState;
345     }
346     // Continue push successors into worklist
347     for (auto *SuccBB : successors(BB)) {
348       WI = new WorkItem(SuccBB, State);
349       WorkList.push_back(WI);
350     }
351   }
352 }
353 
354 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
355 // to. If the unwind edge came from an invoke, return null.
getEHPadFromPredecessor(const BasicBlock * BB,Value * ParentPad)356 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
357                                                  Value *ParentPad) {
358   const Instruction *TI = BB->getTerminator();
359   if (isa<InvokeInst>(TI))
360     return nullptr;
361   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
362     if (CatchSwitch->getParentPad() != ParentPad)
363       return nullptr;
364     return BB;
365   }
366   assert(!TI->isEHPad() && "unexpected EHPad!");
367   auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
368   if (CleanupPad->getParentPad() != ParentPad)
369     return nullptr;
370   return CleanupPad->getParent();
371 }
372 
373 // Starting from a EHPad, Backward walk through control-flow graph
374 // to produce two primary outputs:
375 //      FuncInfo.EHPadStateMap[] and FuncInfo.CxxUnwindMap[]
calculateCXXStateNumbers(WinEHFuncInfo & FuncInfo,const Instruction * FirstNonPHI,int ParentState)376 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
377                                      const Instruction *FirstNonPHI,
378                                      int ParentState) {
379   const BasicBlock *BB = FirstNonPHI->getParent();
380   assert(BB->isEHPad() && "not a funclet!");
381 
382   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
383     assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
384            "shouldn't revist catch funclets!");
385 
386     SmallVector<const CatchPadInst *, 2> Handlers;
387     for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
388       auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
389       Handlers.push_back(CatchPad);
390     }
391     int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
392     FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
393     for (const BasicBlock *PredBlock : predecessors(BB))
394       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
395                                                CatchSwitch->getParentPad())))
396         calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
397                                  TryLow);
398     int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
399 
400     // catchpads are separate funclets in C++ EH due to the way rethrow works.
401     int TryHigh = CatchLow - 1;
402 
403     // MSVC FrameHandler3/4 on x64&Arm64 expect Catch Handlers in $tryMap$
404     //  stored in pre-order (outer first, inner next), not post-order
405     //  Add to map here.  Fix the CatchHigh after children are processed
406     const Module *Mod = BB->getParent()->getParent();
407     bool IsPreOrder = Triple(Mod->getTargetTriple()).isArch64Bit();
408     if (IsPreOrder)
409       addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchLow, Handlers);
410     unsigned TBMEIdx = FuncInfo.TryBlockMap.size() - 1;
411 
412     for (const auto *CatchPad : Handlers) {
413       FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
414       FuncInfo.EHPadStateMap[CatchPad] = CatchLow;
415       for (const User *U : CatchPad->users()) {
416         const auto *UserI = cast<Instruction>(U);
417         if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {
418           BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();
419           if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
420             calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
421         }
422         if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {
423           BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);
424           // If a nested cleanup pad reports a null unwind destination and the
425           // enclosing catch pad doesn't it must be post-dominated by an
426           // unreachable instruction.
427           if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
428             calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
429         }
430       }
431     }
432     int CatchHigh = FuncInfo.getLastStateNumber();
433     // Now child Catches are processed, update CatchHigh
434     if (IsPreOrder)
435       FuncInfo.TryBlockMap[TBMEIdx].CatchHigh = CatchHigh;
436     else // PostOrder
437       addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
438 
439     LLVM_DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
440     LLVM_DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh
441                       << '\n');
442     LLVM_DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
443                       << '\n');
444   } else {
445     auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
446 
447     // It's possible for a cleanup to be visited twice: it might have multiple
448     // cleanupret instructions.
449     if (FuncInfo.EHPadStateMap.count(CleanupPad))
450       return;
451 
452     int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
453     FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
454     LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
455                       << BB->getName() << '\n');
456     for (const BasicBlock *PredBlock : predecessors(BB)) {
457       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
458                                                CleanupPad->getParentPad()))) {
459         calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
460                                  CleanupState);
461       }
462     }
463     for (const User *U : CleanupPad->users()) {
464       const auto *UserI = cast<Instruction>(U);
465       if (UserI->isEHPad())
466         report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
467                            "contain exceptional actions");
468     }
469   }
470 }
471 
addSEHExcept(WinEHFuncInfo & FuncInfo,int ParentState,const Function * Filter,const BasicBlock * Handler)472 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
473                         const Function *Filter, const BasicBlock *Handler) {
474   SEHUnwindMapEntry Entry;
475   Entry.ToState = ParentState;
476   Entry.IsFinally = false;
477   Entry.Filter = Filter;
478   Entry.Handler = Handler;
479   FuncInfo.SEHUnwindMap.push_back(Entry);
480   return FuncInfo.SEHUnwindMap.size() - 1;
481 }
482 
addSEHFinally(WinEHFuncInfo & FuncInfo,int ParentState,const BasicBlock * Handler)483 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
484                          const BasicBlock *Handler) {
485   SEHUnwindMapEntry Entry;
486   Entry.ToState = ParentState;
487   Entry.IsFinally = true;
488   Entry.Filter = nullptr;
489   Entry.Handler = Handler;
490   FuncInfo.SEHUnwindMap.push_back(Entry);
491   return FuncInfo.SEHUnwindMap.size() - 1;
492 }
493 
494 // Starting from a EHPad, Backward walk through control-flow graph
495 // to produce two primary outputs:
496 //      FuncInfo.EHPadStateMap[] and FuncInfo.SEHUnwindMap[]
calculateSEHStateNumbers(WinEHFuncInfo & FuncInfo,const Instruction * FirstNonPHI,int ParentState)497 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
498                                      const Instruction *FirstNonPHI,
499                                      int ParentState) {
500   const BasicBlock *BB = FirstNonPHI->getParent();
501   assert(BB->isEHPad() && "no a funclet!");
502 
503   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
504     assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
505            "shouldn't revist catch funclets!");
506 
507     // Extract the filter function and the __except basic block and create a
508     // state for them.
509     assert(CatchSwitch->getNumHandlers() == 1 &&
510            "SEH doesn't have multiple handlers per __try");
511     const auto *CatchPad =
512         cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
513     const BasicBlock *CatchPadBB = CatchPad->getParent();
514     const Constant *FilterOrNull =
515         cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
516     const Function *Filter = dyn_cast<Function>(FilterOrNull);
517     assert((Filter || FilterOrNull->isNullValue()) &&
518            "unexpected filter value");
519     int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
520 
521     // Everything in the __try block uses TryState as its parent state.
522     FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
523     FuncInfo.EHPadStateMap[CatchPad] = TryState;
524     LLVM_DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
525                       << CatchPadBB->getName() << '\n');
526     for (const BasicBlock *PredBlock : predecessors(BB))
527       if ((PredBlock = getEHPadFromPredecessor(PredBlock,
528                                                CatchSwitch->getParentPad())))
529         calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
530                                  TryState);
531 
532     // Everything in the __except block unwinds to ParentState, just like code
533     // outside the __try.
534     for (const User *U : CatchPad->users()) {
535       const auto *UserI = cast<Instruction>(U);
536       if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {
537         BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();
538         if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
539           calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
540       }
541       if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {
542         BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);
543         // If a nested cleanup pad reports a null unwind destination and the
544         // enclosing catch pad doesn't it must be post-dominated by an
545         // unreachable instruction.
546         if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())
547           calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
548       }
549     }
550   } else {
551     auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
552 
553     // It's possible for a cleanup to be visited twice: it might have multiple
554     // cleanupret instructions.
555     if (FuncInfo.EHPadStateMap.count(CleanupPad))
556       return;
557 
558     int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
559     FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
560     LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
561                       << BB->getName() << '\n');
562     for (const BasicBlock *PredBlock : predecessors(BB))
563       if ((PredBlock =
564                getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
565         calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
566                                  CleanupState);
567     for (const User *U : CleanupPad->users()) {
568       const auto *UserI = cast<Instruction>(U);
569       if (UserI->isEHPad())
570         report_fatal_error("Cleanup funclets for the SEH personality cannot "
571                            "contain exceptional actions");
572     }
573   }
574 }
575 
isTopLevelPadForMSVC(const Instruction * EHPad)576 static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
577   if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
578     return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
579            CatchSwitch->unwindsToCaller();
580   if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
581     return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
582            getCleanupRetUnwindDest(CleanupPad) == nullptr;
583   if (isa<CatchPadInst>(EHPad))
584     return false;
585   llvm_unreachable("unexpected EHPad!");
586 }
587 
calculateSEHStateNumbers(const Function * Fn,WinEHFuncInfo & FuncInfo)588 void llvm::calculateSEHStateNumbers(const Function *Fn,
589                                     WinEHFuncInfo &FuncInfo) {
590   // Don't compute state numbers twice.
591   if (!FuncInfo.SEHUnwindMap.empty())
592     return;
593 
594   for (const BasicBlock &BB : *Fn) {
595     if (!BB.isEHPad())
596       continue;
597     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
598     if (!isTopLevelPadForMSVC(FirstNonPHI))
599       continue;
600     ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
601   }
602 
603   calculateStateNumbersForInvokes(Fn, FuncInfo);
604 
605   bool IsEHa = Fn->getParent()->getModuleFlag("eh-asynch");
606   if (IsEHa) {
607     const BasicBlock *EntryBB = &(Fn->getEntryBlock());
608     calculateSEHStateForAsynchEH(EntryBB, -1, FuncInfo);
609   }
610 }
611 
calculateWinCXXEHStateNumbers(const Function * Fn,WinEHFuncInfo & FuncInfo)612 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
613                                          WinEHFuncInfo &FuncInfo) {
614   // Return if it's already been done.
615   if (!FuncInfo.EHPadStateMap.empty())
616     return;
617 
618   for (const BasicBlock &BB : *Fn) {
619     if (!BB.isEHPad())
620       continue;
621     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
622     if (!isTopLevelPadForMSVC(FirstNonPHI))
623       continue;
624     calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
625   }
626 
627   calculateStateNumbersForInvokes(Fn, FuncInfo);
628 
629   bool IsEHa = Fn->getParent()->getModuleFlag("eh-asynch");
630   if (IsEHa) {
631     const BasicBlock *EntryBB = &(Fn->getEntryBlock());
632     calculateCXXStateForAsynchEH(EntryBB, -1, FuncInfo);
633   }
634 }
635 
addClrEHHandler(WinEHFuncInfo & FuncInfo,int HandlerParentState,int TryParentState,ClrHandlerType HandlerType,uint32_t TypeToken,const BasicBlock * Handler)636 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int HandlerParentState,
637                            int TryParentState, ClrHandlerType HandlerType,
638                            uint32_t TypeToken, const BasicBlock *Handler) {
639   ClrEHUnwindMapEntry Entry;
640   Entry.HandlerParentState = HandlerParentState;
641   Entry.TryParentState = TryParentState;
642   Entry.Handler = Handler;
643   Entry.HandlerType = HandlerType;
644   Entry.TypeToken = TypeToken;
645   FuncInfo.ClrEHUnwindMap.push_back(Entry);
646   return FuncInfo.ClrEHUnwindMap.size() - 1;
647 }
648 
calculateClrEHStateNumbers(const Function * Fn,WinEHFuncInfo & FuncInfo)649 void llvm::calculateClrEHStateNumbers(const Function *Fn,
650                                       WinEHFuncInfo &FuncInfo) {
651   // Return if it's already been done.
652   if (!FuncInfo.EHPadStateMap.empty())
653     return;
654 
655   // This numbering assigns one state number to each catchpad and cleanuppad.
656   // It also computes two tree-like relations over states:
657   // 1) Each state has a "HandlerParentState", which is the state of the next
658   //    outer handler enclosing this state's handler (same as nearest ancestor
659   //    per the ParentPad linkage on EH pads, but skipping over catchswitches).
660   // 2) Each state has a "TryParentState", which:
661   //    a) for a catchpad that's not the last handler on its catchswitch, is
662   //       the state of the next catchpad on that catchswitch
663   //    b) for all other pads, is the state of the pad whose try region is the
664   //       next outer try region enclosing this state's try region.  The "try
665   //       regions are not present as such in the IR, but will be inferred
666   //       based on the placement of invokes and pads which reach each other
667   //       by exceptional exits
668   // Catchswitches do not get their own states, but each gets mapped to the
669   // state of its first catchpad.
670 
671   // Step one: walk down from outermost to innermost funclets, assigning each
672   // catchpad and cleanuppad a state number.  Add an entry to the
673   // ClrEHUnwindMap for each state, recording its HandlerParentState and
674   // handler attributes.  Record the TryParentState as well for each catchpad
675   // that's not the last on its catchswitch, but initialize all other entries'
676   // TryParentStates to a sentinel -1 value that the next pass will update.
677 
678   // Seed a worklist with pads that have no parent.
679   SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
680   for (const BasicBlock &BB : *Fn) {
681     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
682     const Value *ParentPad;
683     if (const auto *CPI = dyn_cast<CleanupPadInst>(FirstNonPHI))
684       ParentPad = CPI->getParentPad();
685     else if (const auto *CSI = dyn_cast<CatchSwitchInst>(FirstNonPHI))
686       ParentPad = CSI->getParentPad();
687     else
688       continue;
689     if (isa<ConstantTokenNone>(ParentPad))
690       Worklist.emplace_back(FirstNonPHI, -1);
691   }
692 
693   // Use the worklist to visit all pads, from outer to inner.  Record
694   // HandlerParentState for all pads.  Record TryParentState only for catchpads
695   // that aren't the last on their catchswitch (setting all other entries'
696   // TryParentStates to an initial value of -1).  This loop is also responsible
697   // for setting the EHPadStateMap entry for all catchpads, cleanuppads, and
698   // catchswitches.
699   while (!Worklist.empty()) {
700     const Instruction *Pad;
701     int HandlerParentState;
702     std::tie(Pad, HandlerParentState) = Worklist.pop_back_val();
703 
704     if (const auto *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
705       // Create the entry for this cleanup with the appropriate handler
706       // properties.  Finally and fault handlers are distinguished by arity.
707       ClrHandlerType HandlerType =
708           (Cleanup->arg_size() ? ClrHandlerType::Fault
709                                : ClrHandlerType::Finally);
710       int CleanupState = addClrEHHandler(FuncInfo, HandlerParentState, -1,
711                                          HandlerType, 0, Pad->getParent());
712       // Queue any child EH pads on the worklist.
713       for (const User *U : Cleanup->users())
714         if (const auto *I = dyn_cast<Instruction>(U))
715           if (I->isEHPad())
716             Worklist.emplace_back(I, CleanupState);
717       // Remember this pad's state.
718       FuncInfo.EHPadStateMap[Cleanup] = CleanupState;
719     } else {
720       // Walk the handlers of this catchswitch in reverse order since all but
721       // the last need to set the following one as its TryParentState.
722       const auto *CatchSwitch = cast<CatchSwitchInst>(Pad);
723       int CatchState = -1, FollowerState = -1;
724       SmallVector<const BasicBlock *, 4> CatchBlocks(CatchSwitch->handlers());
725       for (const BasicBlock *CatchBlock : llvm::reverse(CatchBlocks)) {
726         // Create the entry for this catch with the appropriate handler
727         // properties.
728         const auto *Catch = cast<CatchPadInst>(CatchBlock->getFirstNonPHI());
729         uint32_t TypeToken = static_cast<uint32_t>(
730             cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
731         CatchState =
732             addClrEHHandler(FuncInfo, HandlerParentState, FollowerState,
733                             ClrHandlerType::Catch, TypeToken, CatchBlock);
734         // Queue any child EH pads on the worklist.
735         for (const User *U : Catch->users())
736           if (const auto *I = dyn_cast<Instruction>(U))
737             if (I->isEHPad())
738               Worklist.emplace_back(I, CatchState);
739         // Remember this catch's state.
740         FuncInfo.EHPadStateMap[Catch] = CatchState;
741         FollowerState = CatchState;
742       }
743       // Associate the catchswitch with the state of its first catch.
744       assert(CatchSwitch->getNumHandlers());
745       FuncInfo.EHPadStateMap[CatchSwitch] = CatchState;
746     }
747   }
748 
749   // Step two: record the TryParentState of each state.  For cleanuppads that
750   // don't have cleanuprets, we may need to infer this from their child pads,
751   // so visit pads in descendant-most to ancestor-most order.
752   for (ClrEHUnwindMapEntry &Entry : llvm::reverse(FuncInfo.ClrEHUnwindMap)) {
753     const Instruction *Pad =
754         cast<const BasicBlock *>(Entry.Handler)->getFirstNonPHI();
755     // For most pads, the TryParentState is the state associated with the
756     // unwind dest of exceptional exits from it.
757     const BasicBlock *UnwindDest;
758     if (const auto *Catch = dyn_cast<CatchPadInst>(Pad)) {
759       // If a catch is not the last in its catchswitch, its TryParentState is
760       // the state associated with the next catch in the switch, even though
761       // that's not the unwind dest of exceptions escaping the catch.  Those
762       // cases were already assigned a TryParentState in the first pass, so
763       // skip them.
764       if (Entry.TryParentState != -1)
765         continue;
766       // Otherwise, get the unwind dest from the catchswitch.
767       UnwindDest = Catch->getCatchSwitch()->getUnwindDest();
768     } else {
769       const auto *Cleanup = cast<CleanupPadInst>(Pad);
770       UnwindDest = nullptr;
771       for (const User *U : Cleanup->users()) {
772         if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {
773           // Common and unambiguous case -- cleanupret indicates cleanup's
774           // unwind dest.
775           UnwindDest = CleanupRet->getUnwindDest();
776           break;
777         }
778 
779         // Get an unwind dest for the user
780         const BasicBlock *UserUnwindDest = nullptr;
781         if (auto *Invoke = dyn_cast<InvokeInst>(U)) {
782           UserUnwindDest = Invoke->getUnwindDest();
783         } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(U)) {
784           UserUnwindDest = CatchSwitch->getUnwindDest();
785         } else if (auto *ChildCleanup = dyn_cast<CleanupPadInst>(U)) {
786           int UserState = FuncInfo.EHPadStateMap[ChildCleanup];
787           int UserUnwindState =
788               FuncInfo.ClrEHUnwindMap[UserState].TryParentState;
789           if (UserUnwindState != -1)
790             UserUnwindDest = cast<const BasicBlock *>(
791                 FuncInfo.ClrEHUnwindMap[UserUnwindState].Handler);
792         }
793 
794         // Not having an unwind dest for this user might indicate that it
795         // doesn't unwind, so can't be taken as proof that the cleanup itself
796         // may unwind to caller (see e.g. SimplifyUnreachable and
797         // RemoveUnwindEdge).
798         if (!UserUnwindDest)
799           continue;
800 
801         // Now we have an unwind dest for the user, but we need to see if it
802         // unwinds all the way out of the cleanup or if it stays within it.
803         const Instruction *UserUnwindPad = UserUnwindDest->getFirstNonPHI();
804         const Value *UserUnwindParent;
805         if (auto *CSI = dyn_cast<CatchSwitchInst>(UserUnwindPad))
806           UserUnwindParent = CSI->getParentPad();
807         else
808           UserUnwindParent =
809               cast<CleanupPadInst>(UserUnwindPad)->getParentPad();
810 
811         // The unwind stays within the cleanup iff it targets a child of the
812         // cleanup.
813         if (UserUnwindParent == Cleanup)
814           continue;
815 
816         // This unwind exits the cleanup, so its dest is the cleanup's dest.
817         UnwindDest = UserUnwindDest;
818         break;
819       }
820     }
821 
822     // Record the state of the unwind dest as the TryParentState.
823     int UnwindDestState;
824 
825     // If UnwindDest is null at this point, either the pad in question can
826     // be exited by unwind to caller, or it cannot be exited by unwind.  In
827     // either case, reporting such cases as unwinding to caller is correct.
828     // This can lead to EH tables that "look strange" -- if this pad's is in
829     // a parent funclet which has other children that do unwind to an enclosing
830     // pad, the try region for this pad will be missing the "duplicate" EH
831     // clause entries that you'd expect to see covering the whole parent.  That
832     // should be benign, since the unwind never actually happens.  If it were
833     // an issue, we could add a subsequent pass that pushes unwind dests down
834     // from parents that have them to children that appear to unwind to caller.
835     if (!UnwindDest) {
836       UnwindDestState = -1;
837     } else {
838       UnwindDestState = FuncInfo.EHPadStateMap[UnwindDest->getFirstNonPHI()];
839     }
840 
841     Entry.TryParentState = UnwindDestState;
842   }
843 
844   // Step three: transfer information from pads to invokes.
845   calculateStateNumbersForInvokes(Fn, FuncInfo);
846 }
847 
colorFunclets(Function & F)848 void WinEHPrepareImpl::colorFunclets(Function &F) {
849   BlockColors = colorEHFunclets(F);
850 
851   // Invert the map from BB to colors to color to BBs.
852   for (BasicBlock &BB : F) {
853     ColorVector &Colors = BlockColors[&BB];
854     for (BasicBlock *Color : Colors)
855       FuncletBlocks[Color].push_back(&BB);
856   }
857 }
858 
demotePHIsOnFunclets(Function & F,bool DemoteCatchSwitchPHIOnly)859 void WinEHPrepareImpl::demotePHIsOnFunclets(Function &F,
860                                             bool DemoteCatchSwitchPHIOnly) {
861   // Strip PHI nodes off of EH pads.
862   SmallVector<PHINode *, 16> PHINodes;
863   for (BasicBlock &BB : make_early_inc_range(F)) {
864     if (!BB.isEHPad())
865       continue;
866     if (DemoteCatchSwitchPHIOnly && !isa<CatchSwitchInst>(BB.getFirstNonPHI()))
867       continue;
868 
869     for (Instruction &I : make_early_inc_range(BB)) {
870       auto *PN = dyn_cast<PHINode>(&I);
871       // Stop at the first non-PHI.
872       if (!PN)
873         break;
874 
875       AllocaInst *SpillSlot = insertPHILoads(PN, F);
876       if (SpillSlot)
877         insertPHIStores(PN, SpillSlot);
878 
879       PHINodes.push_back(PN);
880     }
881   }
882 
883   for (auto *PN : PHINodes) {
884     // There may be lingering uses on other EH PHIs being removed
885     PN->replaceAllUsesWith(PoisonValue::get(PN->getType()));
886     PN->eraseFromParent();
887   }
888 }
889 
cloneCommonBlocks(Function & F)890 void WinEHPrepareImpl::cloneCommonBlocks(Function &F) {
891   // We need to clone all blocks which belong to multiple funclets.  Values are
892   // remapped throughout the funclet to propagate both the new instructions
893   // *and* the new basic blocks themselves.
894   for (auto &Funclets : FuncletBlocks) {
895     BasicBlock *FuncletPadBB = Funclets.first;
896     std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
897     Value *FuncletToken;
898     if (FuncletPadBB == &F.getEntryBlock())
899       FuncletToken = ConstantTokenNone::get(F.getContext());
900     else
901       FuncletToken = FuncletPadBB->getFirstNonPHI();
902 
903     std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
904     ValueToValueMapTy VMap;
905     for (BasicBlock *BB : BlocksInFunclet) {
906       ColorVector &ColorsForBB = BlockColors[BB];
907       // We don't need to do anything if the block is monochromatic.
908       size_t NumColorsForBB = ColorsForBB.size();
909       if (NumColorsForBB == 1)
910         continue;
911 
912       DEBUG_WITH_TYPE("win-eh-prepare-coloring",
913                       dbgs() << "  Cloning block \'" << BB->getName()
914                              << "\' for funclet \'" << FuncletPadBB->getName()
915                              << "\'.\n");
916 
917       // Create a new basic block and copy instructions into it!
918       BasicBlock *CBB =
919           CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
920       // Insert the clone immediately after the original to ensure determinism
921       // and to keep the same relative ordering of any funclet's blocks.
922       CBB->insertInto(&F, BB->getNextNode());
923 
924       // Add basic block mapping.
925       VMap[BB] = CBB;
926 
927       // Record delta operations that we need to perform to our color mappings.
928       Orig2Clone.emplace_back(BB, CBB);
929     }
930 
931     // If nothing was cloned, we're done cloning in this funclet.
932     if (Orig2Clone.empty())
933       continue;
934 
935     // Update our color mappings to reflect that one block has lost a color and
936     // another has gained a color.
937     for (auto &BBMapping : Orig2Clone) {
938       BasicBlock *OldBlock = BBMapping.first;
939       BasicBlock *NewBlock = BBMapping.second;
940 
941       BlocksInFunclet.push_back(NewBlock);
942       ColorVector &NewColors = BlockColors[NewBlock];
943       assert(NewColors.empty() && "A new block should only have one color!");
944       NewColors.push_back(FuncletPadBB);
945 
946       DEBUG_WITH_TYPE("win-eh-prepare-coloring",
947                       dbgs() << "  Assigned color \'" << FuncletPadBB->getName()
948                              << "\' to block \'" << NewBlock->getName()
949                              << "\'.\n");
950 
951       llvm::erase(BlocksInFunclet, OldBlock);
952       ColorVector &OldColors = BlockColors[OldBlock];
953       llvm::erase(OldColors, FuncletPadBB);
954 
955       DEBUG_WITH_TYPE("win-eh-prepare-coloring",
956                       dbgs() << "  Removed color \'" << FuncletPadBB->getName()
957                              << "\' from block \'" << OldBlock->getName()
958                              << "\'.\n");
959     }
960 
961     // Loop over all of the instructions in this funclet, fixing up operand
962     // references as we go.  This uses VMap to do all the hard work.
963     for (BasicBlock *BB : BlocksInFunclet)
964       // Loop over all instructions, fixing each one as we find it...
965       for (Instruction &I : *BB)
966         RemapInstruction(&I, VMap,
967                          RF_IgnoreMissingLocals | RF_NoModuleLevelChanges);
968 
969     // Catchrets targeting cloned blocks need to be updated separately from
970     // the loop above because they are not in the current funclet.
971     SmallVector<CatchReturnInst *, 2> FixupCatchrets;
972     for (auto &BBMapping : Orig2Clone) {
973       BasicBlock *OldBlock = BBMapping.first;
974       BasicBlock *NewBlock = BBMapping.second;
975 
976       FixupCatchrets.clear();
977       for (BasicBlock *Pred : predecessors(OldBlock))
978         if (auto *CatchRet = dyn_cast<CatchReturnInst>(Pred->getTerminator()))
979           if (CatchRet->getCatchSwitchParentPad() == FuncletToken)
980             FixupCatchrets.push_back(CatchRet);
981 
982       for (CatchReturnInst *CatchRet : FixupCatchrets)
983         CatchRet->setSuccessor(NewBlock);
984     }
985 
986     auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
987       unsigned NumPreds = PN->getNumIncomingValues();
988       for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
989            ++PredIdx) {
990         BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
991         bool EdgeTargetsFunclet;
992         if (auto *CRI =
993                 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
994           EdgeTargetsFunclet = (CRI->getCatchSwitchParentPad() == FuncletToken);
995         } else {
996           ColorVector &IncomingColors = BlockColors[IncomingBlock];
997           assert(!IncomingColors.empty() && "Block not colored!");
998           assert((IncomingColors.size() == 1 ||
999                   !llvm::is_contained(IncomingColors, FuncletPadBB)) &&
1000                  "Cloning should leave this funclet's blocks monochromatic");
1001           EdgeTargetsFunclet = (IncomingColors.front() == FuncletPadBB);
1002         }
1003         if (IsForOldBlock != EdgeTargetsFunclet)
1004           continue;
1005         PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
1006         // Revisit the next entry.
1007         --PredIdx;
1008         --PredEnd;
1009       }
1010     };
1011 
1012     for (auto &BBMapping : Orig2Clone) {
1013       BasicBlock *OldBlock = BBMapping.first;
1014       BasicBlock *NewBlock = BBMapping.second;
1015       for (PHINode &OldPN : OldBlock->phis()) {
1016         UpdatePHIOnClonedBlock(&OldPN, /*IsForOldBlock=*/true);
1017       }
1018       for (PHINode &NewPN : NewBlock->phis()) {
1019         UpdatePHIOnClonedBlock(&NewPN, /*IsForOldBlock=*/false);
1020       }
1021     }
1022 
1023     // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
1024     // the PHI nodes for NewBB now.
1025     for (auto &BBMapping : Orig2Clone) {
1026       BasicBlock *OldBlock = BBMapping.first;
1027       BasicBlock *NewBlock = BBMapping.second;
1028       for (BasicBlock *SuccBB : successors(NewBlock)) {
1029         for (PHINode &SuccPN : SuccBB->phis()) {
1030           // Ok, we have a PHI node.  Figure out what the incoming value was for
1031           // the OldBlock.
1032           int OldBlockIdx = SuccPN.getBasicBlockIndex(OldBlock);
1033           if (OldBlockIdx == -1)
1034             break;
1035           Value *IV = SuccPN.getIncomingValue(OldBlockIdx);
1036 
1037           // Remap the value if necessary.
1038           if (auto *Inst = dyn_cast<Instruction>(IV)) {
1039             ValueToValueMapTy::iterator I = VMap.find(Inst);
1040             if (I != VMap.end())
1041               IV = I->second;
1042           }
1043 
1044           SuccPN.addIncoming(IV, NewBlock);
1045         }
1046       }
1047     }
1048 
1049     for (ValueToValueMapTy::value_type VT : VMap) {
1050       // If there were values defined in BB that are used outside the funclet,
1051       // then we now have to update all uses of the value to use either the
1052       // original value, the cloned value, or some PHI derived value.  This can
1053       // require arbitrary PHI insertion, of which we are prepared to do, clean
1054       // these up now.
1055       SmallVector<Use *, 16> UsesToRename;
1056 
1057       auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
1058       if (!OldI)
1059         continue;
1060       auto *NewI = cast<Instruction>(VT.second);
1061       // Scan all uses of this instruction to see if it is used outside of its
1062       // funclet, and if so, record them in UsesToRename.
1063       for (Use &U : OldI->uses()) {
1064         Instruction *UserI = cast<Instruction>(U.getUser());
1065         BasicBlock *UserBB = UserI->getParent();
1066         ColorVector &ColorsForUserBB = BlockColors[UserBB];
1067         assert(!ColorsForUserBB.empty());
1068         if (ColorsForUserBB.size() > 1 ||
1069             *ColorsForUserBB.begin() != FuncletPadBB)
1070           UsesToRename.push_back(&U);
1071       }
1072 
1073       // If there are no uses outside the block, we're done with this
1074       // instruction.
1075       if (UsesToRename.empty())
1076         continue;
1077 
1078       // We found a use of OldI outside of the funclet.  Rename all uses of OldI
1079       // that are outside its funclet to be uses of the appropriate PHI node
1080       // etc.
1081       SSAUpdater SSAUpdate;
1082       SSAUpdate.Initialize(OldI->getType(), OldI->getName());
1083       SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
1084       SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
1085 
1086       while (!UsesToRename.empty())
1087         SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
1088     }
1089   }
1090 }
1091 
removeImplausibleInstructions(Function & F)1092 void WinEHPrepareImpl::removeImplausibleInstructions(Function &F) {
1093   // Remove implausible terminators and replace them with UnreachableInst.
1094   for (auto &Funclet : FuncletBlocks) {
1095     BasicBlock *FuncletPadBB = Funclet.first;
1096     std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
1097     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
1098     auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);
1099     auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);
1100     auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);
1101 
1102     for (BasicBlock *BB : BlocksInFunclet) {
1103       for (Instruction &I : *BB) {
1104         auto *CB = dyn_cast<CallBase>(&I);
1105         if (!CB)
1106           continue;
1107 
1108         Value *FuncletBundleOperand = nullptr;
1109         if (auto BU = CB->getOperandBundle(LLVMContext::OB_funclet))
1110           FuncletBundleOperand = BU->Inputs.front();
1111 
1112         if (FuncletBundleOperand == FuncletPad)
1113           continue;
1114 
1115         // Skip call sites which are nounwind intrinsics or inline asm.
1116         auto *CalledFn =
1117             dyn_cast<Function>(CB->getCalledOperand()->stripPointerCasts());
1118         if (CalledFn && ((CalledFn->isIntrinsic() && CB->doesNotThrow()) ||
1119                          CB->isInlineAsm()))
1120           continue;
1121 
1122         // This call site was not part of this funclet, remove it.
1123         if (isa<InvokeInst>(CB)) {
1124           // Remove the unwind edge if it was an invoke.
1125           removeUnwindEdge(BB);
1126           // Get a pointer to the new call.
1127           BasicBlock::iterator CallI =
1128               std::prev(BB->getTerminator()->getIterator());
1129           auto *CI = cast<CallInst>(&*CallI);
1130           changeToUnreachable(CI);
1131         } else {
1132           changeToUnreachable(&I);
1133         }
1134 
1135         // There are no more instructions in the block (except for unreachable),
1136         // we are done.
1137         break;
1138       }
1139 
1140       Instruction *TI = BB->getTerminator();
1141       // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
1142       bool IsUnreachableRet = isa<ReturnInst>(TI) && FuncletPad;
1143       // The token consumed by a CatchReturnInst must match the funclet token.
1144       bool IsUnreachableCatchret = false;
1145       if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
1146         IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
1147       // The token consumed by a CleanupReturnInst must match the funclet token.
1148       bool IsUnreachableCleanupret = false;
1149       if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
1150         IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
1151       if (IsUnreachableRet || IsUnreachableCatchret ||
1152           IsUnreachableCleanupret) {
1153         changeToUnreachable(TI);
1154       } else if (isa<InvokeInst>(TI)) {
1155         if (Personality == EHPersonality::MSVC_CXX && CleanupPad) {
1156           // Invokes within a cleanuppad for the MSVC++ personality never
1157           // transfer control to their unwind edge: the personality will
1158           // terminate the program.
1159           removeUnwindEdge(BB);
1160         }
1161       }
1162     }
1163   }
1164 }
1165 
cleanupPreparedFunclets(Function & F)1166 void WinEHPrepareImpl::cleanupPreparedFunclets(Function &F) {
1167   // Clean-up some of the mess we made by removing useles PHI nodes, trivial
1168   // branches, etc.
1169   for (BasicBlock &BB : llvm::make_early_inc_range(F)) {
1170     SimplifyInstructionsInBlock(&BB);
1171     ConstantFoldTerminator(&BB, /*DeleteDeadConditions=*/true);
1172     MergeBlockIntoPredecessor(&BB);
1173   }
1174 
1175   // We might have some unreachable blocks after cleaning up some impossible
1176   // control flow.
1177   removeUnreachableBlocks(F);
1178 }
1179 
1180 #ifndef NDEBUG
verifyPreparedFunclets(Function & F)1181 void WinEHPrepareImpl::verifyPreparedFunclets(Function &F) {
1182   for (BasicBlock &BB : F) {
1183     size_t NumColors = BlockColors[&BB].size();
1184     assert(NumColors == 1 && "Expected monochromatic BB!");
1185     if (NumColors == 0)
1186       report_fatal_error("Uncolored BB!");
1187     if (NumColors > 1)
1188       report_fatal_error("Multicolor BB!");
1189     assert((DisableDemotion || !(BB.isEHPad() && isa<PHINode>(BB.begin()))) &&
1190            "EH Pad still has a PHI!");
1191   }
1192 }
1193 #endif
1194 
prepareExplicitEH(Function & F)1195 bool WinEHPrepareImpl::prepareExplicitEH(Function &F) {
1196   // Remove unreachable blocks.  It is not valuable to assign them a color and
1197   // their existence can trick us into thinking values are alive when they are
1198   // not.
1199   removeUnreachableBlocks(F);
1200 
1201   // Determine which blocks are reachable from which funclet entries.
1202   colorFunclets(F);
1203 
1204   cloneCommonBlocks(F);
1205 
1206   if (!DisableDemotion)
1207     demotePHIsOnFunclets(F, DemoteCatchSwitchPHIOnly ||
1208                                 DemoteCatchSwitchPHIOnlyOpt);
1209 
1210   if (!DisableCleanups) {
1211     assert(!verifyFunction(F, &dbgs()));
1212     removeImplausibleInstructions(F);
1213 
1214     assert(!verifyFunction(F, &dbgs()));
1215     cleanupPreparedFunclets(F);
1216   }
1217 
1218   LLVM_DEBUG(verifyPreparedFunclets(F));
1219   // Recolor the CFG to verify that all is well.
1220   LLVM_DEBUG(colorFunclets(F));
1221   LLVM_DEBUG(verifyPreparedFunclets(F));
1222 
1223   return true;
1224 }
1225 
1226 // TODO: Share loads when one use dominates another, or when a catchpad exit
1227 // dominates uses (needs dominators).
insertPHILoads(PHINode * PN,Function & F)1228 AllocaInst *WinEHPrepareImpl::insertPHILoads(PHINode *PN, Function &F) {
1229   BasicBlock *PHIBlock = PN->getParent();
1230   AllocaInst *SpillSlot = nullptr;
1231   Instruction *EHPad = PHIBlock->getFirstNonPHI();
1232 
1233   if (!EHPad->isTerminator()) {
1234     // If the EHPad isn't a terminator, then we can insert a load in this block
1235     // that will dominate all uses.
1236     SpillSlot = new AllocaInst(PN->getType(), DL->getAllocaAddrSpace(), nullptr,
1237                                Twine(PN->getName(), ".wineh.spillslot"),
1238                                F.getEntryBlock().begin());
1239     Value *V = new LoadInst(PN->getType(), SpillSlot,
1240                             Twine(PN->getName(), ".wineh.reload"),
1241                             PHIBlock->getFirstInsertionPt());
1242     PN->replaceAllUsesWith(V);
1243     return SpillSlot;
1244   }
1245 
1246   // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
1247   // loads of the slot before every use.
1248   DenseMap<BasicBlock *, Value *> Loads;
1249   for (Use &U : llvm::make_early_inc_range(PN->uses())) {
1250     auto *UsingInst = cast<Instruction>(U.getUser());
1251     if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
1252       // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
1253       // stores for it separately.
1254       continue;
1255     }
1256     replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1257   }
1258   return SpillSlot;
1259 }
1260 
1261 // TODO: improve store placement.  Inserting at def is probably good, but need
1262 // to be careful not to introduce interfering stores (needs liveness analysis).
1263 // TODO: identify related phi nodes that can share spill slots, and share them
1264 // (also needs liveness).
insertPHIStores(PHINode * OriginalPHI,AllocaInst * SpillSlot)1265 void WinEHPrepareImpl::insertPHIStores(PHINode *OriginalPHI,
1266                                        AllocaInst *SpillSlot) {
1267   // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1268   // stored to the spill slot by the end of the given Block.
1269   SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1270 
1271   Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1272 
1273   while (!Worklist.empty()) {
1274     BasicBlock *EHBlock;
1275     Value *InVal;
1276     std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1277 
1278     PHINode *PN = dyn_cast<PHINode>(InVal);
1279     if (PN && PN->getParent() == EHBlock) {
1280       // The value is defined by another PHI we need to remove, with no room to
1281       // insert a store after the PHI, so each predecessor needs to store its
1282       // incoming value.
1283       for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1284         Value *PredVal = PN->getIncomingValue(i);
1285 
1286         // Undef can safely be skipped.
1287         if (isa<UndefValue>(PredVal))
1288           continue;
1289 
1290         insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1291       }
1292     } else {
1293       // We need to store InVal, which dominates EHBlock, but can't put a store
1294       // in EHBlock, so need to put stores in each predecessor.
1295       for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1296         insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1297       }
1298     }
1299   }
1300 }
1301 
insertPHIStore(BasicBlock * PredBlock,Value * PredVal,AllocaInst * SpillSlot,SmallVectorImpl<std::pair<BasicBlock *,Value * >> & Worklist)1302 void WinEHPrepareImpl::insertPHIStore(
1303     BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1304     SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1305 
1306   if (PredBlock->isEHPad() && PredBlock->getFirstNonPHI()->isTerminator()) {
1307     // Pred is unsplittable, so we need to queue it on the worklist.
1308     Worklist.push_back({PredBlock, PredVal});
1309     return;
1310   }
1311 
1312   // Otherwise, insert the store at the end of the basic block.
1313   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator()->getIterator());
1314 }
1315 
replaceUseWithLoad(Value * V,Use & U,AllocaInst * & SpillSlot,DenseMap<BasicBlock *,Value * > & Loads,Function & F)1316 void WinEHPrepareImpl::replaceUseWithLoad(
1317     Value *V, Use &U, AllocaInst *&SpillSlot,
1318     DenseMap<BasicBlock *, Value *> &Loads, Function &F) {
1319   // Lazilly create the spill slot.
1320   if (!SpillSlot)
1321     SpillSlot = new AllocaInst(V->getType(), DL->getAllocaAddrSpace(), nullptr,
1322                                Twine(V->getName(), ".wineh.spillslot"),
1323                                F.getEntryBlock().begin());
1324 
1325   auto *UsingInst = cast<Instruction>(U.getUser());
1326   if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1327     // If this is a PHI node, we can't insert a load of the value before
1328     // the use.  Instead insert the load in the predecessor block
1329     // corresponding to the incoming value.
1330     //
1331     // Note that if there are multiple edges from a basic block to this
1332     // PHI node that we cannot have multiple loads.  The problem is that
1333     // the resulting PHI node will have multiple values (from each load)
1334     // coming in from the same block, which is illegal SSA form.
1335     // For this reason, we keep track of and reuse loads we insert.
1336     BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1337     if (auto *CatchRet =
1338             dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1339       // Putting a load above a catchret and use on the phi would still leave
1340       // a cross-funclet def/use.  We need to split the edge, change the
1341       // catchret to target the new block, and put the load there.
1342       BasicBlock *PHIBlock = UsingInst->getParent();
1343       BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1344       // SplitEdge gives us:
1345       //   IncomingBlock:
1346       //     ...
1347       //     br label %NewBlock
1348       //   NewBlock:
1349       //     catchret label %PHIBlock
1350       // But we need:
1351       //   IncomingBlock:
1352       //     ...
1353       //     catchret label %NewBlock
1354       //   NewBlock:
1355       //     br label %PHIBlock
1356       // So move the terminators to each others' blocks and swap their
1357       // successors.
1358       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1359       Goto->removeFromParent();
1360       CatchRet->removeFromParent();
1361       CatchRet->insertInto(IncomingBlock, IncomingBlock->end());
1362       Goto->insertInto(NewBlock, NewBlock->end());
1363       Goto->setSuccessor(0, PHIBlock);
1364       CatchRet->setSuccessor(NewBlock);
1365       // Update the color mapping for the newly split edge.
1366       // Grab a reference to the ColorVector to be inserted before getting the
1367       // reference to the vector we are copying because inserting the new
1368       // element in BlockColors might cause the map to be reallocated.
1369       ColorVector &ColorsForNewBlock = BlockColors[NewBlock];
1370       ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1371       ColorsForNewBlock = ColorsForPHIBlock;
1372       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1373         FuncletBlocks[FuncletPad].push_back(NewBlock);
1374       // Treat the new block as incoming for load insertion.
1375       IncomingBlock = NewBlock;
1376     }
1377     Value *&Load = Loads[IncomingBlock];
1378     // Insert the load into the predecessor block
1379     if (!Load)
1380       Load = new LoadInst(
1381           V->getType(), SpillSlot, Twine(V->getName(), ".wineh.reload"),
1382           /*isVolatile=*/false, IncomingBlock->getTerminator()->getIterator());
1383 
1384     U.set(Load);
1385   } else {
1386     // Reload right before the old use.
1387     auto *Load = new LoadInst(V->getType(), SpillSlot,
1388                               Twine(V->getName(), ".wineh.reload"),
1389                               /*isVolatile=*/false, UsingInst->getIterator());
1390     U.set(Load);
1391   }
1392 }
1393 
addIPToStateRange(const InvokeInst * II,MCSymbol * InvokeBegin,MCSymbol * InvokeEnd)1394 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1395                                       MCSymbol *InvokeBegin,
1396                                       MCSymbol *InvokeEnd) {
1397   assert(InvokeStateMap.count(II) &&
1398          "should get invoke with precomputed state");
1399   LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);
1400 }
1401 
addIPToStateRange(int State,MCSymbol * InvokeBegin,MCSymbol * InvokeEnd)1402 void WinEHFuncInfo::addIPToStateRange(int State, MCSymbol* InvokeBegin,
1403     MCSymbol* InvokeEnd) {
1404     LabelToStateMap[InvokeBegin] = std::make_pair(State, InvokeEnd);
1405 }
1406 
1407 WinEHFuncInfo::WinEHFuncInfo() = default;
1408