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