1 //===-- WinEHPrepare - Prepare exception handling for code generation ---===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
17 //===----------------------------------------------------------------------===//
19 #include "llvm/CodeGen/Passes.h"
20 #include "llvm/ADT/SetVector.h"
21 #include "llvm/Analysis/CFG.h"
22 #include "llvm/Analysis/EHPersonalities.h"
23 #include "llvm/CodeGen/WinEHFuncInfo.h"
24 #include "llvm/Pass.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
28 #include "llvm/Transforms/Utils/Cloning.h"
29 #include "llvm/Transforms/Utils/Local.h"
30 #include "llvm/Transforms/Utils/SSAUpdater.h"
34 #define DEBUG_TYPE "winehprepare"
36 static cl::opt<bool> DisableDemotion(
37 "disable-demotion", cl::Hidden,
39 "Clone multicolor basic blocks but do not demote cross funclet values"),
42 static cl::opt<bool> DisableCleanups(
43 "disable-cleanups", cl::Hidden,
44 cl::desc("Do not remove implausible terminators or other similar cleanups"),
49 class WinEHPrepare : public FunctionPass {
51 static char ID; // Pass identification, replacement for typeid.
52 WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
54 bool runOnFunction(Function &Fn) override;
56 bool doFinalization(Module &M) override;
58 void getAnalysisUsage(AnalysisUsage &AU) const override;
60 const char *getPassName() const override {
61 return "Windows exception handling preparation";
65 void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
67 insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
68 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
69 AllocaInst *insertPHILoads(PHINode *PN, Function &F);
70 void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
71 DenseMap<BasicBlock *, Value *> &Loads, Function &F);
72 bool prepareExplicitEH(Function &F,
73 SmallVectorImpl<BasicBlock *> &EntryBlocks);
74 void replaceTerminatePadWithCleanup(Function &F);
75 void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
76 void resolveFuncletAncestry(Function &F,
77 SmallVectorImpl<BasicBlock *> &EntryBlocks);
78 void resolveFuncletAncestryForPath(
79 Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath,
80 std::map<BasicBlock *, BasicBlock *> &IdentityMap);
81 void makeFuncletEdgeUnreachable(BasicBlock *Parent, BasicBlock *Child);
82 BasicBlock *cloneFuncletForParent(Function &F, BasicBlock *FuncletEntry,
84 void updateTerminatorsAfterFuncletClone(
85 Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet,
86 BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent,
87 ValueToValueMapTy &VMap,
88 std::map<BasicBlock *, BasicBlock *> &Orig2Clone);
90 void demotePHIsOnFunclets(Function &F);
91 void cloneCommonBlocks(Function &F,
92 SmallVectorImpl<BasicBlock *> &EntryBlocks);
93 void removeImplausibleTerminators(Function &F);
94 void cleanupPreparedFunclets(Function &F);
95 void verifyPreparedFunclets(Function &F);
97 // All fields are reset by runOnFunction.
98 EHPersonality Personality = EHPersonality::Unknown;
100 std::map<BasicBlock *, SetVector<BasicBlock *>> BlockColors;
101 std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
102 std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletChildren;
103 std::map<BasicBlock *, std::vector<BasicBlock *>> FuncletParents;
105 // This is a flag that indicates an uncommon situation where we need to
106 // clone funclets has been detected.
107 bool FuncletCloningRequired = false;
108 // When a funclet with multiple parents contains a catchret, the block to
109 // which it returns will be cloned so that there is a copy in each parent
110 // but one of the copies will not be properly linked to the catchret and
111 // in most cases will have no predecessors. This double map allows us
112 // to find these cloned blocks when we clone the child funclet.
113 std::map<BasicBlock *, std::map<BasicBlock *, BasicBlock*>> EstrangedBlocks;
116 } // end anonymous namespace
118 char WinEHPrepare::ID = 0;
119 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
122 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
123 return new WinEHPrepare(TM);
126 static void findFuncletEntryPoints(Function &Fn,
127 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
128 EntryBlocks.push_back(&Fn.getEntryBlock());
129 for (BasicBlock &BB : Fn) {
130 Instruction *First = BB.getFirstNonPHI();
131 if (!First->isEHPad())
133 assert(!isa<LandingPadInst>(First) &&
134 "landingpad cannot be used with funclet EH personality");
135 // Find EH pad blocks that represent funclet start points.
136 if (!isa<CatchEndPadInst>(First) && !isa<CleanupEndPadInst>(First))
137 EntryBlocks.push_back(&BB);
141 bool WinEHPrepare::runOnFunction(Function &Fn) {
142 if (!Fn.hasPersonalityFn())
145 // Classify the personality to see what kind of preparation we need.
146 Personality = classifyEHPersonality(Fn.getPersonalityFn());
148 // Do nothing if this is not a funclet-based personality.
149 if (!isFuncletEHPersonality(Personality))
152 // Remove unreachable blocks. It is not valuable to assign them a color and
153 // their existence can trick us into thinking values are alive when they are
155 removeUnreachableBlocks(Fn);
157 SmallVector<BasicBlock *, 4> EntryBlocks;
158 findFuncletEntryPoints(Fn, EntryBlocks);
159 return prepareExplicitEH(Fn, EntryBlocks);
162 bool WinEHPrepare::doFinalization(Module &M) { return false; }
164 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
166 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
167 const BasicBlock *BB) {
168 CxxUnwindMapEntry UME;
169 UME.ToState = ToState;
171 FuncInfo.CxxUnwindMap.push_back(UME);
172 return FuncInfo.getLastStateNumber();
175 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
176 int TryHigh, int CatchHigh,
177 ArrayRef<const CatchPadInst *> Handlers) {
178 WinEHTryBlockMapEntry TBME;
179 TBME.TryLow = TryLow;
180 TBME.TryHigh = TryHigh;
181 TBME.CatchHigh = CatchHigh;
182 assert(TBME.TryLow <= TBME.TryHigh);
183 for (const CatchPadInst *CPI : Handlers) {
185 Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
186 if (TypeInfo->isNullValue())
187 HT.TypeDescriptor = nullptr;
189 HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
190 HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
191 HT.Handler = CPI->getParent();
192 if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
193 HT.CatchObj.Alloca = nullptr;
195 HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
196 TBME.HandlerArray.push_back(HT);
198 FuncInfo.TryBlockMap.push_back(TBME);
201 static const CatchPadInst *getSingleCatchPadPredecessor(const BasicBlock *BB) {
202 for (const BasicBlock *PredBlock : predecessors(BB))
203 if (auto *CPI = dyn_cast<CatchPadInst>(PredBlock->getFirstNonPHI()))
208 /// Find all the catchpads that feed directly into the catchendpad. Frontends
209 /// using this personality should ensure that each catchendpad and catchpad has
210 /// one or zero catchpad predecessors.
212 /// The following C++ generates the IR after it:
220 /// catchpad [i8* A typeinfo]
221 /// to label %catch.A unwind label %catchpad.B
223 /// catchpad [i8* B typeinfo]
224 /// to label %catch.B unwind label %endcatches
226 /// catchendblock unwind to caller
228 findCatchPadsForCatchEndPad(const BasicBlock *CatchEndBB,
229 SmallVectorImpl<const CatchPadInst *> &Handlers) {
230 const CatchPadInst *CPI = getSingleCatchPadPredecessor(CatchEndBB);
232 Handlers.push_back(CPI);
233 CPI = getSingleCatchPadPredecessor(CPI->getParent());
235 // We've pushed these back into reverse source order. Reverse them to get
236 // the list back into source order.
237 std::reverse(Handlers.begin(), Handlers.end());
240 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
241 // to. If the unwind edge came from an invoke, return null.
242 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB) {
243 const TerminatorInst *TI = BB->getTerminator();
244 if (isa<InvokeInst>(TI))
248 return cast<CleanupReturnInst>(TI)->getCleanupPad()->getParent();
251 static void calculateExplicitCXXStateNumbers(WinEHFuncInfo &FuncInfo,
252 const BasicBlock &BB,
254 assert(BB.isEHPad());
255 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
256 // All catchpad instructions will be handled when we process their
257 // respective catchendpad instruction.
258 if (isa<CatchPadInst>(FirstNonPHI))
261 if (isa<CatchEndPadInst>(FirstNonPHI)) {
262 SmallVector<const CatchPadInst *, 2> Handlers;
263 findCatchPadsForCatchEndPad(&BB, Handlers);
264 const BasicBlock *FirstTryPad = Handlers.front()->getParent();
265 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
266 FuncInfo.EHPadStateMap[Handlers.front()] = TryLow;
267 for (const BasicBlock *PredBlock : predecessors(FirstTryPad))
268 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
269 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, TryLow);
270 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
272 // catchpads are separate funclets in C++ EH due to the way rethrow works.
273 // In SEH, they aren't, so no invokes will unwind to the catchendpad.
274 FuncInfo.EHPadStateMap[FirstNonPHI] = CatchLow;
275 int TryHigh = CatchLow - 1;
276 for (const BasicBlock *PredBlock : predecessors(&BB))
277 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
278 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CatchLow);
279 int CatchHigh = FuncInfo.getLastStateNumber();
280 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
281 DEBUG(dbgs() << "TryLow[" << FirstTryPad->getName() << "]: " << TryLow
283 DEBUG(dbgs() << "TryHigh[" << FirstTryPad->getName() << "]: " << TryHigh
285 DEBUG(dbgs() << "CatchHigh[" << FirstTryPad->getName() << "]: " << CatchHigh
287 } else if (isa<CleanupPadInst>(FirstNonPHI)) {
288 // A cleanup can have multiple exits; don't re-process after the first.
289 if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
291 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, &BB);
292 FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
293 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
294 << BB.getName() << '\n');
295 for (const BasicBlock *PredBlock : predecessors(&BB))
296 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
297 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CleanupState);
298 } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
299 // Propagate ParentState to the cleanuppad in case it doesn't have
301 BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
302 calculateExplicitCXXStateNumbers(FuncInfo, *CleanupBlock, ParentState);
303 // Anything unwinding through CleanupEndPadInst is in ParentState.
304 FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
305 for (const BasicBlock *PredBlock : predecessors(&BB))
306 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
307 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, ParentState);
308 } else if (isa<TerminatePadInst>(FirstNonPHI)) {
309 report_fatal_error("Not yet implemented!");
311 llvm_unreachable("unexpected EH Pad!");
315 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
316 const Function *Filter, const BasicBlock *Handler) {
317 SEHUnwindMapEntry Entry;
318 Entry.ToState = ParentState;
319 Entry.IsFinally = false;
320 Entry.Filter = Filter;
321 Entry.Handler = Handler;
322 FuncInfo.SEHUnwindMap.push_back(Entry);
323 return FuncInfo.SEHUnwindMap.size() - 1;
326 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
327 const BasicBlock *Handler) {
328 SEHUnwindMapEntry Entry;
329 Entry.ToState = ParentState;
330 Entry.IsFinally = true;
331 Entry.Filter = nullptr;
332 Entry.Handler = Handler;
333 FuncInfo.SEHUnwindMap.push_back(Entry);
334 return FuncInfo.SEHUnwindMap.size() - 1;
337 static void calculateExplicitSEHStateNumbers(WinEHFuncInfo &FuncInfo,
338 const BasicBlock &BB,
340 assert(BB.isEHPad());
341 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
342 // All catchpad instructions will be handled when we process their
343 // respective catchendpad instruction.
344 if (isa<CatchPadInst>(FirstNonPHI))
347 if (isa<CatchEndPadInst>(FirstNonPHI)) {
348 // Extract the filter function and the __except basic block and create a
350 SmallVector<const CatchPadInst *, 1> Handlers;
351 findCatchPadsForCatchEndPad(&BB, Handlers);
352 assert(Handlers.size() == 1 &&
353 "SEH doesn't have multiple handlers per __try");
354 const CatchPadInst *CPI = Handlers.front();
355 const BasicBlock *CatchPadBB = CPI->getParent();
356 const Constant *FilterOrNull =
357 cast<Constant>(CPI->getArgOperand(0)->stripPointerCasts());
358 const Function *Filter = dyn_cast<Function>(FilterOrNull);
359 assert((Filter || FilterOrNull->isNullValue()) &&
360 "unexpected filter value");
361 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
363 // Everything in the __try block uses TryState as its parent state.
364 FuncInfo.EHPadStateMap[CPI] = TryState;
365 DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
366 << CatchPadBB->getName() << '\n');
367 for (const BasicBlock *PredBlock : predecessors(CatchPadBB))
368 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
369 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, TryState);
371 // Everything in the __except block unwinds to ParentState, just like code
372 // outside the __try.
373 FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
374 DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
375 << BB.getName() << '\n');
376 for (const BasicBlock *PredBlock : predecessors(&BB))
377 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
378 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
379 } else if (isa<CleanupPadInst>(FirstNonPHI)) {
380 // A cleanup can have multiple exits; don't re-process after the first.
381 if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
383 int CleanupState = addSEHFinally(FuncInfo, ParentState, &BB);
384 FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
385 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
386 << BB.getName() << '\n');
387 for (const BasicBlock *PredBlock : predecessors(&BB))
388 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
389 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, CleanupState);
390 } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
391 // Propagate ParentState to the cleanuppad in case it doesn't have
393 BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
394 calculateExplicitSEHStateNumbers(FuncInfo, *CleanupBlock, ParentState);
395 // Anything unwinding through CleanupEndPadInst is in ParentState.
396 FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
397 DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
398 << BB.getName() << '\n');
399 for (const BasicBlock *PredBlock : predecessors(&BB))
400 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
401 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
402 } else if (isa<TerminatePadInst>(FirstNonPHI)) {
403 report_fatal_error("Not yet implemented!");
405 llvm_unreachable("unexpected EH Pad!");
409 /// Check if the EH Pad unwinds to caller. Cleanups are a little bit of a
410 /// special case because we have to look at the cleanupret instruction that uses
412 static bool doesEHPadUnwindToCaller(const Instruction *EHPad) {
413 auto *CPI = dyn_cast<CleanupPadInst>(EHPad);
415 return EHPad->mayThrow();
417 // This cleanup does not return or unwind, so we say it unwinds to caller.
418 if (CPI->use_empty())
421 const Instruction *User = CPI->user_back();
422 if (auto *CRI = dyn_cast<CleanupReturnInst>(User))
423 return CRI->unwindsToCaller();
424 return cast<CleanupEndPadInst>(User)->unwindsToCaller();
427 void llvm::calculateSEHStateNumbers(const Function *Fn,
428 WinEHFuncInfo &FuncInfo) {
429 // Don't compute state numbers twice.
430 if (!FuncInfo.SEHUnwindMap.empty())
433 for (const BasicBlock &BB : *Fn) {
434 if (!BB.isEHPad() || !doesEHPadUnwindToCaller(BB.getFirstNonPHI()))
436 calculateExplicitSEHStateNumbers(FuncInfo, BB, -1);
440 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
441 WinEHFuncInfo &FuncInfo) {
442 // Return if it's already been done.
443 if (!FuncInfo.EHPadStateMap.empty())
446 for (const BasicBlock &BB : *Fn) {
449 if (BB.isLandingPad())
450 report_fatal_error("MSVC C++ EH cannot use landingpads");
451 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
452 if (!doesEHPadUnwindToCaller(FirstNonPHI))
454 calculateExplicitCXXStateNumbers(FuncInfo, BB, -1);
458 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
459 ClrHandlerType HandlerType, uint32_t TypeToken,
460 const BasicBlock *Handler) {
461 ClrEHUnwindMapEntry Entry;
462 Entry.Parent = ParentState;
463 Entry.Handler = Handler;
464 Entry.HandlerType = HandlerType;
465 Entry.TypeToken = TypeToken;
466 FuncInfo.ClrEHUnwindMap.push_back(Entry);
467 return FuncInfo.ClrEHUnwindMap.size() - 1;
470 void llvm::calculateClrEHStateNumbers(const Function *Fn,
471 WinEHFuncInfo &FuncInfo) {
472 // Return if it's already been done.
473 if (!FuncInfo.EHPadStateMap.empty())
476 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
478 // Each pad needs to be able to refer to its parent, so scan the function
479 // looking for top-level handlers and seed the worklist with them.
480 for (const BasicBlock &BB : *Fn) {
483 if (BB.isLandingPad())
484 report_fatal_error("CoreCLR EH cannot use landingpads");
485 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
486 if (!doesEHPadUnwindToCaller(FirstNonPHI))
488 // queue this with sentinel parent state -1 to mean unwind to caller.
489 Worklist.emplace_back(FirstNonPHI, -1);
492 while (!Worklist.empty()) {
493 const Instruction *Pad;
495 std::tie(Pad, ParentState) = Worklist.pop_back_val();
498 if (const CleanupEndPadInst *EndPad = dyn_cast<CleanupEndPadInst>(Pad)) {
499 FuncInfo.EHPadStateMap[EndPad] = ParentState;
500 // Queue the cleanuppad, in case it doesn't have a cleanupret.
501 Worklist.emplace_back(EndPad->getCleanupPad(), ParentState);
502 // Preds of the endpad should get the parent state.
503 PredState = ParentState;
504 } else if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
505 // A cleanup can have multiple exits; don't re-process after the first.
506 if (FuncInfo.EHPadStateMap.count(Pad))
508 // CoreCLR personality uses arity to distinguish faults from finallies.
509 const BasicBlock *PadBlock = Cleanup->getParent();
510 ClrHandlerType HandlerType =
511 (Cleanup->getNumOperands() ? ClrHandlerType::Fault
512 : ClrHandlerType::Finally);
514 addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
515 FuncInfo.EHPadStateMap[Cleanup] = NewState;
516 // Propagate the new state to all preds of the cleanup
517 PredState = NewState;
518 } else if (const CatchEndPadInst *EndPad = dyn_cast<CatchEndPadInst>(Pad)) {
519 FuncInfo.EHPadStateMap[EndPad] = ParentState;
520 // Preds of the endpad should get the parent state.
521 PredState = ParentState;
522 } else if (const CatchPadInst *Catch = dyn_cast<CatchPadInst>(Pad)) {
523 const BasicBlock *PadBlock = Catch->getParent();
524 uint32_t TypeToken = static_cast<uint32_t>(
525 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
526 int NewState = addClrEHHandler(FuncInfo, ParentState,
527 ClrHandlerType::Catch, TypeToken, PadBlock);
528 FuncInfo.EHPadStateMap[Catch] = NewState;
529 // Preds of the catch get its state
530 PredState = NewState;
532 llvm_unreachable("Unexpected EH pad");
535 // Queue all predecessors with the given state
536 for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
537 if ((Pred = getEHPadFromPredecessor(Pred)))
538 Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
543 void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) {
544 if (Personality != EHPersonality::MSVC_CXX)
546 for (BasicBlock &BB : F) {
547 Instruction *First = BB.getFirstNonPHI();
548 auto *TPI = dyn_cast<TerminatePadInst>(First);
552 if (TPI->getNumArgOperands() != 1)
554 "Expected a unary terminatepad for MSVC C++ personalities!");
556 auto *TerminateFn = dyn_cast<Function>(TPI->getArgOperand(0));
558 report_fatal_error("Function operand expected in terminatepad for MSVC "
559 "C++ personalities!");
561 // Insert the cleanuppad instruction.
562 auto *CPI = CleanupPadInst::Create(
563 BB.getContext(), {}, Twine("terminatepad.for.", BB.getName()), &BB);
565 // Insert the call to the terminate instruction.
566 auto *CallTerminate = CallInst::Create(TerminateFn, {}, &BB);
567 CallTerminate->setDoesNotThrow();
568 CallTerminate->setDoesNotReturn();
569 CallTerminate->setCallingConv(TerminateFn->getCallingConv());
571 // Insert a new terminator for the cleanuppad using the same successor as
573 CleanupReturnInst::Create(CPI, TPI->getUnwindDest(), &BB);
575 // Let's remove the terminatepad now that we've inserted the new
577 TPI->eraseFromParent();
582 colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks,
583 std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors,
584 std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) {
585 SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
586 BasicBlock *EntryBlock = &F.getEntryBlock();
588 // Build up the color map, which maps each block to its set of 'colors'.
589 // For any block B, the "colors" of B are the set of funclets F (possibly
590 // including a root "funclet" representing the main function), such that
591 // F will need to directly contain B or a copy of B (where the term "directly
592 // contain" is used to distinguish from being "transitively contained" in
593 // a nested funclet).
594 // Use a CFG walk driven by a worklist of (block, color) pairs. The "color"
595 // sets attached during this processing to a block which is the entry of some
596 // funclet F is actually the set of F's parents -- i.e. the union of colors
597 // of all predecessors of F's entry. For all other blocks, the color sets
598 // are as defined above. A post-pass fixes up the block color map to reflect
599 // the same sense of "color" for funclet entries as for other blocks.
601 DEBUG_WITH_TYPE("winehprepare-coloring", dbgs() << "\nColoring funclets for "
602 << F.getName() << "\n");
604 Worklist.push_back({EntryBlock, EntryBlock});
606 while (!Worklist.empty()) {
607 BasicBlock *Visiting;
609 std::tie(Visiting, Color) = Worklist.pop_back_val();
610 DEBUG_WITH_TYPE("winehprepare-coloring",
611 dbgs() << "Visiting " << Visiting->getName() << ", "
612 << Color->getName() << "\n");
613 Instruction *VisitingHead = Visiting->getFirstNonPHI();
614 if (VisitingHead->isEHPad() && !isa<CatchEndPadInst>(VisitingHead) &&
615 !isa<CleanupEndPadInst>(VisitingHead)) {
616 // Mark this as a funclet head as a member of itself.
617 FuncletBlocks[Visiting].insert(Visiting);
618 // Queue exits (i.e. successors of rets/endpads) with the parent color.
619 // Skip any exits that are catchendpads, since the parent color must then
620 // represent one of the catches chained to that catchendpad, but the
621 // catchendpad should get the color of the common parent of all its
622 // chained catches (i.e. the grandparent color of the current pad).
623 // We don't need to worry abou catchendpads going unvisited, since the
624 // catches chained to them must have unwind edges to them by which we will
626 for (User *U : VisitingHead->users()) {
627 if (auto *Exit = dyn_cast<TerminatorInst>(U)) {
628 for (BasicBlock *Succ : successors(Exit->getParent()))
629 if (!isa<CatchEndPadInst>(*Succ->getFirstNonPHI()))
630 if (BlockColors[Succ].insert(Color)) {
631 DEBUG_WITH_TYPE("winehprepare-coloring",
632 dbgs() << " Assigned color \'"
633 << Color->getName() << "\' to block \'"
634 << Succ->getName() << "\'.\n");
635 Worklist.push_back({Succ, Color});
639 // Handle CatchPad specially since its successors need different colors.
640 if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(VisitingHead)) {
641 // Visit the normal successor with the color of the new EH pad, and
642 // visit the unwind successor with the color of the parent.
643 BasicBlock *NormalSucc = CatchPad->getNormalDest();
644 if (BlockColors[NormalSucc].insert(Visiting)) {
645 DEBUG_WITH_TYPE("winehprepare-coloring",
646 dbgs() << " Assigned color \'" << Visiting->getName()
647 << "\' to block \'" << NormalSucc->getName()
649 Worklist.push_back({NormalSucc, Visiting});
651 BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
652 if (BlockColors[UnwindSucc].insert(Color)) {
653 DEBUG_WITH_TYPE("winehprepare-coloring",
654 dbgs() << " Assigned color \'" << Color->getName()
655 << "\' to block \'" << UnwindSucc->getName()
657 Worklist.push_back({UnwindSucc, Color});
661 // Switch color to the current node, except for terminate pads which
662 // have no bodies and only unwind successors and so need their successors
663 // visited with the color of the parent.
664 if (!isa<TerminatePadInst>(VisitingHead))
667 // Note that this is a member of the given color.
668 FuncletBlocks[Color].insert(Visiting);
671 TerminatorInst *Terminator = Visiting->getTerminator();
672 if (isa<CleanupReturnInst>(Terminator) ||
673 isa<CatchReturnInst>(Terminator) ||
674 isa<CleanupEndPadInst>(Terminator)) {
675 // These blocks' successors have already been queued with the parent
679 for (BasicBlock *Succ : successors(Visiting)) {
680 if (isa<CatchEndPadInst>(Succ->getFirstNonPHI())) {
681 // The catchendpad needs to be visited with the parent's color, not
682 // the current color. This will happen in the code above that visits
683 // any catchpad unwind successor with the parent color, so we can
684 // safely skip this successor here.
687 if (BlockColors[Succ].insert(Color)) {
688 DEBUG_WITH_TYPE("winehprepare-coloring",
689 dbgs() << " Assigned color \'" << Color->getName()
690 << "\' to block \'" << Succ->getName()
692 Worklist.push_back({Succ, Color});
698 static BasicBlock *getEndPadForCatch(CatchPadInst *Catch) {
699 // The catch may have sibling catches. Follow the unwind chain until we get
700 // to the catchendpad.
701 BasicBlock *NextUnwindDest = Catch->getUnwindDest();
702 auto *UnwindTerminator = NextUnwindDest->getTerminator();
703 while (auto *NextCatch = dyn_cast<CatchPadInst>(UnwindTerminator)) {
704 NextUnwindDest = NextCatch->getUnwindDest();
705 UnwindTerminator = NextUnwindDest->getTerminator();
707 // The last catch in the chain must unwind to a catchendpad.
708 assert(isa<CatchEndPadInst>(UnwindTerminator));
709 return NextUnwindDest;
712 static void updateClonedEHPadUnwindToParent(
713 BasicBlock *UnwindDest, BasicBlock *OrigBlock, BasicBlock *CloneBlock,
714 std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent) {
715 auto updateUnwindTerminator = [](BasicBlock *BB) {
716 auto *Terminator = BB->getTerminator();
717 if (isa<CatchEndPadInst>(Terminator) ||
718 isa<CleanupEndPadInst>(Terminator)) {
719 removeUnwindEdge(BB);
721 // If the block we're updating has a cleanupendpad or cleanupret
722 // terminator, we just want to replace that terminator with an
723 // unreachable instruction.
724 assert(isa<CleanupEndPadInst>(Terminator) ||
725 isa<CleanupReturnInst>(Terminator));
726 // Loop over all of the successors, removing the block's entry from any
728 for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
729 (*SI)->removePredecessor(BB);
730 // Remove the terminator and replace it with an unreachable instruction.
731 BB->getTerminator()->eraseFromParent();
732 new UnreachableInst(BB->getContext(), BB);
736 assert(UnwindDest->isEHPad());
737 // There are many places to which this EH terminator can unwind and each has
738 // slightly different rules for whether or not it fits with the given
740 auto *EHPadInst = UnwindDest->getFirstNonPHI();
741 if (isa<CatchEndPadInst>(EHPadInst)) {
742 auto *CloneParentCatch =
743 dyn_cast<CatchPadInst>(CloneParent->getFirstNonPHI());
744 if (!CloneParentCatch ||
745 getEndPadForCatch(CloneParentCatch) != UnwindDest) {
747 "winehprepare-coloring",
748 dbgs() << " removing unwind destination of clone block \'"
749 << CloneBlock->getName() << "\'.\n");
750 updateUnwindTerminator(CloneBlock);
752 // It's possible that the catch end pad is a legal match for both the clone
753 // and the original, so they must be checked separately. If the original
754 // funclet will still have multiple parents after the current clone parent
755 // is removed, we'll leave its unwind terminator until later.
756 assert(OrigParents.size() >= 2);
757 if (OrigParents.size() != 2)
760 // If the original funclet will have a single parent after the clone parent
761 // is removed, check that parent's unwind destination.
762 assert(OrigParents.front() == CloneParent ||
763 OrigParents.back() == CloneParent);
764 BasicBlock *OrigParent;
765 if (OrigParents.front() == CloneParent)
766 OrigParent = OrigParents.back();
768 OrigParent = OrigParents.front();
770 auto *OrigParentCatch =
771 dyn_cast<CatchPadInst>(OrigParent->getFirstNonPHI());
772 if (!OrigParentCatch || getEndPadForCatch(OrigParentCatch) != UnwindDest) {
774 "winehprepare-coloring",
775 dbgs() << " removing unwind destination of original block \'"
776 << OrigBlock << "\'.\n");
777 updateUnwindTerminator(OrigBlock);
779 } else if (auto *CleanupEnd = dyn_cast<CleanupEndPadInst>(EHPadInst)) {
780 // If the EH terminator unwinds to a cleanupendpad, that cleanupendpad
781 // must be ending a cleanuppad of either our clone parent or one
782 // one of the parents of the original funclet.
783 auto *CloneParentCP =
784 dyn_cast<CleanupPadInst>(CloneParent->getFirstNonPHI());
785 auto *EndedCP = CleanupEnd->getCleanupPad();
786 if (EndedCP == CloneParentCP) {
787 // If it is ending the cleanuppad of our cloned parent, then we
788 // want to remove the unwind destination of the EH terminator that
789 // we associated with the original funclet.
790 assert(isa<CatchEndPadInst>(OrigBlock->getFirstNonPHI()));
792 "winehprepare-coloring",
793 dbgs() << " removing unwind destination of original block \'"
794 << OrigBlock->getName() << "\'.\n");
795 updateUnwindTerminator(OrigBlock);
797 // If it isn't ending the cleanuppad of our clone parent, then we
798 // want to remove the unwind destination of the EH terminator that
799 // associated with our cloned funclet.
800 assert(isa<CatchEndPadInst>(CloneBlock->getFirstNonPHI()));
802 "winehprepare-coloring",
803 dbgs() << " removing unwind destination of clone block \'"
804 << CloneBlock->getName() << "\'.\n");
805 updateUnwindTerminator(CloneBlock);
808 // If the EH terminator unwinds to a catchpad, cleanuppad or
809 // terminatepad that EH pad must be a sibling of the funclet we're
810 // cloning. We'll clone it later and update one of the catchendpad
811 // instrunctions that unwinds to it at that time.
812 assert(isa<CatchPadInst>(EHPadInst) || isa<CleanupPadInst>(EHPadInst) ||
813 isa<TerminatePadInst>(EHPadInst));
817 // If the terminator is a catchpad, we must also clone the catchendpad to which
818 // it unwinds and add this to the clone parent's block list. The catchendpad
819 // unwinds to either its caller, a sibling EH pad, a cleanup end pad in its
820 // parent funclet or a catch end pad in its grandparent funclet (which must be
821 // coupled with the parent funclet). If it has no unwind destination
822 // (i.e. unwind to caller), there is nothing to be done. If the unwind
823 // destination is a sibling EH pad, we will update the terminators later (in
824 // resolveFuncletAncestryForPath). If it unwinds to a cleanup end pad or a
825 // catch end pad and this end pad corresponds to the clone parent, we will
826 // remove the unwind destination in the original catchendpad. If it unwinds to
827 // a cleanup end pad or a catch end pad that does not correspond to the clone
828 // parent, we will remove the unwind destination in the cloned catchendpad.
829 static void updateCatchTerminators(
830 Function &F, CatchPadInst *OrigCatch, CatchPadInst *CloneCatch,
831 std::vector<BasicBlock *> &OrigParents, BasicBlock *CloneParent,
832 ValueToValueMapTy &VMap,
833 std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors,
834 std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks) {
835 // If we're cloning a catch pad that unwinds to a catchendpad, we also
836 // need to clone the catchendpad. The coloring algorithm associates
837 // the catchendpad block with the funclet's parent, so we have some work
838 // to do here to figure out whether the original belongs to the clone
839 // parent or one of the original funclets other parents (it might have
840 // more than one at this point). In either case, we might also need to
841 // remove the unwind edge if the catchendpad doesn't unwind to a block
842 // in the right grandparent funclet.
843 Instruction *I = CloneCatch->getUnwindDest()->getFirstNonPHI();
844 if (auto *CEP = dyn_cast<CatchEndPadInst>(I)) {
845 assert(BlockColors[CEP->getParent()].size() == 1);
846 BasicBlock *CEPFunclet = *(BlockColors[CEP->getParent()].begin());
847 BasicBlock *CEPCloneParent = nullptr;
848 CatchPadInst *PredCatch = nullptr;
849 if (CEPFunclet == CloneParent) {
850 // The catchendpad is in the clone parent, so we need to clone it
851 // and associate the clone with the original funclet's parent. If
852 // the original funclet had multiple parents, we'll add it to the
853 // first parent that isn't the clone parent. The logic in
854 // updateClonedEHPadUnwindToParent() will only remove the unwind edge
855 // if there is only one parent other than the clone parent, so we don't
856 // need to verify the ancestry. The catchendpad will eventually be
857 // cloned into the correct parent and all invalid unwind edges will be
859 for (auto *Parent : OrigParents) {
860 if (Parent != CloneParent) {
861 CEPCloneParent = Parent;
865 PredCatch = OrigCatch;
867 CEPCloneParent = CloneParent;
868 PredCatch = CloneCatch;
870 assert(CEPCloneParent && PredCatch);
871 DEBUG_WITH_TYPE("winehprepare-coloring",
872 dbgs() << " Cloning catchendpad \'"
873 << CEP->getParent()->getName() << "\' for funclet \'"
874 << CEPCloneParent->getName() << "\'.\n");
875 BasicBlock *ClonedCEP = CloneBasicBlock(
876 CEP->getParent(), VMap, Twine(".from.", CEPCloneParent->getName()));
877 // Insert the clone immediately after the original to ensure determinism
878 // and to keep the same relative ordering of any funclet's blocks.
879 ClonedCEP->insertInto(&F, CEP->getParent()->getNextNode());
880 PredCatch->setUnwindDest(ClonedCEP);
881 FuncletBlocks[CEPCloneParent].insert(ClonedCEP);
882 BlockColors[ClonedCEP].insert(CEPCloneParent);
883 DEBUG_WITH_TYPE("winehprepare-coloring",
884 dbgs() << " Assigning color \'"
885 << CEPCloneParent->getName() << "\' to block \'"
886 << ClonedCEP->getName() << "\'.\n");
887 auto *ClonedCEPInst = cast<CatchEndPadInst>(ClonedCEP->getTerminator());
888 if (auto *Dest = ClonedCEPInst->getUnwindDest())
889 updateClonedEHPadUnwindToParent(Dest, OrigCatch->getUnwindDest(),
890 CloneCatch->getUnwindDest(), OrigParents,
895 // While we are cloning a funclet because it has multiple parents, we will call
896 // this routine to update the terminators for the original and cloned copies
897 // of each basic block. All blocks in the funclet have been clone by this time.
898 // OrigBlock and CloneBlock will be identical except for their block label.
900 // If the terminator is a catchpad, we must also clone the catchendpad to which
901 // it unwinds and in most cases update either the original catchendpad or the
902 // clone. See the updateCatchTerminators() helper routine for details.
904 // If the terminator is a catchret its successor is a block in its parent
905 // funclet. If the instruction returns to a block in the parent for which the
906 // cloned funclet was created, the terminator in the original block must be
907 // replaced by an unreachable instruction. Otherwise the terminator in the
908 // clone block must be replaced by an unreachable instruction.
910 // If the terminator is a cleanupret or cleanupendpad it either unwinds to
911 // caller or unwinds to a sibling EH pad, a cleanup end pad in its parent
912 // funclet or a catch end pad in its grandparent funclet (which must be
913 // coupled with the parent funclet). If it unwinds to caller there is
914 // nothing to be done. If the unwind destination is a sibling EH pad, we will
915 // update the terminators later (in resolveFuncletAncestryForPath). If it
916 // unwinds to a cleanup end pad or a catch end pad and this end pad corresponds
917 // to the clone parent, we will replace the terminator in the original block
918 // with an unreachable instruction. If it unwinds to a cleanup end pad or a
919 // catch end pad that does not correspond to the clone parent, we will replace
920 // the terminator in the clone block with an unreachable instruction.
922 // If the terminator is an invoke instruction, we will handle it after all
923 // siblings of the current funclet have been cloned.
924 void WinEHPrepare::updateTerminatorsAfterFuncletClone(
925 Function &F, BasicBlock *OrigFunclet, BasicBlock *CloneFunclet,
926 BasicBlock *OrigBlock, BasicBlock *CloneBlock, BasicBlock *CloneParent,
927 ValueToValueMapTy &VMap, std::map<BasicBlock *, BasicBlock *> &Orig2Clone) {
928 // If the cloned block doesn't have an exceptional terminator, there is
929 // nothing to be done here.
930 TerminatorInst *CloneTerminator = CloneBlock->getTerminator();
931 if (!CloneTerminator->isExceptional())
934 if (auto *CloneCatch = dyn_cast<CatchPadInst>(CloneTerminator)) {
935 // A cloned catch pad has a lot of wrinkles, so we'll call a helper function
936 // to update this case.
937 auto *OrigCatch = cast<CatchPadInst>(OrigBlock->getTerminator());
938 updateCatchTerminators(F, OrigCatch, CloneCatch,
939 FuncletParents[OrigFunclet], CloneParent, VMap,
940 BlockColors, FuncletBlocks);
941 } else if (auto *CRI = dyn_cast<CatchReturnInst>(CloneTerminator)) {
942 if (FuncletBlocks[CloneParent].count(CRI->getSuccessor())) {
943 BasicBlock *OrigParent;
944 // The original funclet may have more than two parents, but that's OK.
945 // We just need to remap the original catchret to any of the parents.
946 // All of the parents should have an entry in the EstrangedBlocks map
947 // if any of them do.
948 if (FuncletParents[OrigFunclet].front() == CloneParent)
949 OrigParent = FuncletParents[OrigFunclet].back();
951 OrigParent = FuncletParents[OrigFunclet].front();
952 for (succ_iterator SI = succ_begin(OrigBlock), SE = succ_end(OrigBlock);
954 (*SI)->removePredecessor(OrigBlock);
955 BasicBlock *LostBlock = EstrangedBlocks[OrigParent][CRI->getSuccessor()];
956 auto *OrigCatchRet = cast<CatchReturnInst>(OrigBlock->getTerminator());
958 OrigCatchRet->setSuccessor(LostBlock);
960 OrigCatchRet->eraseFromParent();
961 new UnreachableInst(OrigBlock->getContext(), OrigBlock);
964 for (succ_iterator SI = succ_begin(CloneBlock), SE = succ_end(CloneBlock);
966 (*SI)->removePredecessor(CloneBlock);
967 BasicBlock *LostBlock = EstrangedBlocks[CloneParent][CRI->getSuccessor()];
969 CRI->setSuccessor(LostBlock);
971 CRI->eraseFromParent();
972 new UnreachableInst(CloneBlock->getContext(), CloneBlock);
975 } else if (isa<CleanupReturnInst>(CloneTerminator) ||
976 isa<CleanupEndPadInst>(CloneTerminator)) {
977 BasicBlock *UnwindDest = nullptr;
979 // A cleanup pad can unwind through either a cleanupret or a cleanupendpad
980 // but both are handled the same way.
981 if (auto *CRI = dyn_cast<CleanupReturnInst>(CloneTerminator))
982 UnwindDest = CRI->getUnwindDest();
983 else if (auto *CEI = dyn_cast<CleanupEndPadInst>(CloneTerminator))
984 UnwindDest = CEI->getUnwindDest();
986 // If the instruction has no local unwind destination, there is nothing
991 // The unwind destination may be a sibling EH pad, a catchendpad in
992 // a grandparent funclet (ending a catchpad in the parent) or a cleanup
993 // cleanupendpad in the parent. Call a helper routine to diagnose this
994 // and remove either the clone or original terminator as needed.
995 updateClonedEHPadUnwindToParent(UnwindDest, OrigBlock, CloneBlock,
996 FuncletParents[OrigFunclet], CloneParent);
1000 // Clones all blocks used by the specified funclet to avoid the funclet having
1001 // multiple parent funclets. All terminators in the parent that unwind to the
1002 // original funclet are remapped to unwind to the clone. Any terminator in the
1003 // original funclet which returned to this parent is converted to an unreachable
1004 // instruction. Likewise, any terminator in the cloned funclet which returns to
1005 // a parent funclet other than the specified parent is converted to an
1006 // unreachable instruction.
1007 BasicBlock *WinEHPrepare::cloneFuncletForParent(Function &F,
1008 BasicBlock *FuncletEntry,
1009 BasicBlock *Parent) {
1010 std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletEntry];
1012 DEBUG_WITH_TYPE("winehprepare-coloring",
1013 dbgs() << "Cloning funclet \'" << FuncletEntry->getName()
1014 << "\' for parent \'" << Parent->getName() << "\'.\n");
1016 std::map<BasicBlock *, BasicBlock *> Orig2Clone;
1017 ValueToValueMapTy VMap;
1018 for (BasicBlock *BB : BlocksInFunclet) {
1019 // Create a new basic block and copy instructions into it.
1021 CloneBasicBlock(BB, VMap, Twine(".from.", Parent->getName()));
1023 // Insert the clone immediately after the original to ensure determinism
1024 // and to keep the same relative ordering of any funclet's blocks.
1025 CBB->insertInto(&F, BB->getNextNode());
1027 // Add basic block mapping.
1030 // Record delta operations that we need to perform to our color mappings.
1031 Orig2Clone[BB] = CBB;
1032 } // end for (BasicBlock *BB : BlocksInFunclet)
1034 BasicBlock *ClonedFunclet = Orig2Clone[FuncletEntry];
1035 assert(ClonedFunclet);
1037 // Set the coloring for the blocks we just cloned.
1038 std::set<BasicBlock *> &ClonedBlocks = FuncletBlocks[ClonedFunclet];
1039 for (auto &BBMapping : Orig2Clone) {
1040 BasicBlock *NewBlock = BBMapping.second;
1041 ClonedBlocks.insert(NewBlock);
1042 BlockColors[NewBlock].insert(ClonedFunclet);
1044 DEBUG_WITH_TYPE("winehprepare-coloring",
1045 dbgs() << " Assigning color \'" << ClonedFunclet->getName()
1046 << "\' to block \'" << NewBlock->getName()
1049 // Use the VMap to remap the instructions in this cloned block.
1050 for (Instruction &I : *NewBlock)
1051 RemapInstruction(&I, VMap, RF_IgnoreMissingEntries);
1054 // All the cloned blocks have to be colored in the loop above before we can
1055 // update the terminators because doing so can require checking the color of
1056 // other blocks in the cloned funclet.
1057 for (auto &BBMapping : Orig2Clone) {
1058 BasicBlock *OldBlock = BBMapping.first;
1059 BasicBlock *NewBlock = BBMapping.second;
1061 // Update the terminator, if necessary, in both the original block and the
1062 // cloned so that the original funclet never returns to a block in the
1063 // clone parent and the clone funclet never returns to a block in any other
1064 // of the original funclet's parents.
1065 updateTerminatorsAfterFuncletClone(F, FuncletEntry, ClonedFunclet, OldBlock,
1066 NewBlock, Parent, VMap, Orig2Clone);
1068 // Check to see if the cloned block successor has PHI nodes. If so, we need
1069 // to add entries to the PHI nodes for the cloned block now.
1070 for (BasicBlock *SuccBB : successors(NewBlock)) {
1071 for (Instruction &SuccI : *SuccBB) {
1072 auto *SuccPN = dyn_cast<PHINode>(&SuccI);
1076 // Ok, we have a PHI node. Figure out what the incoming value was for
1078 int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
1079 if (OldBlockIdx == -1)
1081 Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
1083 // Remap the value if necessary.
1084 if (auto *Inst = dyn_cast<Instruction>(IV)) {
1085 ValueToValueMapTy::iterator I = VMap.find(Inst);
1086 if (I != VMap.end())
1090 SuccPN->addIncoming(IV, NewBlock);
1095 // Erase the clone's parent from the original funclet's parent list.
1096 std::vector<BasicBlock *> &Parents = FuncletParents[FuncletEntry];
1097 Parents.erase(std::remove(Parents.begin(), Parents.end(), Parent),
1100 // Store the cloned funclet's parent.
1101 assert(std::find(FuncletParents[ClonedFunclet].begin(),
1102 FuncletParents[ClonedFunclet].end(),
1103 Parent) == std::end(FuncletParents[ClonedFunclet]));
1104 FuncletParents[ClonedFunclet].push_back(Parent);
1106 // Copy any children of the original funclet to the clone. We'll either
1107 // clone them too or make that path unreachable when we take the next step
1108 // in resolveFuncletAncestryForPath().
1109 for (auto *Child : FuncletChildren[FuncletEntry]) {
1110 assert(std::find(FuncletChildren[ClonedFunclet].begin(),
1111 FuncletChildren[ClonedFunclet].end(),
1112 Child) == std::end(FuncletChildren[ClonedFunclet]));
1113 FuncletChildren[ClonedFunclet].push_back(Child);
1114 assert(std::find(FuncletParents[Child].begin(), FuncletParents[Child].end(),
1115 ClonedFunclet) == std::end(FuncletParents[Child]));
1116 FuncletParents[Child].push_back(ClonedFunclet);
1119 // Find any blocks that unwound to the original funclet entry from the
1120 // clone parent block and remap them to the clone.
1121 for (auto *U : FuncletEntry->users()) {
1122 auto *UT = dyn_cast<TerminatorInst>(U);
1125 BasicBlock *UBB = UT->getParent();
1126 assert(BlockColors[UBB].size() == 1);
1127 BasicBlock *UFunclet = *(BlockColors[UBB].begin());
1128 // Funclets shouldn't be able to loop back on themselves.
1129 assert(UFunclet != FuncletEntry);
1130 // If this instruction unwinds to the original funclet from the clone
1131 // parent, remap the terminator so that it unwinds to the clone instead.
1132 // We will perform a similar transformation for siblings after all
1133 // the siblings have been cloned.
1134 if (UFunclet == Parent) {
1135 // We're about to break the path from this block to the uncloned funclet
1136 // entry, so remove it as a predeccessor to clean up the PHIs.
1137 FuncletEntry->removePredecessor(UBB);
1138 TerminatorInst *Terminator = UBB->getTerminator();
1139 RemapInstruction(Terminator, VMap, RF_IgnoreMissingEntries);
1143 // This asserts a condition that is relied upon inside the loop below,
1144 // namely that no predecessors of the original funclet entry block
1145 // are also predecessors of the cloned funclet entry block.
1146 assert(std::all_of(pred_begin(FuncletEntry), pred_end(FuncletEntry),
1147 [&ClonedFunclet](BasicBlock *Pred) {
1148 return std::find(pred_begin(ClonedFunclet),
1149 pred_end(ClonedFunclet),
1150 Pred) == pred_end(ClonedFunclet);
1153 // Remove any invalid PHI node entries in the cloned funclet.cl
1154 std::vector<PHINode *> PHIsToErase;
1155 for (Instruction &I : *ClonedFunclet) {
1156 auto *PN = dyn_cast<PHINode>(&I);
1160 // Predecessors of the original funclet do not reach the cloned funclet,
1161 // but the cloning process assumes they will. Remove them now.
1162 for (auto *Pred : predecessors(FuncletEntry))
1163 PN->removeIncomingValue(Pred, false);
1165 for (auto *PN : PHIsToErase)
1166 PN->eraseFromParent();
1168 // Replace the original funclet in the parent's children vector with the
1170 for (auto &It : FuncletChildren[Parent]) {
1171 if (It == FuncletEntry) {
1177 return ClonedFunclet;
1180 // Removes the unwind edge for any exceptional terminators within the specified
1181 // parent funclet that previously unwound to the specified child funclet.
1182 void WinEHPrepare::makeFuncletEdgeUnreachable(BasicBlock *Parent,
1183 BasicBlock *Child) {
1184 for (BasicBlock *BB : FuncletBlocks[Parent]) {
1185 TerminatorInst *Terminator = BB->getTerminator();
1186 if (!Terminator->isExceptional())
1189 // Look for terninators that unwind to the child funclet.
1190 BasicBlock *UnwindDest = nullptr;
1191 if (auto *I = dyn_cast<InvokeInst>(Terminator))
1192 UnwindDest = I->getUnwindDest();
1193 else if (auto *I = dyn_cast<CatchEndPadInst>(Terminator))
1194 UnwindDest = I->getUnwindDest();
1195 else if (auto *I = dyn_cast<TerminatePadInst>(Terminator))
1196 UnwindDest = I->getUnwindDest();
1197 // cleanupendpad, catchret and cleanupret don't represent a parent-to-child
1198 // funclet transition, so we don't need to consider them here.
1200 // If the child funclet is the unwind destination, replace the terminator
1201 // with an unreachable instruction.
1202 if (UnwindDest == Child)
1203 removeUnwindEdge(BB);
1205 // The specified parent is no longer a parent of the specified child.
1206 std::vector<BasicBlock *> &Children = FuncletChildren[Parent];
1207 Children.erase(std::remove(Children.begin(), Children.end(), Child),
1211 // This routine is called after funclets with multiple parents are cloned for
1212 // a specific parent. Here we look for children of the specified funclet that
1213 // unwind to other children of that funclet and update the unwind destinations
1214 // to ensure that each sibling is connected to the correct clone of the sibling
1215 // to which it unwinds.
1217 // If the terminator is an invoke instruction, it unwinds either to a child
1218 // EH pad, a cleanup end pad in the current funclet, or a catch end pad in a
1219 // parent funclet (which ends either the current catch pad or a sibling
1220 // catch pad). If it unwinds to a child EH pad, the child will have multiple
1221 // parents after this funclet is cloned and this case will be handled later in
1222 // the resolveFuncletAncestryForPath processing. If it unwinds to a
1223 // cleanup end pad in the current funclet, the instruction remapping during
1224 // the cloning process should have already mapped the unwind destination to
1225 // the cloned copy of the cleanup end pad. If it unwinds to a catch end pad
1226 // there are two possibilities: either the catch end pad is the unwind
1227 // destination for the catch pad we are currently cloning or it is the unwind
1228 // destination for a sibling catch pad. If it it the unwind destination of the
1229 // catch pad we are cloning, we need to update the cloned invoke instruction
1230 // to unwind to the cloned catch end pad. Otherwise, we will handle this
1231 // later (in resolveFuncletAncestryForPath).
1232 static void updateSiblingToSiblingUnwind(
1233 BasicBlock *CurFunclet,
1234 std::map<BasicBlock *, SetVector<BasicBlock *>> &BlockColors,
1235 std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
1236 std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletParents,
1237 std::map<BasicBlock *, std::vector<BasicBlock *>> &FuncletChildren,
1238 std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) {
1239 // Remap any bad sibling-to-sibling transitions for funclets that
1241 for (BasicBlock *ChildFunclet : FuncletChildren[CurFunclet]) {
1242 for (auto *BB : FuncletBlocks[ChildFunclet]) {
1243 TerminatorInst *Terminator = BB->getTerminator();
1244 if (!Terminator->isExceptional())
1247 // See if this terminator has an unwind destination.
1248 // Note that catchendpads are handled when the associated catchpad
1249 // is cloned. They don't fit the pattern we're looking for here.
1250 BasicBlock *UnwindDest = nullptr;
1251 if (auto *I = dyn_cast<CatchPadInst>(Terminator)) {
1252 UnwindDest = I->getUnwindDest();
1253 // The catchendpad is not a sibling destination. This case should
1254 // have been handled in cloneFuncletForParent().
1255 if (isa<CatchEndPadInst>(Terminator)) {
1256 assert(BlockColors[UnwindDest].size() == 1 &&
1257 "Cloned catchpad unwinds to an pad with multiple parents.");
1258 assert(FuncletParents[UnwindDest].front() == CurFunclet &&
1259 "Cloned catchpad unwinds to the wrong parent.");
1263 if (auto *I = dyn_cast<CleanupReturnInst>(Terminator))
1264 UnwindDest = I->getUnwindDest();
1265 else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator))
1266 UnwindDest = I->getUnwindDest();
1268 // If the cleanup unwinds to caller, there is nothing to be done.
1273 // If the destination is not a cleanup pad, catch pad or terminate pad
1274 // we don't need to handle it here.
1275 Instruction *EHPad = UnwindDest->getFirstNonPHI();
1276 if (!isa<CleanupPadInst>(EHPad) && !isa<CatchPadInst>(EHPad) &&
1277 !isa<TerminatePadInst>(EHPad))
1280 // If it is one of these, then it is either a sibling of the current
1281 // child funclet or a clone of one of those siblings.
1282 // If it is a sibling, no action is needed.
1283 if (FuncletParents[UnwindDest].size() == 1 &&
1284 FuncletParents[UnwindDest].front() == CurFunclet)
1287 // If the unwind destination is a clone of a sibling, we need to figure
1288 // out which sibling it is a clone of and use that sibling as the
1289 // unwind destination.
1290 BasicBlock *DestOrig = Funclet2Orig[UnwindDest];
1291 BasicBlock *TargetSibling = nullptr;
1292 for (auto &Mapping : Funclet2Orig) {
1293 if (Mapping.second != DestOrig)
1295 BasicBlock *MappedFunclet = Mapping.first;
1296 if (FuncletParents[MappedFunclet].size() == 1 &&
1297 FuncletParents[MappedFunclet].front() == CurFunclet) {
1298 TargetSibling = MappedFunclet;
1301 // If we didn't find the sibling we were looking for then the
1302 // unwind destination is not a clone of one of child's siblings.
1303 // That's unexpected.
1304 assert(TargetSibling && "Funclet unwinds to unexpected destination.");
1306 // Update the terminator instruction to unwind to the correct sibling.
1307 if (auto *I = dyn_cast<CatchPadInst>(Terminator))
1308 I->setUnwindDest(TargetSibling);
1309 else if (auto *I = dyn_cast<CleanupReturnInst>(Terminator))
1310 I->setUnwindDest(TargetSibling);
1311 else if (auto *I = dyn_cast<CleanupEndPadInst>(Terminator))
1312 I->setUnwindDest(TargetSibling);
1316 // Invoke remapping can't be done correctly until after all of their
1317 // other sibling-to-sibling unwinds have been remapped.
1318 for (BasicBlock *ChildFunclet : FuncletChildren[CurFunclet]) {
1319 bool NeedOrigInvokeRemapping = false;
1320 for (auto *BB : FuncletBlocks[ChildFunclet]) {
1321 TerminatorInst *Terminator = BB->getTerminator();
1322 auto *II = dyn_cast<InvokeInst>(Terminator);
1326 BasicBlock *UnwindDest = II->getUnwindDest();
1327 assert(UnwindDest && "Invoke unwinds to a null destination.");
1328 assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad.");
1329 auto *EHPadInst = UnwindDest->getFirstNonPHI();
1330 if (isa<CleanupEndPadInst>(EHPadInst)) {
1331 // An invoke that unwinds to a cleanup end pad must be in a cleanup pad.
1332 assert(isa<CleanupPadInst>(ChildFunclet->getFirstNonPHI()) &&
1333 "Unwinding to cleanup end pad from a non cleanup pad funclet.");
1334 // The funclet cloning should have remapped the destination to the cloned
1336 assert(FuncletBlocks[ChildFunclet].count(UnwindDest) &&
1337 "Unwind destination for invoke was not updated during cloning.");
1338 } else if (isa<CatchEndPadInst>(EHPadInst)) {
1339 // If the invoke unwind destination is the unwind destination for
1340 // the current child catch pad funclet, there is nothing to be done.
1341 BasicBlock *OrigFunclet = Funclet2Orig[ChildFunclet];
1342 auto *CurCatch = cast<CatchPadInst>(ChildFunclet->getFirstNonPHI());
1343 auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI());
1344 if (OrigCatch->getUnwindDest() == UnwindDest) {
1345 // If the invoke unwinds to a catch end pad that is the unwind
1346 // destination for the original catch pad, the cloned invoke should
1347 // unwind to the cloned catch end pad.
1348 II->setUnwindDest(CurCatch->getUnwindDest());
1349 } else if (CurCatch->getUnwindDest() == UnwindDest) {
1350 // If the invoke unwinds to a catch end pad that is the unwind
1351 // destination for the clone catch pad, the original invoke should
1352 // unwind to the unwind destination of the original catch pad.
1353 // This happens when the catch end pad is matched to the clone
1354 // parent when the catchpad instruction is cloned and the original
1355 // invoke instruction unwinds to the original catch end pad (which
1356 // is now the unwind destination of the cloned catch pad).
1357 NeedOrigInvokeRemapping = true;
1359 // Otherwise, the invoke unwinds to a catch end pad that is the unwind
1360 // destination another catch pad in the unwind chain from either the
1361 // current catch pad or one of its clones. If it is already the
1362 // catch end pad at the end unwind chain from the current catch pad,
1363 // we'll need to check the invoke instructions in the original funclet
1364 // later. Otherwise, we need to remap this invoke now.
1365 assert((getEndPadForCatch(OrigCatch) == UnwindDest ||
1366 getEndPadForCatch(CurCatch) == UnwindDest) &&
1367 "Invoke within catch pad unwinds to an invalid catch end pad.");
1368 BasicBlock *CurCatchEnd = getEndPadForCatch(CurCatch);
1369 if (CurCatchEnd == UnwindDest)
1370 NeedOrigInvokeRemapping = true;
1372 II->setUnwindDest(CurCatchEnd);
1376 if (NeedOrigInvokeRemapping) {
1377 // To properly remap invoke instructions that unwind to catch end pads
1378 // that are not the unwind destination of the catch pad funclet in which
1379 // the invoke appears, we must also look at the uncloned invoke in the
1380 // original funclet. If we saw an invoke that was already properly
1381 // unwinding to a sibling's catch end pad, we need to check the invokes
1382 // in the original funclet.
1383 BasicBlock *OrigFunclet = Funclet2Orig[ChildFunclet];
1384 for (auto *BB : FuncletBlocks[OrigFunclet]) {
1385 auto *II = dyn_cast<InvokeInst>(BB->getTerminator());
1389 BasicBlock *UnwindDest = II->getUnwindDest();
1390 assert(UnwindDest && "Invoke unwinds to a null destination.");
1391 assert(UnwindDest->isEHPad() && "Invoke does not unwind to an EH pad.");
1392 auto *CEP = dyn_cast<CatchEndPadInst>(UnwindDest->getFirstNonPHI());
1396 // If the invoke unwind destination is the unwind destination for
1397 // the original catch pad funclet, there is nothing to be done.
1398 auto *OrigCatch = cast<CatchPadInst>(OrigFunclet->getFirstNonPHI());
1400 // If the invoke unwinds to a catch end pad that is neither the unwind
1401 // destination of OrigCatch or the destination another catch pad in the
1402 // unwind chain from current catch pad, we need to remap the invoke.
1403 BasicBlock *OrigCatchEnd = getEndPadForCatch(OrigCatch);
1404 if (OrigCatchEnd != UnwindDest)
1405 II->setUnwindDest(OrigCatchEnd);
1411 void WinEHPrepare::resolveFuncletAncestry(
1412 Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
1413 // Most of the time this will be unnecessary. If the conditions arise that
1414 // require this work, this flag will be set.
1415 if (!FuncletCloningRequired)
1418 // Funclet2Orig is used to map any cloned funclets back to the original
1419 // funclet from which they were cloned. The map is seeded with the
1420 // original funclets mapping to themselves.
1421 std::map<BasicBlock *, BasicBlock *> Funclet2Orig;
1422 for (auto *Funclet : EntryBlocks)
1423 Funclet2Orig[Funclet] = Funclet;
1425 // Start with the entry funclet and walk the funclet parent-child tree.
1426 SmallVector<BasicBlock *, 4> FuncletPath;
1427 FuncletPath.push_back(&(F.getEntryBlock()));
1428 resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig);
1431 // Walks the funclet control flow, cloning any funclets that have more than one
1432 // parent funclet and breaking any cyclic unwind chains so that the path becomes
1433 // unreachable at the point where a funclet would have unwound to a funclet that
1434 // was already in the chain.
1435 void WinEHPrepare::resolveFuncletAncestryForPath(
1436 Function &F, SmallVectorImpl<BasicBlock *> &FuncletPath,
1437 std::map<BasicBlock *, BasicBlock *> &Funclet2Orig) {
1438 bool ClonedAnyChildren = false;
1439 BasicBlock *CurFunclet = FuncletPath.back();
1440 // Copy the children vector because we might changing it.
1441 std::vector<BasicBlock *> Children(FuncletChildren[CurFunclet]);
1442 for (BasicBlock *ChildFunclet : Children) {
1443 // Don't allow the funclet chain to unwind back on itself.
1444 // If this funclet is already in the current funclet chain, make the
1445 // path to it through the current funclet unreachable.
1446 bool IsCyclic = false;
1447 BasicBlock *ChildIdentity = Funclet2Orig[ChildFunclet];
1448 for (BasicBlock *Ancestor : FuncletPath) {
1449 BasicBlock *AncestorIdentity = Funclet2Orig[Ancestor];
1450 if (AncestorIdentity == ChildIdentity) {
1455 // If the unwind chain wraps back on itself, break the chain.
1457 makeFuncletEdgeUnreachable(CurFunclet, ChildFunclet);
1460 // If this child funclet has other parents, clone the entire funclet.
1461 if (FuncletParents[ChildFunclet].size() > 1) {
1462 ChildFunclet = cloneFuncletForParent(F, ChildFunclet, CurFunclet);
1463 Funclet2Orig[ChildFunclet] = ChildIdentity;
1464 ClonedAnyChildren = true;
1466 FuncletPath.push_back(ChildFunclet);
1467 resolveFuncletAncestryForPath(F, FuncletPath, Funclet2Orig);
1468 FuncletPath.pop_back();
1470 // If we didn't clone any children, we can return now.
1471 if (!ClonedAnyChildren)
1474 updateSiblingToSiblingUnwind(CurFunclet, BlockColors, FuncletBlocks,
1475 FuncletParents, FuncletChildren, Funclet2Orig);
1478 void WinEHPrepare::colorFunclets(Function &F,
1479 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
1480 ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks);
1482 // The processing above actually accumulated the parent set for this
1483 // funclet into the color set for its entry; use the parent set to
1484 // populate the children map, and reset the color set to include just
1485 // the funclet itself (no instruction can target a funclet entry except on
1486 // that transitions to the child funclet).
1487 for (BasicBlock *FuncletEntry : EntryBlocks) {
1488 SetVector<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
1489 // It will be rare for funclets to have multiple parents, but if any
1490 // do we need to clone the funclet later to address that. Here we
1491 // set a flag indicating that this case has arisen so that we don't
1492 // have to do a lot of checking later to handle the more common case.
1493 if (ColorMapItem.size() > 1)
1494 FuncletCloningRequired = true;
1495 for (BasicBlock *Parent : ColorMapItem) {
1496 assert(std::find(FuncletChildren[Parent].begin(),
1497 FuncletChildren[Parent].end(),
1498 FuncletEntry) == std::end(FuncletChildren[Parent]));
1499 FuncletChildren[Parent].push_back(FuncletEntry);
1500 assert(std::find(FuncletParents[FuncletEntry].begin(),
1501 FuncletParents[FuncletEntry].end(),
1502 Parent) == std::end(FuncletParents[FuncletEntry]));
1503 FuncletParents[FuncletEntry].push_back(Parent);
1505 ColorMapItem.clear();
1506 ColorMapItem.insert(FuncletEntry);
1510 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
1511 WinEHFuncInfo &FuncInfo) {
1512 SmallVector<BasicBlock *, 4> EntryBlocks;
1513 // colorFunclets needs the set of EntryBlocks, get them using
1514 // findFuncletEntryPoints.
1515 findFuncletEntryPoints(const_cast<Function &>(*Fn), EntryBlocks);
1517 std::map<BasicBlock *, SetVector<BasicBlock *>> BlockColors;
1518 std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
1519 // Figure out which basic blocks belong to which funclets.
1520 colorFunclets(const_cast<Function &>(*Fn), EntryBlocks, BlockColors,
1523 // The static colorFunclets routine assigns multiple colors to funclet entries
1524 // because that information is needed to calculate funclets' parent-child
1525 // relationship, but we don't need those relationship here and ultimately the
1526 // entry blocks should have the color of the funclet they begin.
1527 for (BasicBlock *FuncletEntry : EntryBlocks) {
1528 BlockColors[FuncletEntry].clear();
1529 BlockColors[FuncletEntry].insert(FuncletEntry);
1532 // We need to find the catchret successors. To do this, we must first find
1533 // all the catchpad funclets.
1534 for (auto &Funclet : FuncletBlocks) {
1535 // Figure out what kind of funclet we are looking at; We only care about
1537 BasicBlock *FuncletPadBB = Funclet.first;
1538 Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
1539 auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
1543 // The users of a catchpad are always catchrets.
1544 for (User *Exit : CatchPad->users()) {
1545 auto *CatchReturn = dyn_cast<CatchReturnInst>(Exit);
1548 BasicBlock *CatchRetSuccessor = CatchReturn->getSuccessor();
1549 SetVector<BasicBlock *> &SuccessorColors = BlockColors[CatchRetSuccessor];
1550 assert(SuccessorColors.size() == 1 && "Expected BB to be monochrome!");
1551 BasicBlock *Color = *SuccessorColors.begin();
1552 // Record the catchret successor's funclet membership.
1553 FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color;
1558 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
1559 // Strip PHI nodes off of EH pads.
1560 SmallVector<PHINode *, 16> PHINodes;
1561 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
1562 BasicBlock *BB = &*FI++;
1565 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
1566 Instruction *I = &*BI++;
1567 auto *PN = dyn_cast<PHINode>(I);
1568 // Stop at the first non-PHI.
1572 AllocaInst *SpillSlot = insertPHILoads(PN, F);
1574 insertPHIStores(PN, SpillSlot);
1576 PHINodes.push_back(PN);
1580 for (auto *PN : PHINodes) {
1581 // There may be lingering uses on other EH PHIs being removed
1582 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
1583 PN->eraseFromParent();
1587 void WinEHPrepare::cloneCommonBlocks(
1588 Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
1589 // We need to clone all blocks which belong to multiple funclets. Values are
1590 // remapped throughout the funclet to propogate both the new instructions
1591 // *and* the new basic blocks themselves.
1592 for (BasicBlock *FuncletPadBB : EntryBlocks) {
1593 std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
1595 std::map<BasicBlock *, BasicBlock *> Orig2Clone;
1596 ValueToValueMapTy VMap;
1597 for (auto BlockIt = BlocksInFunclet.begin(),
1598 BlockEnd = BlocksInFunclet.end();
1599 BlockIt != BlockEnd;) {
1600 // Increment the iterator inside the loop because we might be removing
1601 // blocks from the set.
1602 BasicBlock *BB = *BlockIt++;
1603 SetVector<BasicBlock *> &ColorsForBB = BlockColors[BB];
1604 // We don't need to do anything if the block is monochromatic.
1605 size_t NumColorsForBB = ColorsForBB.size();
1606 if (NumColorsForBB == 1)
1609 // If this block is a catchendpad, it shouldn't be cloned.
1610 // We will only see a catchendpad with multiple colors in the case where
1611 // some funclet has multiple parents. In that case, the color will be
1612 // resolved during the resolveFuncletAncestry processing.
1613 // For now, find the catchpad that unwinds to this block and assign
1614 // that catchpad's first parent to be the color for this block.
1615 if (isa<CatchEndPadInst>(BB->getFirstNonPHI())) {
1617 FuncletCloningRequired &&
1618 "Found multi-colored catchendpad with no multi-parent funclets.");
1619 BasicBlock *CatchParent = nullptr;
1620 // There can only be one catchpad predecessor for a catchendpad.
1621 for (BasicBlock *PredBB : predecessors(BB)) {
1622 if (isa<CatchPadInst>(PredBB->getTerminator())) {
1623 CatchParent = PredBB;
1627 // There must be one catchpad predecessor for a catchendpad.
1628 assert(CatchParent && "No catchpad found for catchendpad.");
1630 // If the catchpad has multiple parents, we'll clone the catchendpad
1631 // when we clone the catchpad funclet and insert it into the correct
1632 // funclet. For now, we just select the first parent of the catchpad
1633 // and give the catchendpad that color.
1634 BasicBlock *CorrectColor = FuncletParents[CatchParent].front();
1635 assert(FuncletBlocks[CorrectColor].count(BB));
1636 assert(BlockColors[BB].count(CorrectColor));
1638 // Remove this block from the FuncletBlocks set of any funclet that
1639 // isn't the funclet whose color we just selected.
1640 for (BasicBlock *ContainingFunclet : BlockColors[BB])
1641 if (ContainingFunclet != CorrectColor)
1642 FuncletBlocks[ContainingFunclet].erase(BB);
1643 BlockColors[BB].remove_if([&](BasicBlock *ContainingFunclet) {
1644 return ContainingFunclet != CorrectColor;
1646 // This should leave just one color for BB.
1647 assert(BlockColors[BB].size() == 1);
1651 DEBUG_WITH_TYPE("winehprepare-coloring",
1652 dbgs() << " Cloning block \'" << BB->getName()
1653 << "\' for funclet \'" << FuncletPadBB->getName()
1656 // Create a new basic block and copy instructions into it!
1658 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
1659 // Insert the clone immediately after the original to ensure determinism
1660 // and to keep the same relative ordering of any funclet's blocks.
1661 CBB->insertInto(&F, BB->getNextNode());
1663 // Add basic block mapping.
1666 // Record delta operations that we need to perform to our color mappings.
1667 Orig2Clone[BB] = CBB;
1670 // If nothing was cloned, we're done cloning in this funclet.
1671 if (Orig2Clone.empty())
1674 // Update our color mappings to reflect that one block has lost a color and
1675 // another has gained a color.
1676 for (auto &BBMapping : Orig2Clone) {
1677 BasicBlock *OldBlock = BBMapping.first;
1678 BasicBlock *NewBlock = BBMapping.second;
1680 BlocksInFunclet.insert(NewBlock);
1681 BlockColors[NewBlock].insert(FuncletPadBB);
1683 DEBUG_WITH_TYPE("winehprepare-coloring",
1684 dbgs() << " Assigned color \'" << FuncletPadBB->getName()
1685 << "\' to block \'" << NewBlock->getName()
1688 BlocksInFunclet.erase(OldBlock);
1689 BlockColors[OldBlock].remove(FuncletPadBB);
1691 DEBUG_WITH_TYPE("winehprepare-coloring",
1692 dbgs() << " Removed color \'" << FuncletPadBB->getName()
1693 << "\' from block \'" << OldBlock->getName()
1696 // If we are cloning a funclet that might share a child funclet with
1697 // another funclet, look to see if the cloned block is reached from a
1698 // catchret instruction. If so, save this association so we can retrieve
1699 // the possibly orphaned clone when we clone the child funclet.
1700 if (FuncletCloningRequired) {
1701 for (auto *Pred : predecessors(OldBlock)) {
1702 auto *Terminator = Pred->getTerminator();
1703 if (!isa<CatchReturnInst>(Terminator))
1705 // If this block is reached from a catchret instruction in a funclet
1706 // that has multiple parents, it will have a color for each of those
1707 // parents. We just removed the color of one of the parents, but
1708 // the cloned block will be unreachable until we clone the child
1709 // funclet that contains the catchret instruction. In that case we
1710 // need to create a mapping that will let us find the cloned block
1711 // later and associate it with the cloned child funclet.
1712 bool BlockWillBeEstranged = false;
1713 for (auto *Color : BlockColors[Pred]) {
1714 if (FuncletParents[Color].size() > 1) {
1715 BlockWillBeEstranged = true;
1716 break; // Breaks out of the color loop
1719 if (BlockWillBeEstranged) {
1720 EstrangedBlocks[FuncletPadBB][OldBlock] = NewBlock;
1721 DEBUG_WITH_TYPE("winehprepare-coloring",
1722 dbgs() << " Saved mapping of estranged block \'"
1723 << NewBlock->getName() << "\' for \'"
1724 << FuncletPadBB->getName() << "\'.\n");
1725 break; // Breaks out of the predecessor loop
1731 // Loop over all of the instructions in this funclet, fixing up operand
1732 // references as we go. This uses VMap to do all the hard work.
1733 for (BasicBlock *BB : BlocksInFunclet)
1734 // Loop over all instructions, fixing each one as we find it...
1735 for (Instruction &I : *BB)
1736 RemapInstruction(&I, VMap,
1737 RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
1739 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
1740 // the PHI nodes for NewBB now.
1741 for (auto &BBMapping : Orig2Clone) {
1742 BasicBlock *OldBlock = BBMapping.first;
1743 BasicBlock *NewBlock = BBMapping.second;
1744 for (BasicBlock *SuccBB : successors(NewBlock)) {
1745 for (Instruction &SuccI : *SuccBB) {
1746 auto *SuccPN = dyn_cast<PHINode>(&SuccI);
1750 // Ok, we have a PHI node. Figure out what the incoming value was for
1752 int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
1753 if (OldBlockIdx == -1)
1755 Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
1757 // Remap the value if necessary.
1758 if (auto *Inst = dyn_cast<Instruction>(IV)) {
1759 ValueToValueMapTy::iterator I = VMap.find(Inst);
1760 if (I != VMap.end())
1764 SuccPN->addIncoming(IV, NewBlock);
1769 for (ValueToValueMapTy::value_type VT : VMap) {
1770 // If there were values defined in BB that are used outside the funclet,
1771 // then we now have to update all uses of the value to use either the
1772 // original value, the cloned value, or some PHI derived value. This can
1773 // require arbitrary PHI insertion, of which we are prepared to do, clean
1775 SmallVector<Use *, 16> UsesToRename;
1777 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
1780 auto *NewI = cast<Instruction>(VT.second);
1781 // Scan all uses of this instruction to see if it is used outside of its
1782 // funclet, and if so, record them in UsesToRename.
1783 for (Use &U : OldI->uses()) {
1784 Instruction *UserI = cast<Instruction>(U.getUser());
1785 BasicBlock *UserBB = UserI->getParent();
1786 SetVector<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB];
1787 assert(!ColorsForUserBB.empty());
1788 if (ColorsForUserBB.size() > 1 ||
1789 *ColorsForUserBB.begin() != FuncletPadBB)
1790 UsesToRename.push_back(&U);
1793 // If there are no uses outside the block, we're done with this
1795 if (UsesToRename.empty())
1798 // We found a use of OldI outside of the funclet. Rename all uses of OldI
1799 // that are outside its funclet to be uses of the appropriate PHI node
1801 SSAUpdater SSAUpdate;
1802 SSAUpdate.Initialize(OldI->getType(), OldI->getName());
1803 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
1804 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
1806 while (!UsesToRename.empty())
1807 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
1812 void WinEHPrepare::removeImplausibleTerminators(Function &F) {
1813 // Remove implausible terminators and replace them with UnreachableInst.
1814 for (auto &Funclet : FuncletBlocks) {
1815 BasicBlock *FuncletPadBB = Funclet.first;
1816 std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
1817 Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
1818 auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
1819 auto *CleanupPad = dyn_cast<CleanupPadInst>(FirstNonPHI);
1821 for (BasicBlock *BB : BlocksInFunclet) {
1822 TerminatorInst *TI = BB->getTerminator();
1823 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
1824 bool IsUnreachableRet = isa<ReturnInst>(TI) && (CatchPad || CleanupPad);
1825 // The token consumed by a CatchReturnInst must match the funclet token.
1826 bool IsUnreachableCatchret = false;
1827 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
1828 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
1829 // The token consumed by a CleanupReturnInst must match the funclet token.
1830 bool IsUnreachableCleanupret = false;
1831 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
1832 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
1833 // The token consumed by a CleanupEndPadInst must match the funclet token.
1834 bool IsUnreachableCleanupendpad = false;
1835 if (auto *CEPI = dyn_cast<CleanupEndPadInst>(TI))
1836 IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad;
1837 if (IsUnreachableRet || IsUnreachableCatchret ||
1838 IsUnreachableCleanupret || IsUnreachableCleanupendpad) {
1839 // Loop through all of our successors and make sure they know that one
1840 // of their predecessors is going away.
1841 for (BasicBlock *SuccBB : TI->successors())
1842 SuccBB->removePredecessor(BB);
1844 if (IsUnreachableCleanupendpad) {
1845 // We can't simply replace a cleanupendpad with unreachable, because
1846 // its predecessor edges are EH edges and unreachable is not an EH
1847 // pad. Change all predecessors to the "unwind to caller" form.
1848 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1850 BasicBlock *Pred = *PI++;
1851 removeUnwindEdge(Pred);
1855 new UnreachableInst(BB->getContext(), TI);
1856 TI->eraseFromParent();
1858 // FIXME: Check for invokes/cleanuprets/cleanupendpads which unwind to
1859 // implausible catchendpads (i.e. catchendpad not in immediate parent
1865 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
1866 // Clean-up some of the mess we made by removing useles PHI nodes, trivial
1868 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
1869 BasicBlock *BB = &*FI++;
1870 SimplifyInstructionsInBlock(BB);
1871 ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
1872 MergeBlockIntoPredecessor(BB);
1875 // We might have some unreachable blocks after cleaning up some impossible
1877 removeUnreachableBlocks(F);
1880 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
1881 // Recolor the CFG to verify that all is well.
1882 for (BasicBlock &BB : F) {
1883 size_t NumColors = BlockColors[&BB].size();
1884 assert(NumColors == 1 && "Expected monochromatic BB!");
1886 report_fatal_error("Uncolored BB!");
1888 report_fatal_error("Multicolor BB!");
1889 bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
1890 assert(!EHPadHasPHI && "EH Pad still has a PHI!");
1892 report_fatal_error("EH Pad still has a PHI!");
1896 bool WinEHPrepare::prepareExplicitEH(
1897 Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
1898 replaceTerminatePadWithCleanup(F);
1900 // Determine which blocks are reachable from which funclet entries.
1901 colorFunclets(F, EntryBlocks);
1903 if (!DisableDemotion)
1904 demotePHIsOnFunclets(F);
1906 cloneCommonBlocks(F, EntryBlocks);
1908 resolveFuncletAncestry(F, EntryBlocks);
1910 if (!DisableCleanups) {
1911 removeImplausibleTerminators(F);
1913 cleanupPreparedFunclets(F);
1916 verifyPreparedFunclets(F);
1918 BlockColors.clear();
1919 FuncletBlocks.clear();
1920 FuncletChildren.clear();
1921 FuncletParents.clear();
1922 EstrangedBlocks.clear();
1923 FuncletCloningRequired = false;
1928 // TODO: Share loads when one use dominates another, or when a catchpad exit
1929 // dominates uses (needs dominators).
1930 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1931 BasicBlock *PHIBlock = PN->getParent();
1932 AllocaInst *SpillSlot = nullptr;
1934 if (isa<CleanupPadInst>(PHIBlock->getFirstNonPHI())) {
1935 // Insert a load in place of the PHI and replace all uses.
1936 SpillSlot = new AllocaInst(PN->getType(), nullptr,
1937 Twine(PN->getName(), ".wineh.spillslot"),
1938 &F.getEntryBlock().front());
1939 Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
1940 &*PHIBlock->getFirstInsertionPt());
1941 PN->replaceAllUsesWith(V);
1945 DenseMap<BasicBlock *, Value *> Loads;
1946 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1949 auto *UsingInst = cast<Instruction>(U.getUser());
1950 BasicBlock *UsingBB = UsingInst->getParent();
1951 if (UsingBB->isEHPad()) {
1952 // Use is on an EH pad phi. Leave it alone; we'll insert loads and
1953 // stores for it separately.
1954 assert(isa<PHINode>(UsingInst));
1957 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1962 // TODO: improve store placement. Inserting at def is probably good, but need
1963 // to be careful not to introduce interfering stores (needs liveness analysis).
1964 // TODO: identify related phi nodes that can share spill slots, and share them
1965 // (also needs liveness).
1966 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1967 AllocaInst *SpillSlot) {
1968 // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1969 // stored to the spill slot by the end of the given Block.
1970 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1972 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1974 while (!Worklist.empty()) {
1975 BasicBlock *EHBlock;
1977 std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1979 PHINode *PN = dyn_cast<PHINode>(InVal);
1980 if (PN && PN->getParent() == EHBlock) {
1981 // The value is defined by another PHI we need to remove, with no room to
1982 // insert a store after the PHI, so each predecessor needs to store its
1984 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1985 Value *PredVal = PN->getIncomingValue(i);
1987 // Undef can safely be skipped.
1988 if (isa<UndefValue>(PredVal))
1991 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1994 // We need to store InVal, which dominates EHBlock, but can't put a store
1995 // in EHBlock, so need to put stores in each predecessor.
1996 for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1997 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
2003 void WinEHPrepare::insertPHIStore(
2004 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
2005 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
2007 if (PredBlock->isEHPad() &&
2008 !isa<CleanupPadInst>(PredBlock->getFirstNonPHI())) {
2009 // Pred is unsplittable, so we need to queue it on the worklist.
2010 Worklist.push_back({PredBlock, PredVal});
2014 // Otherwise, insert the store at the end of the basic block.
2015 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
2018 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
2019 DenseMap<BasicBlock *, Value *> &Loads,
2021 // Lazilly create the spill slot.
2023 SpillSlot = new AllocaInst(V->getType(), nullptr,
2024 Twine(V->getName(), ".wineh.spillslot"),
2025 &F.getEntryBlock().front());
2027 auto *UsingInst = cast<Instruction>(U.getUser());
2028 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
2029 // If this is a PHI node, we can't insert a load of the value before
2030 // the use. Instead insert the load in the predecessor block
2031 // corresponding to the incoming value.
2033 // Note that if there are multiple edges from a basic block to this
2034 // PHI node that we cannot have multiple loads. The problem is that
2035 // the resulting PHI node will have multiple values (from each load)
2036 // coming in from the same block, which is illegal SSA form.
2037 // For this reason, we keep track of and reuse loads we insert.
2038 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
2039 if (auto *CatchRet =
2040 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
2041 // Putting a load above a catchret and use on the phi would still leave
2042 // a cross-funclet def/use. We need to split the edge, change the
2043 // catchret to target the new block, and put the load there.
2044 BasicBlock *PHIBlock = UsingInst->getParent();
2045 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
2046 // SplitEdge gives us:
2049 // br label %NewBlock
2051 // catchret label %PHIBlock
2055 // catchret label %NewBlock
2057 // br label %PHIBlock
2058 // So move the terminators to each others' blocks and swap their
2060 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
2061 Goto->removeFromParent();
2062 CatchRet->removeFromParent();
2063 IncomingBlock->getInstList().push_back(CatchRet);
2064 NewBlock->getInstList().push_back(Goto);
2065 Goto->setSuccessor(0, PHIBlock);
2066 CatchRet->setSuccessor(NewBlock);
2067 // Update the color mapping for the newly split edge.
2068 SetVector<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock];
2069 BlockColors[NewBlock] = ColorsForPHIBlock;
2070 for (BasicBlock *FuncletPad : ColorsForPHIBlock)
2071 FuncletBlocks[FuncletPad].insert(NewBlock);
2072 // Treat the new block as incoming for load insertion.
2073 IncomingBlock = NewBlock;
2075 Value *&Load = Loads[IncomingBlock];
2076 // Insert the load into the predecessor block
2078 Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
2079 /*Volatile=*/false, IncomingBlock->getTerminator());
2083 // Reload right before the old use.
2084 auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
2085 /*Volatile=*/false, UsingInst);
2090 void WinEHFuncInfo::addIPToStateRange(const BasicBlock *PadBB,
2091 MCSymbol *InvokeBegin,
2092 MCSymbol *InvokeEnd) {
2093 assert(PadBB->isEHPad() && EHPadStateMap.count(PadBB->getFirstNonPHI()) &&
2094 "should get EH pad BB with precomputed state");
2095 InvokeToStateMap[InvokeBegin] =
2096 std::make_pair(EHPadStateMap[PadBB->getFirstNonPHI()], InvokeEnd);