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/MapVector.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallSet.h"
23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/ADT/Triple.h"
25 #include "llvm/ADT/TinyPtrVector.h"
26 #include "llvm/Analysis/CFG.h"
27 #include "llvm/Analysis/LibCallSemantics.h"
28 #include "llvm/Analysis/TargetLibraryInfo.h"
29 #include "llvm/CodeGen/WinEHFuncInfo.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/IR/IRBuilder.h"
33 #include "llvm/IR/Instructions.h"
34 #include "llvm/IR/IntrinsicInst.h"
35 #include "llvm/IR/Module.h"
36 #include "llvm/IR/PatternMatch.h"
37 #include "llvm/MC/MCSymbol.h"
38 #include "llvm/Pass.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Support/raw_ostream.h"
41 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
42 #include "llvm/Transforms/Utils/Cloning.h"
43 #include "llvm/Transforms/Utils/Local.h"
44 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
45 #include "llvm/Transforms/Utils/SSAUpdater.h"
49 using namespace llvm::PatternMatch;
51 #define DEBUG_TYPE "winehprepare"
53 static cl::opt<bool> DisableDemotion(
54 "disable-demotion", cl::Hidden,
56 "Clone multicolor basic blocks but do not demote cross funclet values"),
59 static cl::opt<bool> DisableCleanups(
60 "disable-cleanups", cl::Hidden,
61 cl::desc("Do not remove implausible terminators or other similar cleanups"),
66 class WinEHPrepare : public FunctionPass {
68 static char ID; // Pass identification, replacement for typeid.
69 WinEHPrepare(const TargetMachine *TM = nullptr)
72 TheTriple = TM->getTargetTriple();
75 bool runOnFunction(Function &Fn) override;
77 bool doFinalization(Module &M) override;
79 void getAnalysisUsage(AnalysisUsage &AU) const override;
81 const char *getPassName() const override {
82 return "Windows exception handling preparation";
86 void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
88 insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
89 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
90 AllocaInst *insertPHILoads(PHINode *PN, Function &F);
91 void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
92 DenseMap<BasicBlock *, Value *> &Loads, Function &F);
93 void demoteNonlocalUses(Value *V, std::set<BasicBlock *> &ColorsForBB,
95 bool prepareExplicitEH(Function &F,
96 SmallVectorImpl<BasicBlock *> &EntryBlocks);
97 void replaceTerminatePadWithCleanup(Function &F);
98 void colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks);
99 void demotePHIsOnFunclets(Function &F);
100 void demoteUsesBetweenFunclets(Function &F);
101 void demoteArgumentUses(Function &F);
102 void cloneCommonBlocks(Function &F,
103 SmallVectorImpl<BasicBlock *> &EntryBlocks);
104 void removeImplausibleTerminators(Function &F);
105 void cleanupPreparedFunclets(Function &F);
106 void verifyPreparedFunclets(Function &F);
110 // All fields are reset by runOnFunction.
111 EHPersonality Personality = EHPersonality::Unknown;
113 std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
114 std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
115 std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
118 } // end anonymous namespace
120 char WinEHPrepare::ID = 0;
121 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
124 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
125 return new WinEHPrepare(TM);
128 static void findFuncletEntryPoints(Function &Fn,
129 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
130 EntryBlocks.push_back(&Fn.getEntryBlock());
131 for (BasicBlock &BB : Fn) {
132 Instruction *First = BB.getFirstNonPHI();
133 if (!First->isEHPad())
135 assert(!isa<LandingPadInst>(First) &&
136 "landingpad cannot be used with funclet EH personality");
137 // Find EH pad blocks that represent funclet start points.
138 if (!isa<CatchEndPadInst>(First) && !isa<CleanupEndPadInst>(First))
139 EntryBlocks.push_back(&BB);
143 bool WinEHPrepare::runOnFunction(Function &Fn) {
144 if (!Fn.hasPersonalityFn())
147 // Classify the personality to see what kind of preparation we need.
148 Personality = classifyEHPersonality(Fn.getPersonalityFn());
150 // Do nothing if this is not a funclet-based personality.
151 if (!isFuncletEHPersonality(Personality))
154 // Remove unreachable blocks. It is not valuable to assign them a color and
155 // their existence can trick us into thinking values are alive when they are
157 removeUnreachableBlocks(Fn);
159 SmallVector<BasicBlock *, 4> EntryBlocks;
160 findFuncletEntryPoints(Fn, EntryBlocks);
161 return prepareExplicitEH(Fn, EntryBlocks);
164 bool WinEHPrepare::doFinalization(Module &M) { return false; }
166 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {
167 AU.addRequired<DominatorTreeWrapperPass>();
168 AU.addRequired<TargetLibraryInfoWrapperPass>();
171 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
172 const BasicBlock *BB) {
173 CxxUnwindMapEntry UME;
174 UME.ToState = ToState;
176 FuncInfo.CxxUnwindMap.push_back(UME);
177 return FuncInfo.getLastStateNumber();
180 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
181 int TryHigh, int CatchHigh,
182 ArrayRef<const CatchPadInst *> Handlers) {
183 WinEHTryBlockMapEntry TBME;
184 TBME.TryLow = TryLow;
185 TBME.TryHigh = TryHigh;
186 TBME.CatchHigh = CatchHigh;
187 assert(TBME.TryLow <= TBME.TryHigh);
188 for (const CatchPadInst *CPI : Handlers) {
190 Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
191 if (TypeInfo->isNullValue())
192 HT.TypeDescriptor = nullptr;
194 HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
195 HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
196 HT.Handler = CPI->getParent();
197 if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
198 HT.CatchObj.Alloca = nullptr;
200 HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
201 TBME.HandlerArray.push_back(HT);
203 FuncInfo.TryBlockMap.push_back(TBME);
206 static const CatchPadInst *getSingleCatchPadPredecessor(const BasicBlock *BB) {
207 for (const BasicBlock *PredBlock : predecessors(BB))
208 if (auto *CPI = dyn_cast<CatchPadInst>(PredBlock->getFirstNonPHI()))
213 /// Find all the catchpads that feed directly into the catchendpad. Frontends
214 /// using this personality should ensure that each catchendpad and catchpad has
215 /// one or zero catchpad predecessors.
217 /// The following C++ generates the IR after it:
225 /// catchpad [i8* A typeinfo]
226 /// to label %catch.A unwind label %catchpad.B
228 /// catchpad [i8* B typeinfo]
229 /// to label %catch.B unwind label %endcatches
231 /// catchendblock unwind to caller
233 findCatchPadsForCatchEndPad(const BasicBlock *CatchEndBB,
234 SmallVectorImpl<const CatchPadInst *> &Handlers) {
235 const CatchPadInst *CPI = getSingleCatchPadPredecessor(CatchEndBB);
237 Handlers.push_back(CPI);
238 CPI = getSingleCatchPadPredecessor(CPI->getParent());
240 // We've pushed these back into reverse source order. Reverse them to get
241 // the list back into source order.
242 std::reverse(Handlers.begin(), Handlers.end());
245 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
246 // to. If the unwind edge came from an invoke, return null.
247 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB) {
248 const TerminatorInst *TI = BB->getTerminator();
249 if (isa<InvokeInst>(TI))
253 return cast<CleanupReturnInst>(TI)->getCleanupPad()->getParent();
256 static void calculateExplicitCXXStateNumbers(WinEHFuncInfo &FuncInfo,
257 const BasicBlock &BB,
259 assert(BB.isEHPad());
260 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
261 // All catchpad instructions will be handled when we process their
262 // respective catchendpad instruction.
263 if (isa<CatchPadInst>(FirstNonPHI))
266 if (isa<CatchEndPadInst>(FirstNonPHI)) {
267 SmallVector<const CatchPadInst *, 2> Handlers;
268 findCatchPadsForCatchEndPad(&BB, Handlers);
269 const BasicBlock *FirstTryPad = Handlers.front()->getParent();
270 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
271 FuncInfo.EHPadStateMap[Handlers.front()] = TryLow;
272 for (const BasicBlock *PredBlock : predecessors(FirstTryPad))
273 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
274 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, TryLow);
275 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
277 // catchpads are separate funclets in C++ EH due to the way rethrow works.
278 // In SEH, they aren't, so no invokes will unwind to the catchendpad.
279 FuncInfo.EHPadStateMap[FirstNonPHI] = CatchLow;
280 int TryHigh = CatchLow - 1;
281 for (const BasicBlock *PredBlock : predecessors(&BB))
282 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
283 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CatchLow);
284 int CatchHigh = FuncInfo.getLastStateNumber();
285 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
286 DEBUG(dbgs() << "TryLow[" << FirstTryPad->getName() << "]: " << TryLow
288 DEBUG(dbgs() << "TryHigh[" << FirstTryPad->getName() << "]: " << TryHigh
290 DEBUG(dbgs() << "CatchHigh[" << FirstTryPad->getName() << "]: " << CatchHigh
292 } else if (isa<CleanupPadInst>(FirstNonPHI)) {
293 // A cleanup can have multiple exits; don't re-process after the first.
294 if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
296 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, &BB);
297 FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
298 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
299 << BB.getName() << '\n');
300 for (const BasicBlock *PredBlock : predecessors(&BB))
301 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
302 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, CleanupState);
303 } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
304 // Propagate ParentState to the cleanuppad in case it doesn't have
306 BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
307 calculateExplicitCXXStateNumbers(FuncInfo, *CleanupBlock, ParentState);
308 // Anything unwinding through CleanupEndPadInst is in ParentState.
309 FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
310 for (const BasicBlock *PredBlock : predecessors(&BB))
311 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
312 calculateExplicitCXXStateNumbers(FuncInfo, *PredBlock, ParentState);
313 } else if (isa<TerminatePadInst>(FirstNonPHI)) {
314 report_fatal_error("Not yet implemented!");
316 llvm_unreachable("unexpected EH Pad!");
320 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
321 const Function *Filter, const BasicBlock *Handler) {
322 SEHUnwindMapEntry Entry;
323 Entry.ToState = ParentState;
324 Entry.IsFinally = false;
325 Entry.Filter = Filter;
326 Entry.Handler = Handler;
327 FuncInfo.SEHUnwindMap.push_back(Entry);
328 return FuncInfo.SEHUnwindMap.size() - 1;
331 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
332 const BasicBlock *Handler) {
333 SEHUnwindMapEntry Entry;
334 Entry.ToState = ParentState;
335 Entry.IsFinally = true;
336 Entry.Filter = nullptr;
337 Entry.Handler = Handler;
338 FuncInfo.SEHUnwindMap.push_back(Entry);
339 return FuncInfo.SEHUnwindMap.size() - 1;
342 static void calculateExplicitSEHStateNumbers(WinEHFuncInfo &FuncInfo,
343 const BasicBlock &BB,
345 assert(BB.isEHPad());
346 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
347 // All catchpad instructions will be handled when we process their
348 // respective catchendpad instruction.
349 if (isa<CatchPadInst>(FirstNonPHI))
352 if (isa<CatchEndPadInst>(FirstNonPHI)) {
353 // Extract the filter function and the __except basic block and create a
355 SmallVector<const CatchPadInst *, 1> Handlers;
356 findCatchPadsForCatchEndPad(&BB, Handlers);
357 assert(Handlers.size() == 1 &&
358 "SEH doesn't have multiple handlers per __try");
359 const CatchPadInst *CPI = Handlers.front();
360 const BasicBlock *CatchPadBB = CPI->getParent();
361 const Constant *FilterOrNull =
362 cast<Constant>(CPI->getArgOperand(0)->stripPointerCasts());
363 const Function *Filter = dyn_cast<Function>(FilterOrNull);
364 assert((Filter || FilterOrNull->isNullValue()) &&
365 "unexpected filter value");
366 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
368 // Everything in the __try block uses TryState as its parent state.
369 FuncInfo.EHPadStateMap[CPI] = TryState;
370 DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
371 << CatchPadBB->getName() << '\n');
372 for (const BasicBlock *PredBlock : predecessors(CatchPadBB))
373 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
374 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, TryState);
376 // Everything in the __except block unwinds to ParentState, just like code
377 // outside the __try.
378 FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
379 DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
380 << BB.getName() << '\n');
381 for (const BasicBlock *PredBlock : predecessors(&BB))
382 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
383 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
384 } else if (isa<CleanupPadInst>(FirstNonPHI)) {
385 // A cleanup can have multiple exits; don't re-process after the first.
386 if (FuncInfo.EHPadStateMap.count(FirstNonPHI))
388 int CleanupState = addSEHFinally(FuncInfo, ParentState, &BB);
389 FuncInfo.EHPadStateMap[FirstNonPHI] = CleanupState;
390 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
391 << BB.getName() << '\n');
392 for (const BasicBlock *PredBlock : predecessors(&BB))
393 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
394 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, CleanupState);
395 } else if (auto *CEPI = dyn_cast<CleanupEndPadInst>(FirstNonPHI)) {
396 // Propagate ParentState to the cleanuppad in case it doesn't have
398 BasicBlock *CleanupBlock = CEPI->getCleanupPad()->getParent();
399 calculateExplicitSEHStateNumbers(FuncInfo, *CleanupBlock, ParentState);
400 // Anything unwinding through CleanupEndPadInst is in ParentState.
401 FuncInfo.EHPadStateMap[FirstNonPHI] = ParentState;
402 DEBUG(dbgs() << "Assigning state #" << ParentState << " to BB "
403 << BB.getName() << '\n');
404 for (const BasicBlock *PredBlock : predecessors(&BB))
405 if ((PredBlock = getEHPadFromPredecessor(PredBlock)))
406 calculateExplicitSEHStateNumbers(FuncInfo, *PredBlock, ParentState);
407 } else if (isa<TerminatePadInst>(FirstNonPHI)) {
408 report_fatal_error("Not yet implemented!");
410 llvm_unreachable("unexpected EH Pad!");
414 /// Check if the EH Pad unwinds to caller. Cleanups are a little bit of a
415 /// special case because we have to look at the cleanupret instruction that uses
417 static bool doesEHPadUnwindToCaller(const Instruction *EHPad) {
418 auto *CPI = dyn_cast<CleanupPadInst>(EHPad);
420 return EHPad->mayThrow();
422 // This cleanup does not return or unwind, so we say it unwinds to caller.
423 if (CPI->use_empty())
426 const Instruction *User = CPI->user_back();
427 if (auto *CRI = dyn_cast<CleanupReturnInst>(User))
428 return CRI->unwindsToCaller();
429 return cast<CleanupEndPadInst>(User)->unwindsToCaller();
432 void llvm::calculateSEHStateNumbers(const Function *Fn,
433 WinEHFuncInfo &FuncInfo) {
434 // Don't compute state numbers twice.
435 if (!FuncInfo.SEHUnwindMap.empty())
438 for (const BasicBlock &BB : *Fn) {
439 if (!BB.isEHPad() || !doesEHPadUnwindToCaller(BB.getFirstNonPHI()))
441 calculateExplicitSEHStateNumbers(FuncInfo, BB, -1);
445 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
446 WinEHFuncInfo &FuncInfo) {
447 // Return if it's already been done.
448 if (!FuncInfo.EHPadStateMap.empty())
451 for (const BasicBlock &BB : *Fn) {
454 if (BB.isLandingPad())
455 report_fatal_error("MSVC C++ EH cannot use landingpads");
456 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
457 if (!doesEHPadUnwindToCaller(FirstNonPHI))
459 calculateExplicitCXXStateNumbers(FuncInfo, BB, -1);
463 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
464 ClrHandlerType HandlerType, uint32_t TypeToken,
465 const BasicBlock *Handler) {
466 ClrEHUnwindMapEntry Entry;
467 Entry.Parent = ParentState;
468 Entry.Handler = Handler;
469 Entry.HandlerType = HandlerType;
470 Entry.TypeToken = TypeToken;
471 FuncInfo.ClrEHUnwindMap.push_back(Entry);
472 return FuncInfo.ClrEHUnwindMap.size() - 1;
475 void llvm::calculateClrEHStateNumbers(const Function *Fn,
476 WinEHFuncInfo &FuncInfo) {
477 // Return if it's already been done.
478 if (!FuncInfo.EHPadStateMap.empty())
481 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
483 // Each pad needs to be able to refer to its parent, so scan the function
484 // looking for top-level handlers and seed the worklist with them.
485 for (const BasicBlock &BB : *Fn) {
488 if (BB.isLandingPad())
489 report_fatal_error("CoreCLR EH cannot use landingpads");
490 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
491 if (!doesEHPadUnwindToCaller(FirstNonPHI))
493 // queue this with sentinel parent state -1 to mean unwind to caller.
494 Worklist.emplace_back(FirstNonPHI, -1);
497 while (!Worklist.empty()) {
498 const Instruction *Pad;
500 std::tie(Pad, ParentState) = Worklist.pop_back_val();
503 if (const CleanupEndPadInst *EndPad = dyn_cast<CleanupEndPadInst>(Pad)) {
504 FuncInfo.EHPadStateMap[EndPad] = ParentState;
505 // Queue the cleanuppad, in case it doesn't have a cleanupret.
506 Worklist.emplace_back(EndPad->getCleanupPad(), ParentState);
507 // Preds of the endpad should get the parent state.
508 PredState = ParentState;
509 } else if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
510 // A cleanup can have multiple exits; don't re-process after the first.
511 if (FuncInfo.EHPadStateMap.count(Pad))
513 // CoreCLR personality uses arity to distinguish faults from finallies.
514 const BasicBlock *PadBlock = Cleanup->getParent();
515 ClrHandlerType HandlerType =
516 (Cleanup->getNumOperands() ? ClrHandlerType::Fault
517 : ClrHandlerType::Finally);
519 addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
520 FuncInfo.EHPadStateMap[Cleanup] = NewState;
521 // Propagate the new state to all preds of the cleanup
522 PredState = NewState;
523 } else if (const CatchEndPadInst *EndPad = dyn_cast<CatchEndPadInst>(Pad)) {
524 FuncInfo.EHPadStateMap[EndPad] = ParentState;
525 // Preds of the endpad should get the parent state.
526 PredState = ParentState;
527 } else if (const CatchPadInst *Catch = dyn_cast<CatchPadInst>(Pad)) {
528 const BasicBlock *PadBlock = Catch->getParent();
529 uint32_t TypeToken = static_cast<uint32_t>(
530 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
531 int NewState = addClrEHHandler(FuncInfo, ParentState,
532 ClrHandlerType::Catch, TypeToken, PadBlock);
533 FuncInfo.EHPadStateMap[Catch] = NewState;
534 // Preds of the catch get its state
535 PredState = NewState;
537 llvm_unreachable("Unexpected EH pad");
540 // Queue all predecessors with the given state
541 for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
542 if ((Pred = getEHPadFromPredecessor(Pred)))
543 Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
548 void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) {
549 if (Personality != EHPersonality::MSVC_CXX)
551 for (BasicBlock &BB : F) {
552 Instruction *First = BB.getFirstNonPHI();
553 auto *TPI = dyn_cast<TerminatePadInst>(First);
557 if (TPI->getNumArgOperands() != 1)
559 "Expected a unary terminatepad for MSVC C++ personalities!");
561 auto *TerminateFn = dyn_cast<Function>(TPI->getArgOperand(0));
563 report_fatal_error("Function operand expected in terminatepad for MSVC "
564 "C++ personalities!");
566 // Insert the cleanuppad instruction.
567 auto *CPI = CleanupPadInst::Create(
568 BB.getContext(), {}, Twine("terminatepad.for.", BB.getName()), &BB);
570 // Insert the call to the terminate instruction.
571 auto *CallTerminate = CallInst::Create(TerminateFn, {}, &BB);
572 CallTerminate->setDoesNotThrow();
573 CallTerminate->setDoesNotReturn();
574 CallTerminate->setCallingConv(TerminateFn->getCallingConv());
576 // Insert a new terminator for the cleanuppad using the same successor as
578 CleanupReturnInst::Create(CPI, TPI->getUnwindDest(), &BB);
580 // Let's remove the terminatepad now that we've inserted the new
582 TPI->eraseFromParent();
587 colorFunclets(Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks,
588 std::map<BasicBlock *, std::set<BasicBlock *>> &BlockColors,
589 std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletBlocks,
590 std::map<BasicBlock *, std::set<BasicBlock *>> &FuncletChildren) {
591 SmallVector<std::pair<BasicBlock *, BasicBlock *>, 16> Worklist;
592 BasicBlock *EntryBlock = &F.getEntryBlock();
594 // Build up the color map, which maps each block to its set of 'colors'.
595 // For any block B, the "colors" of B are the set of funclets F (possibly
596 // including a root "funclet" representing the main function), such that
597 // F will need to directly contain B or a copy of B (where the term "directly
598 // contain" is used to distinguish from being "transitively contained" in
599 // a nested funclet).
600 // Use a CFG walk driven by a worklist of (block, color) pairs. The "color"
601 // sets attached during this processing to a block which is the entry of some
602 // funclet F is actually the set of F's parents -- i.e. the union of colors
603 // of all predecessors of F's entry. For all other blocks, the color sets
604 // are as defined above. A post-pass fixes up the block color map to reflect
605 // the same sense of "color" for funclet entries as for other blocks.
607 Worklist.push_back({EntryBlock, EntryBlock});
609 while (!Worklist.empty()) {
610 BasicBlock *Visiting;
612 std::tie(Visiting, Color) = Worklist.pop_back_val();
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).second)
631 Worklist.push_back({Succ, Color});
634 // Handle CatchPad specially since its successors need different colors.
635 if (CatchPadInst *CatchPad = dyn_cast<CatchPadInst>(VisitingHead)) {
636 // Visit the normal successor with the color of the new EH pad, and
637 // visit the unwind successor with the color of the parent.
638 BasicBlock *NormalSucc = CatchPad->getNormalDest();
639 if (BlockColors[NormalSucc].insert(Visiting).second) {
640 Worklist.push_back({NormalSucc, Visiting});
642 BasicBlock *UnwindSucc = CatchPad->getUnwindDest();
643 if (BlockColors[UnwindSucc].insert(Color).second) {
644 Worklist.push_back({UnwindSucc, Color});
648 // Switch color to the current node, except for terminate pads which
649 // have no bodies and only unwind successors and so need their successors
650 // visited with the color of the parent.
651 if (!isa<TerminatePadInst>(VisitingHead))
654 // Note that this is a member of the given color.
655 FuncletBlocks[Color].insert(Visiting);
658 TerminatorInst *Terminator = Visiting->getTerminator();
659 if (isa<CleanupReturnInst>(Terminator) ||
660 isa<CatchReturnInst>(Terminator) ||
661 isa<CleanupEndPadInst>(Terminator)) {
662 // These blocks' successors have already been queued with the parent
666 for (BasicBlock *Succ : successors(Visiting)) {
667 if (isa<CatchEndPadInst>(Succ->getFirstNonPHI())) {
668 // The catchendpad needs to be visited with the parent's color, not
669 // the current color. This will happen in the code above that visits
670 // any catchpad unwind successor with the parent color, so we can
671 // safely skip this successor here.
674 if (BlockColors[Succ].insert(Color).second) {
675 Worklist.push_back({Succ, Color});
680 // The processing above actually accumulated the parent set for this
681 // funclet into the color set for its entry; use the parent set to
682 // populate the children map, and reset the color set to include just
683 // the funclet itself (no instruction can target a funclet entry except on
684 // that transitions to the child funclet).
685 for (BasicBlock *FuncletEntry : EntryBlocks) {
686 std::set<BasicBlock *> &ColorMapItem = BlockColors[FuncletEntry];
687 for (BasicBlock *Parent : ColorMapItem)
688 FuncletChildren[Parent].insert(FuncletEntry);
689 ColorMapItem.clear();
690 ColorMapItem.insert(FuncletEntry);
694 void WinEHPrepare::colorFunclets(Function &F,
695 SmallVectorImpl<BasicBlock *> &EntryBlocks) {
696 ::colorFunclets(F, EntryBlocks, BlockColors, FuncletBlocks, FuncletChildren);
699 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
700 WinEHFuncInfo &FuncInfo) {
701 SmallVector<BasicBlock *, 4> EntryBlocks;
702 // colorFunclets needs the set of EntryBlocks, get them using
703 // findFuncletEntryPoints.
704 findFuncletEntryPoints(const_cast<Function &>(*Fn), EntryBlocks);
706 std::map<BasicBlock *, std::set<BasicBlock *>> BlockColors;
707 std::map<BasicBlock *, std::set<BasicBlock *>> FuncletBlocks;
708 std::map<BasicBlock *, std::set<BasicBlock *>> FuncletChildren;
709 // Figure out which basic blocks belong to which funclets.
710 colorFunclets(const_cast<Function &>(*Fn), EntryBlocks, BlockColors,
711 FuncletBlocks, FuncletChildren);
713 // We need to find the catchret successors. To do this, we must first find
714 // all the catchpad funclets.
715 for (auto &Funclet : FuncletBlocks) {
716 // Figure out what kind of funclet we are looking at; We only care about
718 BasicBlock *FuncletPadBB = Funclet.first;
719 Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
720 auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
724 // The users of a catchpad are always catchrets.
725 for (User *Exit : CatchPad->users()) {
726 auto *CatchReturn = dyn_cast<CatchReturnInst>(Exit);
729 BasicBlock *CatchRetSuccessor = CatchReturn->getSuccessor();
730 std::set<BasicBlock *> &SuccessorColors = BlockColors[CatchRetSuccessor];
731 assert(SuccessorColors.size() == 1 && "Expected BB to be monochrome!");
732 BasicBlock *Color = *SuccessorColors.begin();
733 if (auto *CPI = dyn_cast<CatchPadInst>(Color->getFirstNonPHI()))
734 Color = CPI->getNormalDest();
735 // Record the catchret successor's funclet membership.
736 FuncInfo.CatchRetSuccessorColorMap[CatchReturn] = Color;
741 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
742 // Strip PHI nodes off of EH pads.
743 SmallVector<PHINode *, 16> PHINodes;
744 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
745 BasicBlock *BB = &*FI++;
748 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
749 Instruction *I = &*BI++;
750 auto *PN = dyn_cast<PHINode>(I);
751 // Stop at the first non-PHI.
755 AllocaInst *SpillSlot = insertPHILoads(PN, F);
757 insertPHIStores(PN, SpillSlot);
759 PHINodes.push_back(PN);
763 for (auto *PN : PHINodes) {
764 // There may be lingering uses on other EH PHIs being removed
765 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
766 PN->eraseFromParent();
770 void WinEHPrepare::demoteUsesBetweenFunclets(Function &F) {
771 // Turn all inter-funclet uses of a Value into loads and stores.
772 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
773 BasicBlock *BB = &*FI++;
774 std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
775 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
776 Instruction *I = &*BI++;
777 // Funclets are permitted to use static allocas.
778 if (auto *AI = dyn_cast<AllocaInst>(I))
779 if (AI->isStaticAlloca())
782 demoteNonlocalUses(I, ColorsForBB, F);
787 void WinEHPrepare::demoteArgumentUses(Function &F) {
788 // Also demote function parameters used in funclets.
789 std::set<BasicBlock *> &ColorsForEntry = BlockColors[&F.getEntryBlock()];
790 for (Argument &Arg : F.args())
791 demoteNonlocalUses(&Arg, ColorsForEntry, F);
794 void WinEHPrepare::cloneCommonBlocks(
795 Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
796 // We need to clone all blocks which belong to multiple funclets. Values are
797 // remapped throughout the funclet to propogate both the new instructions
798 // *and* the new basic blocks themselves.
799 for (BasicBlock *FuncletPadBB : EntryBlocks) {
800 std::set<BasicBlock *> &BlocksInFunclet = FuncletBlocks[FuncletPadBB];
802 std::map<BasicBlock *, BasicBlock *> Orig2Clone;
803 ValueToValueMapTy VMap;
804 for (BasicBlock *BB : BlocksInFunclet) {
805 std::set<BasicBlock *> &ColorsForBB = BlockColors[BB];
806 // We don't need to do anything if the block is monochromatic.
807 size_t NumColorsForBB = ColorsForBB.size();
808 if (NumColorsForBB == 1)
811 // Create a new basic block and copy instructions into it!
813 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
814 // Insert the clone immediately after the original to ensure determinism
815 // and to keep the same relative ordering of any funclet's blocks.
816 CBB->insertInto(&F, BB->getNextNode());
818 // Add basic block mapping.
821 // Record delta operations that we need to perform to our color mappings.
822 Orig2Clone[BB] = CBB;
825 // If nothing was cloned, we're done cloning in this funclet.
826 if (Orig2Clone.empty())
829 // Update our color mappings to reflect that one block has lost a color and
830 // another has gained a color.
831 for (auto &BBMapping : Orig2Clone) {
832 BasicBlock *OldBlock = BBMapping.first;
833 BasicBlock *NewBlock = BBMapping.second;
835 BlocksInFunclet.insert(NewBlock);
836 BlockColors[NewBlock].insert(FuncletPadBB);
838 BlocksInFunclet.erase(OldBlock);
839 BlockColors[OldBlock].erase(FuncletPadBB);
842 // Loop over all of the instructions in this funclet, fixing up operand
843 // references as we go. This uses VMap to do all the hard work.
844 for (BasicBlock *BB : BlocksInFunclet)
845 // Loop over all instructions, fixing each one as we find it...
846 for (Instruction &I : *BB)
847 RemapInstruction(&I, VMap,
848 RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
850 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
851 // the PHI nodes for NewBB now.
852 for (auto &BBMapping : Orig2Clone) {
853 BasicBlock *OldBlock = BBMapping.first;
854 BasicBlock *NewBlock = BBMapping.second;
855 for (BasicBlock *SuccBB : successors(NewBlock)) {
856 for (Instruction &SuccI : *SuccBB) {
857 auto *SuccPN = dyn_cast<PHINode>(&SuccI);
861 // Ok, we have a PHI node. Figure out what the incoming value was for
863 int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
864 if (OldBlockIdx == -1)
866 Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
868 // Remap the value if necessary.
869 if (auto *Inst = dyn_cast<Instruction>(IV)) {
870 ValueToValueMapTy::iterator I = VMap.find(Inst);
875 SuccPN->addIncoming(IV, NewBlock);
880 for (ValueToValueMapTy::value_type VT : VMap) {
881 // If there were values defined in BB that are used outside the funclet,
882 // then we now have to update all uses of the value to use either the
883 // original value, the cloned value, or some PHI derived value. This can
884 // require arbitrary PHI insertion, of which we are prepared to do, clean
886 SmallVector<Use *, 16> UsesToRename;
888 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
891 auto *NewI = cast<Instruction>(VT.second);
892 // Scan all uses of this instruction to see if it is used outside of its
893 // funclet, and if so, record them in UsesToRename.
894 for (Use &U : OldI->uses()) {
895 Instruction *UserI = cast<Instruction>(U.getUser());
896 BasicBlock *UserBB = UserI->getParent();
897 std::set<BasicBlock *> &ColorsForUserBB = BlockColors[UserBB];
898 assert(!ColorsForUserBB.empty());
899 if (ColorsForUserBB.size() > 1 ||
900 *ColorsForUserBB.begin() != FuncletPadBB)
901 UsesToRename.push_back(&U);
904 // If there are no uses outside the block, we're done with this
906 if (UsesToRename.empty())
909 // We found a use of OldI outside of the funclet. Rename all uses of OldI
910 // that are outside its funclet to be uses of the appropriate PHI node
912 SSAUpdater SSAUpdate;
913 SSAUpdate.Initialize(OldI->getType(), OldI->getName());
914 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
915 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
917 while (!UsesToRename.empty())
918 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
923 void WinEHPrepare::removeImplausibleTerminators(Function &F) {
924 // Remove implausible terminators and replace them with UnreachableInst.
925 for (auto &Funclet : FuncletBlocks) {
926 BasicBlock *FuncletPadBB = Funclet.first;
927 std::set<BasicBlock *> &BlocksInFunclet = Funclet.second;
928 Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
929 auto *CatchPad = dyn_cast<CatchPadInst>(FirstNonPHI);
930 auto *CleanupPad = dyn_cast<CleanupPadInst>(FirstNonPHI);
932 for (BasicBlock *BB : BlocksInFunclet) {
933 TerminatorInst *TI = BB->getTerminator();
934 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
935 bool IsUnreachableRet = isa<ReturnInst>(TI) && (CatchPad || CleanupPad);
936 // The token consumed by a CatchReturnInst must match the funclet token.
937 bool IsUnreachableCatchret = false;
938 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
939 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
940 // The token consumed by a CleanupReturnInst must match the funclet token.
941 bool IsUnreachableCleanupret = false;
942 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
943 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
944 // The token consumed by a CleanupEndPadInst must match the funclet token.
945 bool IsUnreachableCleanupendpad = false;
946 if (auto *CEPI = dyn_cast<CleanupEndPadInst>(TI))
947 IsUnreachableCleanupendpad = CEPI->getCleanupPad() != CleanupPad;
948 if (IsUnreachableRet || IsUnreachableCatchret ||
949 IsUnreachableCleanupret || IsUnreachableCleanupendpad) {
950 // Loop through all of our successors and make sure they know that one
951 // of their predecessors is going away.
952 for (BasicBlock *SuccBB : TI->successors())
953 SuccBB->removePredecessor(BB);
955 if (IsUnreachableCleanupendpad) {
956 // We can't simply replace a cleanupendpad with unreachable, because
957 // its predecessor edges are EH edges and unreachable is not an EH
958 // pad. Change all predecessors to the "unwind to caller" form.
959 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
961 BasicBlock *Pred = *PI++;
962 removeUnwindEdge(Pred);
966 new UnreachableInst(BB->getContext(), TI);
967 TI->eraseFromParent();
969 // FIXME: Check for invokes/cleanuprets/cleanupendpads which unwind to
970 // implausible catchendpads (i.e. catchendpad not in immediate parent
976 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
977 // Clean-up some of the mess we made by removing useles PHI nodes, trivial
979 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
980 BasicBlock *BB = &*FI++;
981 SimplifyInstructionsInBlock(BB);
982 ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
983 MergeBlockIntoPredecessor(BB);
986 // We might have some unreachable blocks after cleaning up some impossible
988 removeUnreachableBlocks(F);
991 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
992 // Recolor the CFG to verify that all is well.
993 for (BasicBlock &BB : F) {
994 size_t NumColors = BlockColors[&BB].size();
995 assert(NumColors == 1 && "Expected monochromatic BB!");
997 report_fatal_error("Uncolored BB!");
999 report_fatal_error("Multicolor BB!");
1000 if (!DisableDemotion) {
1001 bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
1002 assert(!EHPadHasPHI && "EH Pad still has a PHI!");
1004 report_fatal_error("EH Pad still has a PHI!");
1009 bool WinEHPrepare::prepareExplicitEH(
1010 Function &F, SmallVectorImpl<BasicBlock *> &EntryBlocks) {
1011 replaceTerminatePadWithCleanup(F);
1013 // Determine which blocks are reachable from which funclet entries.
1014 colorFunclets(F, EntryBlocks);
1016 if (!DisableDemotion) {
1017 demotePHIsOnFunclets(F);
1019 demoteUsesBetweenFunclets(F);
1021 demoteArgumentUses(F);
1024 cloneCommonBlocks(F, EntryBlocks);
1026 if (!DisableCleanups) {
1027 removeImplausibleTerminators(F);
1029 cleanupPreparedFunclets(F);
1032 verifyPreparedFunclets(F);
1034 BlockColors.clear();
1035 FuncletBlocks.clear();
1036 FuncletChildren.clear();
1041 // TODO: Share loads when one use dominates another, or when a catchpad exit
1042 // dominates uses (needs dominators).
1043 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
1044 BasicBlock *PHIBlock = PN->getParent();
1045 AllocaInst *SpillSlot = nullptr;
1047 if (isa<CleanupPadInst>(PHIBlock->getFirstNonPHI())) {
1048 // Insert a load in place of the PHI and replace all uses.
1049 SpillSlot = new AllocaInst(PN->getType(), nullptr,
1050 Twine(PN->getName(), ".wineh.spillslot"),
1051 &F.getEntryBlock().front());
1052 Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
1053 &*PHIBlock->getFirstInsertionPt());
1054 PN->replaceAllUsesWith(V);
1058 DenseMap<BasicBlock *, Value *> Loads;
1059 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
1062 auto *UsingInst = cast<Instruction>(U.getUser());
1063 BasicBlock *UsingBB = UsingInst->getParent();
1064 if (UsingBB->isEHPad()) {
1065 // Use is on an EH pad phi. Leave it alone; we'll insert loads and
1066 // stores for it separately.
1067 assert(isa<PHINode>(UsingInst));
1070 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
1075 // TODO: improve store placement. Inserting at def is probably good, but need
1076 // to be careful not to introduce interfering stores (needs liveness analysis).
1077 // TODO: identify related phi nodes that can share spill slots, and share them
1078 // (also needs liveness).
1079 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
1080 AllocaInst *SpillSlot) {
1081 // Use a worklist of (Block, Value) pairs -- the given Value needs to be
1082 // stored to the spill slot by the end of the given Block.
1083 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
1085 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
1087 while (!Worklist.empty()) {
1088 BasicBlock *EHBlock;
1090 std::tie(EHBlock, InVal) = Worklist.pop_back_val();
1092 PHINode *PN = dyn_cast<PHINode>(InVal);
1093 if (PN && PN->getParent() == EHBlock) {
1094 // The value is defined by another PHI we need to remove, with no room to
1095 // insert a store after the PHI, so each predecessor needs to store its
1097 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
1098 Value *PredVal = PN->getIncomingValue(i);
1100 // Undef can safely be skipped.
1101 if (isa<UndefValue>(PredVal))
1104 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
1107 // We need to store InVal, which dominates EHBlock, but can't put a store
1108 // in EHBlock, so need to put stores in each predecessor.
1109 for (BasicBlock *PredBlock : predecessors(EHBlock)) {
1110 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
1116 void WinEHPrepare::insertPHIStore(
1117 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
1118 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
1120 if (PredBlock->isEHPad() &&
1121 !isa<CleanupPadInst>(PredBlock->getFirstNonPHI())) {
1122 // Pred is unsplittable, so we need to queue it on the worklist.
1123 Worklist.push_back({PredBlock, PredVal});
1127 // Otherwise, insert the store at the end of the basic block.
1128 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1131 // TODO: Share loads for same-funclet uses (requires dominators if funclets
1132 // aren't properly nested).
1133 void WinEHPrepare::demoteNonlocalUses(Value *V,
1134 std::set<BasicBlock *> &ColorsForBB,
1136 // Tokens can only be used non-locally due to control flow involving
1137 // unreachable edges. Don't try to demote the token usage, we'll simply
1138 // delete the cloned user later.
1139 if (isa<CatchPadInst>(V) || isa<CleanupPadInst>(V))
1142 DenseMap<BasicBlock *, Value *> Loads;
1143 AllocaInst *SpillSlot = nullptr;
1144 for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE;) {
1146 auto *UsingInst = cast<Instruction>(U.getUser());
1147 BasicBlock *UsingBB = UsingInst->getParent();
1149 // Is the Use inside a block which is colored the same as the Def?
1150 // If so, we don't need to escape the Def because we will clone
1151 // ourselves our own private copy.
1152 std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[UsingBB];
1153 if (ColorsForUsingBB == ColorsForBB)
1156 replaceUseWithLoad(V, U, SpillSlot, Loads, F);
1159 // Insert stores of the computed value into the stack slot.
1160 // We have to be careful if I is an invoke instruction,
1161 // because we can't insert the store AFTER the terminator instruction.
1162 BasicBlock::iterator InsertPt;
1163 if (isa<Argument>(V)) {
1164 InsertPt = F.getEntryBlock().getTerminator()->getIterator();
1165 } else if (isa<TerminatorInst>(V)) {
1166 auto *II = cast<InvokeInst>(V);
1167 // We cannot demote invoke instructions to the stack if their normal
1168 // edge is critical. Therefore, split the critical edge and create a
1169 // basic block into which the store can be inserted.
1170 if (!II->getNormalDest()->getSinglePredecessor()) {
1172 GetSuccessorNumber(II->getParent(), II->getNormalDest());
1173 assert(isCriticalEdge(II, SuccNum) && "Expected a critical edge!");
1174 BasicBlock *NewBlock = SplitCriticalEdge(II, SuccNum);
1175 assert(NewBlock && "Unable to split critical edge.");
1176 // Update the color mapping for the newly split edge.
1177 std::set<BasicBlock *> &ColorsForUsingBB = BlockColors[II->getParent()];
1178 BlockColors[NewBlock] = ColorsForUsingBB;
1179 for (BasicBlock *FuncletPad : ColorsForUsingBB)
1180 FuncletBlocks[FuncletPad].insert(NewBlock);
1182 InsertPt = II->getNormalDest()->getFirstInsertionPt();
1184 InsertPt = cast<Instruction>(V)->getIterator();
1186 // Don't insert before PHI nodes or EH pad instrs.
1187 for (; isa<PHINode>(InsertPt) || InsertPt->isEHPad(); ++InsertPt)
1190 new StoreInst(V, SpillSlot, &*InsertPt);
1194 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1195 DenseMap<BasicBlock *, Value *> &Loads,
1197 // Lazilly create the spill slot.
1199 SpillSlot = new AllocaInst(V->getType(), nullptr,
1200 Twine(V->getName(), ".wineh.spillslot"),
1201 &F.getEntryBlock().front());
1203 auto *UsingInst = cast<Instruction>(U.getUser());
1204 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1205 // If this is a PHI node, we can't insert a load of the value before
1206 // the use. Instead insert the load in the predecessor block
1207 // corresponding to the incoming value.
1209 // Note that if there are multiple edges from a basic block to this
1210 // PHI node that we cannot have multiple loads. The problem is that
1211 // the resulting PHI node will have multiple values (from each load)
1212 // coming in from the same block, which is illegal SSA form.
1213 // For this reason, we keep track of and reuse loads we insert.
1214 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1215 if (auto *CatchRet =
1216 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1217 // Putting a load above a catchret and use on the phi would still leave
1218 // a cross-funclet def/use. We need to split the edge, change the
1219 // catchret to target the new block, and put the load there.
1220 BasicBlock *PHIBlock = UsingInst->getParent();
1221 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1222 // SplitEdge gives us:
1225 // br label %NewBlock
1227 // catchret label %PHIBlock
1231 // catchret label %NewBlock
1233 // br label %PHIBlock
1234 // So move the terminators to each others' blocks and swap their
1236 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1237 Goto->removeFromParent();
1238 CatchRet->removeFromParent();
1239 IncomingBlock->getInstList().push_back(CatchRet);
1240 NewBlock->getInstList().push_back(Goto);
1241 Goto->setSuccessor(0, PHIBlock);
1242 CatchRet->setSuccessor(NewBlock);
1243 // Update the color mapping for the newly split edge.
1244 std::set<BasicBlock *> &ColorsForPHIBlock = BlockColors[PHIBlock];
1245 BlockColors[NewBlock] = ColorsForPHIBlock;
1246 for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1247 FuncletBlocks[FuncletPad].insert(NewBlock);
1248 // Treat the new block as incoming for load insertion.
1249 IncomingBlock = NewBlock;
1251 Value *&Load = Loads[IncomingBlock];
1252 // Insert the load into the predecessor block
1254 Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1255 /*Volatile=*/false, IncomingBlock->getTerminator());
1259 // Reload right before the old use.
1260 auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1261 /*Volatile=*/false, UsingInst);
1266 void WinEHFuncInfo::addIPToStateRange(const BasicBlock *PadBB,
1267 MCSymbol *InvokeBegin,
1268 MCSymbol *InvokeEnd) {
1269 assert(PadBB->isEHPad() && EHPadStateMap.count(PadBB->getFirstNonPHI()) &&
1270 "should get EH pad BB with precomputed state");
1271 InvokeToStateMap[InvokeBegin] =
1272 std::make_pair(EHPadStateMap[PadBB->getFirstNonPHI()], InvokeEnd);