[WinEH] Fix CatchRetSuccessorColorMap accounting
[oota-llvm.git] / lib / CodeGen / WinEHPrepare.cpp
1 //===-- WinEHPrepare - Prepare exception handling for code generation ---===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass lowers LLVM IR exception handling into something closer to what the
11 // backend wants for functions using a personality function from a runtime
12 // provided by MSVC. Functions with other personality functions are left alone
13 // and may be prepared by other passes. In particular, all supported MSVC
14 // personality functions require cleanup code to be outlined, and the C++
15 // personality requires catch handler code to be outlined.
16 //
17 //===----------------------------------------------------------------------===//
18
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/Analysis/CFG.h"
21 #include "llvm/Analysis/LibCallSemantics.h"
22 #include "llvm/CodeGen/WinEHFuncInfo.h"
23 #include "llvm/Pass.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
26 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
27 #include "llvm/Transforms/Utils/Cloning.h"
28 #include "llvm/Transforms/Utils/Local.h"
29 #include "llvm/Transforms/Utils/SSAUpdater.h"
30
31 using namespace llvm;
32
33 #define DEBUG_TYPE "winehprepare"
34
35 static cl::opt<bool> DisableDemotion(
36     "disable-demotion", cl::Hidden,
37     cl::desc(
38         "Clone multicolor basic blocks but do not demote cross funclet values"),
39     cl::init(false));
40
41 static cl::opt<bool> DisableCleanups(
42     "disable-cleanups", cl::Hidden,
43     cl::desc("Do not remove implausible terminators or other similar cleanups"),
44     cl::init(false));
45
46 namespace {
47
48 class WinEHPrepare : public FunctionPass {
49 public:
50   static char ID; // Pass identification, replacement for typeid.
51   WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
52
53   bool runOnFunction(Function &Fn) override;
54
55   bool doFinalization(Module &M) override;
56
57   void getAnalysisUsage(AnalysisUsage &AU) const override;
58
59   const char *getPassName() const override {
60     return "Windows exception handling preparation";
61   }
62
63 private:
64   void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
65   void
66   insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
67                  SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
68   AllocaInst *insertPHILoads(PHINode *PN, Function &F);
69   void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
70                           DenseMap<BasicBlock *, Value *> &Loads, Function &F);
71   void demoteNonlocalUses(Value *V, std::set<BasicBlock *> &ColorsForBB,
72                           Function &F);
73   bool prepareExplicitEH(Function &F,
74                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
75   void replaceTerminatePadWithCleanup(Function &F);
76   void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
77   void demotePHIsOnFunclets(Function &F);
78   void demoteUsesBetweenFunclets(Function &F);
79   void demoteArgumentUses(Function &F);
80   void cloneCommonBlocks(Function &F,
81                          SmallVectorImpl<BasicBlock *> &EntryBlocks);
82   void removeImplausibleTerminators(Function &F);
83   void cleanupPreparedFunclets(Function &F);
84   void verifyPreparedFunclets(Function &F);
85
86   // All fields are reset by runOnFunction.
87   EHPersonality Personality = EHPersonality::Unknown;
88
89   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
90   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
91   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
92 };
93
94 } // end anonymous namespace
95
96 char WinEHPrepare::ID = 0;
97 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
98                    false, false)
99
100 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
101   return new WinEHPrepare(TM);
102 }
103
104 static void findFuncletEntryPoints(Function &Fn,
105                                    SmallVectorImpl<BasicBlock *> &EntryBlocks) {
106   EntryBlocks.push_back(&Fn.getEntryBlock());
107   for (BasicBlock &BB : Fn) {
108     Instruction *First = BB.getFirstNonPHI();
109     if (!First->isEHPad())
110       continue;
111     assert(!isa<LandingPadInst>(First) &&
112            "landingpad cannot be used with funclet EH personality");
113     // Find EH pad blocks that represent funclet start points.
114     if (!isa<CatchEndPadInst>(First) && !isa<CleanupEndPadInst>(First))
115       EntryBlocks.push_back(&BB);
116   }
117 }
118
119 bool WinEHPrepare::runOnFunction(Function &Fn) {
120   if (!Fn.hasPersonalityFn())
121     return false;
122
123   // Classify the personality to see what kind of preparation we need.
124   Personality = classifyEHPersonality(Fn.getPersonalityFn());
125
126   // Do nothing if this is not a funclet-based personality.
127   if (!isFuncletEHPersonality(Personality))
128     return false;
129
130   // Remove unreachable blocks.  It is not valuable to assign them a color and
131   // their existence can trick us into thinking values are alive when they are
132   // not.
133   removeUnreachableBlocks(Fn);
134
135   SmallVector<BasicBlock *, 4> EntryBlocks;
136   findFuncletEntryPoints(Fn, EntryBlocks);
137   return prepareExplicitEH(Fn, EntryBlocks);
138 }
139
140 bool WinEHPrepare::doFinalization(Module &M) { return false; }
141
142 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
143
144 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
145                              const BasicBlock *BB) {
146   CxxUnwindMapEntry UME;
147   UME.ToState = ToState;
148   UME.Cleanup = BB;
149   FuncInfo.CxxUnwindMap.push_back(UME);
150   return FuncInfo.getLastStateNumber();
151 }
152
153 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
154                                 int TryHigh, int CatchHigh,
155                                 ArrayRef<const CatchPadInst *> Handlers) {
156   WinEHTryBlockMapEntry TBME;
157   TBME.TryLow = TryLow;
158   TBME.TryHigh = TryHigh;
159   TBME.CatchHigh = CatchHigh;
160   assert(TBME.TryLow <= TBME.TryHigh);
161   for (const CatchPadInst *CPI : Handlers) {
162     WinEHHandlerType HT;
163     Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
164     if (TypeInfo->isNullValue())
165       HT.TypeDescriptor = nullptr;
166     else
167       HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
168     HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
169     HT.Handler = CPI->getParent();
170     if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
171       HT.CatchObj.Alloca = nullptr;
172     else
173       HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
174     TBME.HandlerArray.push_back(HT);
175   }
176   FuncInfo.TryBlockMap.push_back(TBME);
177 }
178
179 static const CatchPadInst *getSingleCatchPadPredecessor(const BasicBlock *BB) {
180   for (const BasicBlock *PredBlock : predecessors(BB))
181     if (auto *CPI = dyn_cast<CatchPadInst>(PredBlock->getFirstNonPHI()))
182       return CPI;
183   return nullptr;
184 }
185
186 /// Find all the catchpads that feed directly into the catchendpad. Frontends
187 /// using this personality should ensure that each catchendpad and catchpad has
188 /// one or zero catchpad predecessors.
189 ///
190 /// The following C++ generates the IR after it:
191 ///   try {
192 ///   } catch (A) {
193 ///   } catch (B) {
194 ///   }
195 ///
196 /// IR:
197 ///   %catchpad.A
198 ///     catchpad [i8* A typeinfo]
199 ///         to label %catch.A unwind label %catchpad.B
200 ///   %catchpad.B
201 ///     catchpad [i8* B typeinfo]
202 ///         to label %catch.B unwind label %endcatches
203 ///   %endcatches
204 ///     catchendblock unwind to caller
205 static void
206 findCatchPadsForCatchEndPad(const BasicBlock *CatchEndBB,
207                             SmallVectorImpl<const CatchPadInst *> &Handlers) {
208   const CatchPadInst *CPI = getSingleCatchPadPredecessor(CatchEndBB);
209   while (CPI) {
210     Handlers.push_back(CPI);
211     CPI = getSingleCatchPadPredecessor(CPI->getParent());
212   }
213   // We've pushed these back into reverse source order.  Reverse them to get
214   // the list back into source order.
215   std::reverse(Handlers.begin(), Handlers.end());
216 }
217
218 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
219 // to. If the unwind edge came from an invoke, return null.
220 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB) {
221   const TerminatorInst *TI = BB->getTerminator();
222   if (isa<InvokeInst>(TI))
223     return nullptr;
224   if (TI->isEHPad())
225     return BB;
226   return cast<CleanupReturnInst>(TI)->getCleanupPad()->getParent();
227 }
228
229 static void calculateExplicitCXXStateNumbers(WinEHFuncInfo &FuncInfo,
230                                              const BasicBlock &BB,
231                                              int ParentState) {
232   assert(BB.isEHPad());
233   const Instruction *FirstNonPHI = BB.getFirstNonPHI();
234   // All catchpad instructions will be handled when we process their
235   // respective catchendpad instruction.
236   if (isa<CatchPadInst>(FirstNonPHI))
237     return;
238
239   if (isa<CatchEndPadInst>(FirstNonPHI)) {
240     SmallVector<const CatchPadInst *, 2> Handlers;
241     findCatchPadsForCatchEndPad(&BB, Handlers);
242     const BasicBlock *FirstTryPad = Handlers.front()->getParent();
243     int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
244     FuncInfo.EHPadStateMap[Handlers.front()] = TryLow;
245     for (const BasicBlock *PredBlock : predecessors(FirstTryPad))
246       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
247         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, TryLow);
248     int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
249
250     // catchpads are separate funclets in C++ EH due to the way rethrow works.
251     // In SEH, they aren't, so no invokes will unwind to the catchendpad.
252     FuncInfo.EHPadStateMap[FirstNonPHI] = CatchLow;
253     int TryHigh = CatchLow - 1;
254     for (const BasicBlock *PredBlock : predecessors(&BB))
255       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
256         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CatchLow);
257     int CatchHigh = FuncInfo.getLastStateNumber();
258     addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
259     DEBUG(dbgs() << "TryLow[" << FirstTryPad->getName() << "]: " << TryLow
260                  << '\n');
261     DEBUG(dbgs() << "TryHigh[" << FirstTryPad->getName() << "]: " << TryHigh
262                  << '\n');
263     DEBUG(dbgs() << "CatchHigh[" << FirstTryPad->getName() << "]: " << CatchHigh
264                  << '\n');
265   } else if (isa<CleanupPadInst>(FirstNonPHI)) {
266     // A cleanup can have multiple exits; don't re-process after the first.
267     if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
268       return;
269     int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, &BB);
270     FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
271     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
272                  << BB.getName() << '\n');
273     for (const BasicBlock *PredBlock : predecessors(&BB))
274       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
275         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CleanupState);
276   } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
277     // Propagate ParentState to the cleanuppad in case it doesn't have
278     // any cleanuprets.
279     BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
280     calculateExplicitCXXStateNumbers(FuncInfo, *CleanupBlock, ParentState);
281     // Anything unwinding through CleanupEndPadInst is in ParentState.
282     FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
283     for (const BasicBlock *PredBlock : predecessors(&BB))
284       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
285         calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, ParentState);
286   } else if (isa<TerminatePadInst>(FirstNonPHI)) {
287     report_fatal_error("Not yet implemented!");
288   } else {
289     llvm_unreachable("unexpected EH Pad!");
290   }
291 }
292
293 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
294                         const Function *Filter, const BasicBlock *Handler) {
295   SEHUnwindMapEntry Entry;
296   Entry.ToState = ParentState;
297   Entry.IsFinally = false;
298   Entry.Filter = Filter;
299   Entry.Handler = Handler;
300   FuncInfo.SEHUnwindMap.push_back(Entry);
301   return FuncInfo.SEHUnwindMap.size() - 1;
302 }
303
304 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
305                          const BasicBlock *Handler) {
306   SEHUnwindMapEntry Entry;
307   Entry.ToState = ParentState;
308   Entry.IsFinally = true;
309   Entry.Filter = nullptr;
310   Entry.Handler = Handler;
311   FuncInfo.SEHUnwindMap.push_back(Entry);
312   return FuncInfo.SEHUnwindMap.size() - 1;
313 }
314
315 static void calculateExplicitSEHStateNumbers(WinEHFuncInfo &FuncInfo,
316                                              const BasicBlock &BB,
317                                              int ParentState) {
318   assert(BB.isEHPad());
319   const Instruction *FirstNonPHI = BB.getFirstNonPHI();
320   // All catchpad instructions will be handled when we process their
321   // respective catchendpad instruction.
322   if (isa<CatchPadInst>(FirstNonPHI))
323     return;
324
325   if (isa<CatchEndPadInst>(FirstNonPHI)) {
326     // Extract the filter function and the __except basic block and create a
327     // state for them.
328     SmallVector<const CatchPadInst *, 1> Handlers;
329     findCatchPadsForCatchEndPad(&BB, Handlers);
330     assert(Handlers.size() == 1 &&
331            "SEH doesn't have multiple handlers per __try");
332     const CatchPadInst *CPI = Handlers.front();
333     const BasicBlock *CatchPadBB = CPI->getParent();
334     const Constant *FilterOrNull =
335         cast<Constant>(CPI->getArgOperand(0)->stripPointerCasts());
336     const Function *Filter = dyn_cast<Function>(FilterOrNull);
337     assert((Filter || FilterOrNull->isNullValue()) &&
338            "unexpected filter value");
339     int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
340
341     // Everything in the __try block uses TryState as its parent state.
342     FuncInfo.EHPadStateMap[CPI] = TryState;
343     DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
344                  << CatchPadBB->getName() << '\n');
345     for (const BasicBlock *PredBlock : predecessors(CatchPadBB))
346       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
347         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, TryState);
348
349     // Everything in the __except block unwinds to ParentState, just like code
350     // outside the __try.
351     FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
352     DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
353                  << BB.getName() << '\n');
354     for (const BasicBlock *PredBlock : predecessors(&BB))
355       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
356         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
357   } else if (isa<CleanupPadInst>(FirstNonPHI)) {
358     // A cleanup can have multiple exits; don't re-process after the first.
359     if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
360       return;
361     int CleanupState = addSEHFinally(FuncInfo, ParentState, &BB);
362     FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
363     DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
364                  << BB.getName() << '\n');
365     for (const BasicBlock *PredBlock : predecessors(&BB))
366       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
367         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, CleanupState);
368   } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
369     // Propagate ParentState to the cleanuppad in case it doesn't have
370     // any cleanuprets.
371     BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
372     calculateExplicitSEHStateNumbers(FuncInfo, *CleanupBlock, ParentState);
373     // Anything unwinding through CleanupEndPadInst is in ParentState.
374     FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
375     DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
376                  << BB.getName() << '\n');
377     for (const BasicBlock *PredBlock : predecessors(&BB))
378       if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
379         calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
380   } else if (isa<TerminatePadInst>(FirstNonPHI)) {
381     report_fatal_error("Not yet implemented!");
382   } else {
383     llvm_unreachable("unexpected EH Pad!");
384   }
385 }
386
387 /// Check if the EH Pad unwinds to caller.  Cleanups are a little bit of a
388 /// special case because we have to look at the cleanupret instruction that uses
389 /// the cleanuppad.
390 static bool doesEHPadUnwindToCaller(const Instruction *EHPad) {
391   auto *CPI = dyn_cast<CleanupPadInst>(EHPad);
392   if (!CPI)
393     return EHPad->mayThrow();
394
395   // This cleanup does not return or unwind, so we say it unwinds to caller.
396   if (CPI->use_empty())
397     return true;
398
399   const Instruction *User = CPI->user_back();
400   if (auto *CRI = dyn_cast<CleanupReturnInst>(User))
401     return CRI->unwindsToCaller();
402   return cast<CleanupEndPadInst>(User)->unwindsToCaller();
403 }
404
405 void llvm::calculateSEHStateNumbers(const Function *Fn,
406                                     WinEHFuncInfo &FuncInfo) {
407   // Don't compute state numbers twice.
408   if (!FuncInfo.SEHUnwindMap.empty())
409     return;
410
411   for (const BasicBlock &BB : *Fn) {
412     if (!BB.isEHPad() || !doesEHPadUnwindToCaller(BB.getFirstNonPHI()))
413       continue;
414     calculateExplicitSEHStateNumbers(FuncInfo, BB, -1);
415   }
416 }
417
418 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
419                                          WinEHFuncInfo &FuncInfo) {
420   // Return if it's already been done.
421   if (!FuncInfo.EHPadStateMap.empty())
422     return;
423
424   for (const BasicBlock &BB : *Fn) {
425     if (!BB.isEHPad())
426       continue;
427     if (BB.isLandingPad())
428       report_fatal_error("MSVC C++ EH cannot use landingpads");
429     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
430     if (!doesEHPadUnwindToCaller(FirstNonPHI))
431       continue;
432     calculateExplicitCXXStateNumbers(FuncInfo, BB, -1);
433   }
434 }
435
436 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
437                            ClrHandlerType HandlerType, uint32_t TypeToken,
438                            const BasicBlock *Handler) {
439   ClrEHUnwindMapEntry Entry;
440   Entry.Parent = ParentState;
441   Entry.Handler = Handler;
442   Entry.HandlerType = HandlerType;
443   Entry.TypeToken = TypeToken;
444   FuncInfo.ClrEHUnwindMap.push_back(Entry);
445   return FuncInfo.ClrEHUnwindMap.size() - 1;
446 }
447
448 void llvm::calculateClrEHStateNumbers(const Function *Fn,
449                                       WinEHFuncInfo &FuncInfo) {
450   // Return if it's already been done.
451   if (!FuncInfo.EHPadStateMap.empty())
452     return;
453
454   SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
455
456   // Each pad needs to be able to refer to its parent, so scan the function
457   // looking for top-level handlers and seed the worklist with them.
458   for (const BasicBlock &BB : *Fn) {
459     if (!BB.isEHPad())
460       continue;
461     if (BB.isLandingPad())
462       report_fatal_error("CoreCLR EH cannot use landingpads");
463     const Instruction *FirstNonPHI = BB.getFirstNonPHI();
464     if (!doesEHPadUnwindToCaller(FirstNonPHI))
465       continue;
466     // queue this with sentinel parent state -1 to mean unwind to caller.
467     Worklist.emplace_back(FirstNonPHI, -1);
468   }
469
470   while (!Worklist.empty()) {
471     const Instruction *Pad;
472     int ParentState;
473     std::tie(Pad, ParentState) = Worklist.pop_back_val();
474
475     int PredState;
476     if (const CleanupEndPadInst *EndPad = dyn_cast<CleanupEndPadInst>(Pad)) {
477       FuncInfo.EHPadStateMap[EndPad] = ParentState;
478       // Queue the cleanuppad, in case it doesn't have a cleanupret.
479       Worklist.emplace_back(EndPad->getCleanupPad(), ParentState);
480       // Preds of the endpad should get the parent state.
481       PredState = ParentState;
482     } else if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
483       // A cleanup can have multiple exits; don't re-process after the first.
484       if (FuncInfo.EHPadStateMap.count(Pad))
485         continue;
486       // CoreCLR personality uses arity to distinguish faults from finallies.
487       const BasicBlock *PadBlock = Cleanup->getParent();
488       ClrHandlerType HandlerType =
489           (Cleanup->getNumOperands() ? ClrHandlerType::Fault
490                                      : ClrHandlerType::Finally);
491       int NewState =
492           addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
493       FuncInfo.EHPadStateMap[Cleanup] = NewState;
494       // Propagate the new state to all preds of the cleanup
495       PredState = NewState;
496     } else if (const CatchEndPadInst *EndPad = dyn_cast<CatchEndPadInst>(Pad)) {
497       FuncInfo.EHPadStateMap[EndPad] = ParentState;
498       // Preds of the endpad should get the parent state.
499       PredState = ParentState;
500     } else if (const CatchPadInst *Catch = dyn_cast<CatchPadInst>(Pad)) {
501       const BasicBlock *PadBlock = Catch->getParent();
502       uint32_t TypeToken = static_cast<uint32_t>(
503           cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
504       int NewState = addClrEHHandler(FuncInfo, ParentState,
505                                      ClrHandlerType::Catch, TypeToken, PadBlock);
506       FuncInfo.EHPadStateMap[Catch] = NewState;
507       // Preds of the catch get its state
508       PredState = NewState;
509     } else {
510       llvm_unreachable("Unexpected EH pad");
511     }
512
513     // Queue all predecessors with the given state
514     for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
515       if ((Pred = getEHPadFromPredecessor(Pred)))
516         Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
517     }
518   }
519 }
520
521 void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) {
522   if (Personality != EHPersonality::MSVC_CXX)
523     return;
524   for (BasicBlock &BB : F) {
525     Instruction *First = BB.getFirstNonPHI();
526     auto *TPI = dyn_cast<TerminatePadInst>(First);
527     if (!TPI)
528       continue;
529
530     if (TPI->getNumArgOperands() != 1)
531       report_fatal_error(
532           "Expected a unary terminatepad for MSVC C++ personalities!");
533
534     auto *TerminateFn = dyn_cast<Function>(TPI->getArgOperand(0));
535     if (!TerminateFn)
536       report_fatal_error("Function operand expected in terminatepad for MSVC "
537                          "C++ personalities!");
538
539     // Insert the cleanuppad instruction.
540     auto *CPI = CleanupPadInst::Create(
541         BB.getContext(), {}, Twine("terminatepad.for.", BB.getName()), &BB);
542
543     // Insert the call to the terminate instruction.
544     auto *CallTerminate = CallInst::Create(TerminateFn, {}, &BB);
545     CallTerminate->setDoesNotThrow();
546     CallTerminate->setDoesNotReturn();
547     CallTerminate->setCallingConv(TerminateFn->getCallingConv());
548
549     // Insert a new terminator for the cleanuppad using the same successor as
550     // the terminatepad.
551     CleanupReturnInst::Create(CPI, TPI->getUnwindDest(), &BB);
552
553     // Let's remove the terminatepad now that we've inserted the new
554     // instructions.
555     TPI->eraseFromParent();
556   }
557 }
558
559 static void
560 colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks,
561               std::map<BasicBlock *, std::set<BasicBlock *>> &BlockColors,
562               std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
563               std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletChildren) {
564   SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
565   BasicBlock *EntryBlock = &F.getEntryBlock();
566
567   // Build up the color map, which maps each block to its set of 'colors'.
568   // For any block B, the "colors" of B are the set of funclets F (possibly
569   // including a root "funclet" representing the main function), such that
570   // F will need to directly contain B or a copy of B (where the term "directly
571   // contain" is used to distinguish from being "transitively contained" in
572   // a nested funclet).
573   // Use a CFG walk driven by a worklist of (block, color) pairs.  The "color"
574   // sets attached during this processing to a block which is the entry of some
575   // funclet F is actually the set of F's parents -- i.e. the union of colors
576   // of all predecessors of F's entry.  For all other blocks, the color sets
577   // are as defined above.  A post-pass fixes up the block color map to reflect
578   // the same sense of "color" for funclet entries as for other blocks.
579
580   Worklist.push_back({EntryBlock, EntryBlock});
581
582   while (!Worklist.empty()) {
583     BasicBlock *Visiting;
584     BasicBlock *Color;
585     std::tie(Visiting, Color) = Worklist.pop_back_val();
586     Instruction *VisitingHead = Visiting->getFirstNonPHI();
587     if (VisitingHead->isEHPad() && !isa<CatchEndPadInst>(VisitingHead) &&
588         !isa<CleanupEndPadInst>(VisitingHead)) {
589       // Mark this as a funclet head as a member of itself.
590       FuncletBlocks[Visiting].insert(Visiting);
591       // Queue exits (i.e. successors of rets/endpads) with the parent color.
592       // Skip any exits that are catchendpads, since the parent color must then
593       // represent one of the catches chained to that catchendpad, but the
594       // catchendpad should get the color of the common parent of all its
595       // chained catches (i.e. the grandparent color of the current pad).
596       // We don't need to worry abou catchendpads going unvisited, since the
597       // catches chained to them must have unwind edges to them by which we will
598       // visit them.
599       for (User *U : VisitingHead->users()) {
600         if (auto *Exit = dyn_cast<TerminatorInst>(U)) {
601           for (BasicBlock *Succ : successors(Exit->getParent()))
602             if (!isa<CatchEndPadInst>(*Succ->getFirstNonPHI()))
603               if (BlockColors[Succ].insert(Color).second)
604                 Worklist.push_back({Succ, Color});
605         }
606       }
607       // Handle CatchPad specially since its successors need different colors.
608       if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(VisitingHead)) {
609         // Visit the normal successor with the color of the new EH pad, and
610         // visit the unwind successor with the color of the parent.
611         BasicBlock *NormalSucc = CatchPad->getNormalDest();
612         if (BlockColors[NormalSucc].insert(Visiting).second) {
613           Worklist.push_back({NormalSucc, Visiting});
614         }
615         BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
616         if (BlockColors[UnwindSucc].insert(Color).second) {
617           Worklist.push_back({UnwindSucc, Color});
618         }
619         continue;
620       }
621       // Switch color to the current node, except for terminate pads which
622       // have no bodies and only unwind successors and so need their successors
623       // visited with the color of the parent.
624       if (!isa<TerminatePadInst>(VisitingHead))
625         Color = Visiting;
626     } else {
627       // Note that this is a member of the given color.
628       FuncletBlocks[Color].insert(Visiting);
629     }
630
631     TerminatorInst *Terminator = Visiting->getTerminator();
632     if (isa<CleanupReturnInst>(Terminator) ||
633         isa<CatchReturnInst>(Terminator) ||
634         isa<CleanupEndPadInst>(Terminator)) {
635       // These blocks' successors have already been queued with the parent
636       // color.
637       continue;
638     }
639     for (BasicBlock *Succ : successors(Visiting)) {
640       if (isa<CatchEndPadInst>(Succ->getFirstNonPHI())) {
641         // The catchendpad needs to be visited with the parent's color, not
642         // the current color.  This will happen in the code above that visits
643         // any catchpad unwind successor with the parent color, so we can
644         // safely skip this successor here.
645         continue;
646       }
647       if (BlockColors[Succ].insert(Color).second) {
648         Worklist.push_back({Succ, Color});
649       }
650     }
651   }
652
653   // The processing above actually accumulated the parent set for this
654   // funclet into the color set for its entry; use the parent set to
655   // populate the children map, and reset the color set to include just
656   // the funclet itself (no instruction can target a funclet entry except on
657   // that transitions to the child funclet).
658   for (BasicBlock *FuncletEntry : EntryBlocks) {
659     std::set<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
660     for (BasicBlock *Parent : ColorMapItem)
661       FuncletChildren[Parent].insert(FuncletEntry);
662     ColorMapItem.clear();
663     ColorMapItem.insert(FuncletEntry);
664   }
665 }
666
667 void WinEHPrepare::colorFunclets(Function &F,
668                                  SmallVectorImpl<BasicBlock *> &EntryBlocks) {
669   ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks, FuncletChildren);
670 }
671
672 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
673                                                WinEHFuncInfo &FuncInfo) {
674   SmallVector<BasicBlock *, 4> EntryBlocks;
675   // colorFunclets needs the set of EntryBlocks, get them using
676   // findFuncletEntryPoints.
677   findFuncletEntryPoints(const_cast<Function &>(*Fn), EntryBlocks);
678
679   std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
680   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
681   std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
682   // Figure out which basic blocks belong to which funclets.
683   colorFunclets(const_cast<Function &>(*Fn), EntryBlocks, BlockColors,
684                 FuncletBlocks, FuncletChildren);
685
686   // We need to find the catchret successors.  To do this, we must first find
687   // all the catchpad funclets.
688   for (auto &Funclet : FuncletBlocks) {
689     // Figure out what kind of funclet we are looking at; We only care about
690     // catchpads.
691     BasicBlock *FuncletPadBB = Funclet.first;
692     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
693     auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
694     if (!CatchPad)
695       continue;
696
697     // The users of a catchpad are always catchrets.
698     for (User *Exit : CatchPad->users()) {
699       auto *CatchReturn = dyn_cast<CatchReturnInst>(Exit);
700       if (!CatchReturn)
701         continue;
702       BasicBlock *CatchRetSuccessor = CatchReturn->getSuccessor();
703       std::set<BasicBlock *> &SuccessorColors = BlockColors[CatchRetSuccessor];
704       assert(SuccessorColors.size() == 1 && "Expected BB to be monochrome!");
705       BasicBlock *Color = *SuccessorColors.begin();
706       // Record the catchret successor's funclet membership.
707       FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color;
708     }
709   }
710 }
711
712 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
713   // Strip PHI nodes off of EH pads.
714   SmallVector<PHINode *, 16> PHINodes;
715   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
716     BasicBlock *BB = &*FI++;
717     if (!BB->isEHPad())
718       continue;
719     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
720       Instruction *I = &*BI++;
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::demoteUsesBetweenFunclets(Function &F) {
742   // Turn all inter-funclet uses of a Value into loads and stores.
743   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
744     BasicBlock *BB = &*FI++;
745     std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
746     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
747       Instruction *I = &*BI++;
748       // Funclets are permitted to use static allocas.
749       if (auto *AI = dyn_cast<AllocaInst>(I))
750         if (AI->isStaticAlloca())
751           continue;
752
753       demoteNonlocalUses(I, ColorsForBB, F);
754     }
755   }
756 }
757
758 void WinEHPrepare::demoteArgumentUses(Function &F) {
759   // Also demote function parameters used in funclets.
760   std::set<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
761   for (Argument &Arg : F.args())
762     demoteNonlocalUses(&Arg, ColorsForEntry, F);
763 }
764
765 void WinEHPrepare::cloneCommonBlocks(
766     Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
767   // We need to clone all blocks which belong to multiple funclets.  Values are
768   // remapped throughout the funclet to propogate both the new instructions
769   // *and* the new basic blocks themselves.
770   for (BasicBlock *FuncletPadBB : EntryBlocks) {
771     std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
772
773     std::map<BasicBlock *, BasicBlock *> Orig2Clone;
774     ValueToValueMapTy VMap;
775     for (BasicBlock *BB : BlocksInFunclet) {
776       std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
777       // We don't need to do anything if the block is monochromatic.
778       size_t NumColorsForBB = ColorsForBB.size();
779       if (NumColorsForBB == 1)
780         continue;
781
782       // Create a new basic block and copy instructions into it!
783       BasicBlock *CBB =
784           CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
785       // Insert the clone immediately after the original to ensure determinism
786       // and to keep the same relative ordering of any funclet's blocks.
787       CBB->insertInto(&F, BB->getNextNode());
788
789       // Add basic block mapping.
790       VMap[BB] = CBB;
791
792       // Record delta operations that we need to perform to our color mappings.
793       Orig2Clone[BB] = CBB;
794     }
795
796     // If nothing was cloned, we're done cloning in this funclet.
797     if (Orig2Clone.empty())
798       continue;
799
800     // Update our color mappings to reflect that one block has lost a color and
801     // another has gained a color.
802     for (auto &BBMapping : Orig2Clone) {
803       BasicBlock *OldBlock = BBMapping.first;
804       BasicBlock *NewBlock = BBMapping.second;
805
806       BlocksInFunclet.insert(NewBlock);
807       BlockColors[NewBlock].insert(FuncletPadBB);
808
809       BlocksInFunclet.erase(OldBlock);
810       BlockColors[OldBlock].erase(FuncletPadBB);
811     }
812
813     // Loop over all of the instructions in this funclet, fixing up operand
814     // references as we go.  This uses VMap to do all the hard work.
815     for (BasicBlock *BB : BlocksInFunclet)
816       // Loop over all instructions, fixing each one as we find it...
817       for (Instruction &I : *BB)
818         RemapInstruction(&I, VMap,
819                          RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
820
821     // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
822     // the PHI nodes for NewBB now.
823     for (auto &BBMapping : Orig2Clone) {
824       BasicBlock *OldBlock = BBMapping.first;
825       BasicBlock *NewBlock = BBMapping.second;
826       for (BasicBlock *SuccBB : successors(NewBlock)) {
827         for (Instruction &SuccI : *SuccBB) {
828           auto *SuccPN = dyn_cast<PHINode>(&SuccI);
829           if (!SuccPN)
830             break;
831
832           // Ok, we have a PHI node.  Figure out what the incoming value was for
833           // the OldBlock.
834           int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
835           if (OldBlockIdx == -1)
836             break;
837           Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
838
839           // Remap the value if necessary.
840           if (auto *Inst = dyn_cast<Instruction>(IV)) {
841             ValueToValueMapTy::iterator I = VMap.find(Inst);
842             if (I != VMap.end())
843               IV = I->second;
844           }
845
846           SuccPN->addIncoming(IV, NewBlock);
847         }
848       }
849     }
850
851     for (ValueToValueMapTy::value_type VT : VMap) {
852       // If there were values defined in BB that are used outside the funclet,
853       // then we now have to update all uses of the value to use either the
854       // original value, the cloned value, or some PHI derived value.  This can
855       // require arbitrary PHI insertion, of which we are prepared to do, clean
856       // these up now.
857       SmallVector<Use *, 16> UsesToRename;
858
859       auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
860       if (!OldI)
861         continue;
862       auto *NewI = cast<Instruction>(VT.second);
863       // Scan all uses of this instruction to see if it is used outside of its
864       // funclet, and if so, record them in UsesToRename.
865       for (Use &U : OldI->uses()) {
866         Instruction *UserI = cast<Instruction>(U.getUser());
867         BasicBlock *UserBB = UserI->getParent();
868         std::set<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB];
869         assert(!ColorsForUserBB.empty());
870         if (ColorsForUserBB.size() > 1 ||
871             *ColorsForUserBB.begin() != FuncletPadBB)
872           UsesToRename.push_back(&U);
873       }
874
875       // If there are no uses outside the block, we're done with this
876       // instruction.
877       if (UsesToRename.empty())
878         continue;
879
880       // We found a use of OldI outside of the funclet.  Rename all uses of OldI
881       // that are outside its funclet to be uses of the appropriate PHI node
882       // etc.
883       SSAUpdater SSAUpdate;
884       SSAUpdate.Initialize(OldI->getType(), OldI->getName());
885       SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
886       SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
887
888       while (!UsesToRename.empty())
889         SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
890     }
891   }
892 }
893
894 void WinEHPrepare::removeImplausibleTerminators(Function &F) {
895   // Remove implausible terminators and replace them with UnreachableInst.
896   for (auto &Funclet : FuncletBlocks) {
897     BasicBlock *FuncletPadBB = Funclet.first;
898     std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
899     Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
900     auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
901     auto *CleanupPad = dyn_cast<CleanupPadInst>(FirstNonPHI);
902
903     for (BasicBlock *BB : BlocksInFunclet) {
904       TerminatorInst *TI = BB->getTerminator();
905       // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
906       bool IsUnreachableRet = isa<ReturnInst>(TI) && (CatchPad || CleanupPad);
907       // The token consumed by a CatchReturnInst must match the funclet token.
908       bool IsUnreachableCatchret = false;
909       if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
910         IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
911       // The token consumed by a CleanupReturnInst must match the funclet token.
912       bool IsUnreachableCleanupret = false;
913       if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
914         IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
915       // The token consumed by a CleanupEndPadInst must match the funclet token.
916       bool IsUnreachableCleanupendpad = false;
917       if (auto *CEPI = dyn_cast<CleanupEndPadInst>(TI))
918         IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad;
919       if (IsUnreachableRet || IsUnreachableCatchret ||
920           IsUnreachableCleanupret || IsUnreachableCleanupendpad) {
921         // Loop through all of our successors and make sure they know that one
922         // of their predecessors is going away.
923         for (BasicBlock *SuccBB : TI->successors())
924           SuccBB->removePredecessor(BB);
925
926         if (IsUnreachableCleanupendpad) {
927           // We can't simply replace a cleanupendpad with unreachable, because
928           // its predecessor edges are EH edges and unreachable is not an EH
929           // pad.  Change all predecessors to the "unwind to caller" form.
930           for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
931                PI != PE;) {
932             BasicBlock *Pred = *PI++;
933             removeUnwindEdge(Pred);
934           }
935         }
936
937         new UnreachableInst(BB->getContext(), TI);
938         TI->eraseFromParent();
939       }
940       // FIXME: Check for invokes/cleanuprets/cleanupendpads which unwind to
941       // implausible catchendpads (i.e. catchendpad not in immediate parent
942       // funclet).
943     }
944   }
945 }
946
947 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
948   // Clean-up some of the mess we made by removing useles PHI nodes, trivial
949   // branches, etc.
950   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
951     BasicBlock *BB = &*FI++;
952     SimplifyInstructionsInBlock(BB);
953     ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
954     MergeBlockIntoPredecessor(BB);
955   }
956
957   // We might have some unreachable blocks after cleaning up some impossible
958   // control flow.
959   removeUnreachableBlocks(F);
960 }
961
962 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
963   // Recolor the CFG to verify that all is well.
964   for (BasicBlock &BB : F) {
965     size_t NumColors = BlockColors[&BB].size();
966     assert(NumColors == 1 && "Expected monochromatic BB!");
967     if (NumColors == 0)
968       report_fatal_error("Uncolored BB!");
969     if (NumColors > 1)
970       report_fatal_error("Multicolor BB!");
971     if (!DisableDemotion) {
972       bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
973       assert(!EHPadHasPHI && "EH Pad still has a PHI!");
974       if (EHPadHasPHI)
975         report_fatal_error("EH Pad still has a PHI!");
976     }
977   }
978 }
979
980 bool WinEHPrepare::prepareExplicitEH(
981     Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
982   replaceTerminatePadWithCleanup(F);
983
984   // Determine which blocks are reachable from which funclet entries.
985   colorFunclets(F, EntryBlocks);
986
987   if (!DisableDemotion) {
988     demotePHIsOnFunclets(F);
989
990     demoteUsesBetweenFunclets(F);
991
992     demoteArgumentUses(F);
993   }
994
995   cloneCommonBlocks(F, EntryBlocks);
996
997   if (!DisableCleanups) {
998     removeImplausibleTerminators(F);
999
1000     cleanupPreparedFunclets(F);
1001   }
1002
1003   verifyPreparedFunclets(F);
1004
1005   BlockColors.clear();
1006   FuncletBlocks.clear();
1007   FuncletChildren.clear();
1008
1009   return true;
1010 }
1011
1012 // TODO: Share loads when one use dominates another, or when a catchpad exit
1013 // dominates uses (needs dominators).
1014 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1015   BasicBlock *PHIBlock = PN->getParent();
1016   AllocaInst *SpillSlot = nullptr;
1017
1018   if (isa<CleanupPadInst>(PHIBlock->getFirstNonPHI())) {
1019     // Insert a load in place of the PHI and replace all uses.
1020     SpillSlot = new AllocaInst(PN->getType(), nullptr,
1021                                Twine(PN->getName(), ".wineh.spillslot"),
1022                                &F.getEntryBlock().front());
1023     Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
1024                             &*PHIBlock->getFirstInsertionPt());
1025     PN->replaceAllUsesWith(V);
1026     return SpillSlot;
1027   }
1028
1029   DenseMap<BasicBlock *, Value *> Loads;
1030   for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1031        UI != UE;) {
1032     Use &U = *UI++;
1033     auto *UsingInst = cast<Instruction>(U.getUser());
1034     BasicBlock *UsingBB = UsingInst->getParent();
1035     if (UsingBB->isEHPad()) {
1036       // Use is on an EH pad phi.  Leave it alone; we'll insert loads and
1037       // stores for it separately.
1038       assert(isa<PHINode>(UsingInst));
1039       continue;
1040     }
1041     replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1042   }
1043   return SpillSlot;
1044 }
1045
1046 // TODO: improve store placement.  Inserting at def is probably good, but need
1047 // to be careful not to introduce interfering stores (needs liveness analysis).
1048 // TODO: identify related phi nodes that can share spill slots, and share them
1049 // (also needs liveness).
1050 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1051                                    AllocaInst *SpillSlot) {
1052   // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1053   // stored to the spill slot by the end of the given Block.
1054   SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1055
1056   Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1057
1058   while (!Worklist.empty()) {
1059     BasicBlock *EHBlock;
1060     Value *InVal;
1061     std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1062
1063     PHINode *PN = dyn_cast<PHINode>(InVal);
1064     if (PN && PN->getParent() == EHBlock) {
1065       // The value is defined by another PHI we need to remove, with no room to
1066       // insert a store after the PHI, so each predecessor needs to store its
1067       // incoming value.
1068       for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1069         Value *PredVal = PN->getIncomingValue(i);
1070
1071         // Undef can safely be skipped.
1072         if (isa<UndefValue>(PredVal))
1073           continue;
1074
1075         insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1076       }
1077     } else {
1078       // We need to store InVal, which dominates EHBlock, but can't put a store
1079       // in EHBlock, so need to put stores in each predecessor.
1080       for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1081         insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1082       }
1083     }
1084   }
1085 }
1086
1087 void WinEHPrepare::insertPHIStore(
1088     BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1089     SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1090
1091   if (PredBlock->isEHPad() &&
1092       !isa<CleanupPadInst>(PredBlock->getFirstNonPHI())) {
1093     // Pred is unsplittable, so we need to queue it on the worklist.
1094     Worklist.push_back({PredBlock, PredVal});
1095     return;
1096   }
1097
1098   // Otherwise, insert the store at the end of the basic block.
1099   new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1100 }
1101
1102 // TODO: Share loads for same-funclet uses (requires dominators if funclets
1103 // aren't properly nested).
1104 void WinEHPrepare::demoteNonlocalUses(Value *V,
1105                                       std::set<BasicBlock *> &ColorsForBB,
1106                                       Function &F) {
1107   // Tokens can only be used non-locally due to control flow involving
1108   // unreachable edges.  Don't try to demote the token usage, we'll simply
1109   // delete the cloned user later.
1110   if (isa<CatchPadInst>(V) || isa<CleanupPadInst>(V))
1111     return;
1112
1113   DenseMap<BasicBlock *, Value *> Loads;
1114   AllocaInst *SpillSlot = nullptr;
1115   for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;) {
1116     Use &U = *UI++;
1117     auto *UsingInst = cast<Instruction>(U.getUser());
1118     BasicBlock *UsingBB = UsingInst->getParent();
1119
1120     // Is the Use inside a block which is colored the same as the Def?
1121     // If so, we don't need to escape the Def because we will clone
1122     // ourselves our own private copy.
1123     std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
1124     if (ColorsForUsingBB == ColorsForBB)
1125       continue;
1126
1127     replaceUseWithLoad(V, U, SpillSlot, Loads, F);
1128   }
1129   if (SpillSlot) {
1130     // Insert stores of the computed value into the stack slot.
1131     // We have to be careful if I is an invoke instruction,
1132     // because we can't insert the store AFTER the terminator instruction.
1133     BasicBlock::iterator InsertPt;
1134     if (isa<Argument>(V)) {
1135       InsertPt = F.getEntryBlock().getTerminator()->getIterator();
1136     } else if (isa<TerminatorInst>(V)) {
1137       auto *II = cast<InvokeInst>(V);
1138       // We cannot demote invoke instructions to the stack if their normal
1139       // edge is critical. Therefore, split the critical edge and create a
1140       // basic block into which the store can be inserted.
1141       if (!II->getNormalDest()->getSinglePredecessor()) {
1142         unsigned SuccNum =
1143             GetSuccessorNumber(II->getParent(), II->getNormalDest());
1144         assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
1145         BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
1146         assert(NewBlock && "Unable to split critical edge.");
1147         // Update the color mapping for the newly split edge.
1148         std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[II->getParent()];
1149         BlockColors[NewBlock] = ColorsForUsingBB;
1150         for (BasicBlock *FuncletPad : ColorsForUsingBB)
1151           FuncletBlocks[FuncletPad].insert(NewBlock);
1152       }
1153       InsertPt = II->getNormalDest()->getFirstInsertionPt();
1154     } else {
1155       InsertPt = cast<Instruction>(V)->getIterator();
1156       ++InsertPt;
1157       // Don't insert before PHI nodes or EH pad instrs.
1158       for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
1159         ;
1160     }
1161     new StoreInst(V, SpillSlot, &*InsertPt);
1162   }
1163 }
1164
1165 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1166                                       DenseMap<BasicBlock *, Value *> &Loads,
1167                                       Function &F) {
1168   // Lazilly create the spill slot.
1169   if (!SpillSlot)
1170     SpillSlot = new AllocaInst(V->getType(), nullptr,
1171                                Twine(V->getName(), ".wineh.spillslot"),
1172                                &F.getEntryBlock().front());
1173
1174   auto *UsingInst = cast<Instruction>(U.getUser());
1175   if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1176     // If this is a PHI node, we can't insert a load of the value before
1177     // the use.  Instead insert the load in the predecessor block
1178     // corresponding to the incoming value.
1179     //
1180     // Note that if there are multiple edges from a basic block to this
1181     // PHI node that we cannot have multiple loads.  The problem is that
1182     // the resulting PHI node will have multiple values (from each load)
1183     // coming in from the same block, which is illegal SSA form.
1184     // For this reason, we keep track of and reuse loads we insert.
1185     BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1186     if (auto *CatchRet =
1187             dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1188       // Putting a load above a catchret and use on the phi would still leave
1189       // a cross-funclet def/use.  We need to split the edge, change the
1190       // catchret to target the new block, and put the load there.
1191       BasicBlock *PHIBlock = UsingInst->getParent();
1192       BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1193       // SplitEdge gives us:
1194       //   IncomingBlock:
1195       //     ...
1196       //     br label %NewBlock
1197       //   NewBlock:
1198       //     catchret label %PHIBlock
1199       // But we need:
1200       //   IncomingBlock:
1201       //     ...
1202       //     catchret label %NewBlock
1203       //   NewBlock:
1204       //     br label %PHIBlock
1205       // So move the terminators to each others' blocks and swap their
1206       // successors.
1207       BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1208       Goto->removeFromParent();
1209       CatchRet->removeFromParent();
1210       IncomingBlock->getInstList().push_back(CatchRet);
1211       NewBlock->getInstList().push_back(Goto);
1212       Goto->setSuccessor(0, PHIBlock);
1213       CatchRet->setSuccessor(NewBlock);
1214       // Update the color mapping for the newly split edge.
1215       std::set<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock];
1216       BlockColors[NewBlock] = ColorsForPHIBlock;
1217       for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1218         FuncletBlocks[FuncletPad].insert(NewBlock);
1219       // Treat the new block as incoming for load insertion.
1220       IncomingBlock = NewBlock;
1221     }
1222     Value *&Load = Loads[IncomingBlock];
1223     // Insert the load into the predecessor block
1224     if (!Load)
1225       Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1226                           /*Volatile=*/false, IncomingBlock->getTerminator());
1227
1228     U.set(Load);
1229   } else {
1230     // Reload right before the old use.
1231     auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1232                               /*Volatile=*/false, UsingInst);
1233     U.set(Load);
1234   }
1235 }
1236
1237 void WinEHFuncInfo::addIPToStateRange(const BasicBlock *PadBB,
1238                                       MCSymbol *InvokeBegin,
1239                                       MCSymbol *InvokeEnd) {
1240   assert(PadBB->isEHPad() && EHPadStateMap.count(PadBB->getFirstNonPHI()) &&
1241          "should get EH pad BB with precomputed state");
1242   InvokeToStateMap[InvokeBegin] =
1243       std::make_pair(EHPadStateMap[PadBB->getFirstNonPHI()], InvokeEnd);
1244 }