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/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 void colorFunclets(Function &F);
75 void demotePHIsOnFunclets(Function &F);
76 void cloneCommonBlocks(Function &F);
77 void removeImplausibleInstructions(Function &F);
78 void cleanupPreparedFunclets(Function &F);
79 void verifyPreparedFunclets(Function &F);
81 // All fields are reset by runOnFunction.
82 EHPersonality Personality = EHPersonality::Unknown;
84 DenseMap<BasicBlock *, ColorVector> BlockColors;
85 MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
88 } // end anonymous namespace
90 char WinEHPrepare::ID = 0;
91 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
94 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
95 return new WinEHPrepare(TM);
98 bool WinEHPrepare::runOnFunction(Function &Fn) {
99 if (!Fn.hasPersonalityFn())
102 // Classify the personality to see what kind of preparation we need.
103 Personality = classifyEHPersonality(Fn.getPersonalityFn());
105 // Do nothing if this is not a funclet-based personality.
106 if (!isFuncletEHPersonality(Personality))
109 return prepareExplicitEH(Fn);
112 bool WinEHPrepare::doFinalization(Module &M) { return false; }
114 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
116 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
117 const BasicBlock *BB) {
118 CxxUnwindMapEntry UME;
119 UME.ToState = ToState;
121 FuncInfo.CxxUnwindMap.push_back(UME);
122 return FuncInfo.getLastStateNumber();
125 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
126 int TryHigh, int CatchHigh,
127 ArrayRef<const CatchPadInst *> Handlers) {
128 WinEHTryBlockMapEntry TBME;
129 TBME.TryLow = TryLow;
130 TBME.TryHigh = TryHigh;
131 TBME.CatchHigh = CatchHigh;
132 assert(TBME.TryLow <= TBME.TryHigh);
133 for (const CatchPadInst *CPI : Handlers) {
135 Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
136 if (TypeInfo->isNullValue())
137 HT.TypeDescriptor = nullptr;
139 HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
140 HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
141 HT.Handler = CPI->getParent();
142 if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
143 HT.CatchObj.Alloca = nullptr;
145 HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
146 TBME.HandlerArray.push_back(HT);
148 FuncInfo.TryBlockMap.push_back(TBME);
151 static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
152 for (const User *U : CleanupPad->users())
153 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
154 return CRI->getUnwindDest();
158 static void calculateStateNumbersForInvokes(const Function *Fn,
159 WinEHFuncInfo &FuncInfo) {
160 auto *F = const_cast<Function *>(Fn);
161 DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
162 for (BasicBlock &BB : *F) {
163 auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
167 auto &BBColors = BlockColors[&BB];
168 assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
169 BasicBlock *FuncletEntryBB = BBColors.front();
171 BasicBlock *FuncletUnwindDest;
173 dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
174 assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
176 FuncletUnwindDest = nullptr;
177 else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
178 FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
179 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
180 FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
182 llvm_unreachable("unexpected funclet pad!");
184 BasicBlock *InvokeUnwindDest = II->getUnwindDest();
186 if (FuncletUnwindDest == InvokeUnwindDest) {
187 auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
188 if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
189 BaseState = BaseStateI->second;
192 if (BaseState != -1) {
193 FuncInfo.InvokeStateMap[II] = BaseState;
195 Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
196 assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
197 FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
202 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
203 // to. If the unwind edge came from an invoke, return null.
204 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
206 const TerminatorInst *TI = BB->getTerminator();
207 if (isa<InvokeInst>(TI))
209 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
210 if (CatchSwitch->getParentPad() != ParentPad)
214 assert(!TI->isEHPad() && "unexpected EHPad!");
215 auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
216 if (CleanupPad->getParentPad() != ParentPad)
218 return CleanupPad->getParent();
221 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
222 const Instruction *FirstNonPHI,
224 const BasicBlock *BB = FirstNonPHI->getParent();
225 assert(BB->isEHPad() && "not a funclet!");
227 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
228 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
229 "shouldn't revist catch funclets!");
231 SmallVector<const CatchPadInst *, 2> Handlers;
232 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
233 auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
234 Handlers.push_back(CatchPad);
236 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
237 FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
238 for (const BasicBlock *PredBlock : predecessors(BB))
239 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
240 CatchSwitch->getParentPad())))
241 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
243 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
245 // catchpads are separate funclets in C++ EH due to the way rethrow works.
246 int TryHigh = CatchLow - 1;
247 for (const auto *CatchPad : Handlers) {
248 FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
249 for (const User *U : CatchPad->users()) {
250 const auto *UserI = cast<Instruction>(U);
251 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
252 if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
253 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
254 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
255 if (getCleanupRetUnwindDest(InnerCleanupPad) ==
256 CatchSwitch->getUnwindDest())
257 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
260 int CatchHigh = FuncInfo.getLastStateNumber();
261 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
262 DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
263 DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh << '\n');
264 DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
267 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
269 // It's possible for a cleanup to be visited twice: it might have multiple
270 // cleanupret instructions.
271 if (FuncInfo.EHPadStateMap.count(CleanupPad))
274 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
275 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
276 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
277 << BB->getName() << '\n');
278 for (const BasicBlock *PredBlock : predecessors(BB)) {
279 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
280 CleanupPad->getParentPad()))) {
281 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
285 for (const User *U : CleanupPad->users()) {
286 const auto *UserI = cast<Instruction>(U);
287 if (UserI->isEHPad())
288 report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
289 "contain exceptional actions");
294 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
295 const Function *Filter, const BasicBlock *Handler) {
296 SEHUnwindMapEntry Entry;
297 Entry.ToState = ParentState;
298 Entry.IsFinally = false;
299 Entry.Filter = Filter;
300 Entry.Handler = Handler;
301 FuncInfo.SEHUnwindMap.push_back(Entry);
302 return FuncInfo.SEHUnwindMap.size() - 1;
305 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
306 const BasicBlock *Handler) {
307 SEHUnwindMapEntry Entry;
308 Entry.ToState = ParentState;
309 Entry.IsFinally = true;
310 Entry.Filter = nullptr;
311 Entry.Handler = Handler;
312 FuncInfo.SEHUnwindMap.push_back(Entry);
313 return FuncInfo.SEHUnwindMap.size() - 1;
316 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
317 const Instruction *FirstNonPHI,
319 const BasicBlock *BB = FirstNonPHI->getParent();
320 assert(BB->isEHPad() && "no a funclet!");
322 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
323 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
324 "shouldn't revist catch funclets!");
326 // Extract the filter function and the __except basic block and create a
328 assert(CatchSwitch->getNumHandlers() == 1 &&
329 "SEH doesn't have multiple handlers per __try");
330 const auto *CatchPad =
331 cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
332 const BasicBlock *CatchPadBB = CatchPad->getParent();
333 const Constant *FilterOrNull =
334 cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
335 const Function *Filter = dyn_cast<Function>(FilterOrNull);
336 assert((Filter || FilterOrNull->isNullValue()) &&
337 "unexpected filter value");
338 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
340 // Everything in the __try block uses TryState as its parent state.
341 FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
342 DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
343 << CatchPadBB->getName() << '\n');
344 for (const BasicBlock *PredBlock : predecessors(BB))
345 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
346 CatchSwitch->getParentPad())))
347 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
350 // Everything in the __except block unwinds to ParentState, just like code
351 // outside the __try.
352 for (const User *U : CatchPad->users()) {
353 const auto *UserI = cast<Instruction>(U);
354 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
355 if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
356 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
357 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
358 if (getCleanupRetUnwindDest(InnerCleanupPad) ==
359 CatchSwitch->getUnwindDest())
360 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
363 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
365 // It's possible for a cleanup to be visited twice: it might have multiple
366 // cleanupret instructions.
367 if (FuncInfo.EHPadStateMap.count(CleanupPad))
370 int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
371 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
372 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
373 << BB->getName() << '\n');
374 for (const BasicBlock *PredBlock : predecessors(BB))
376 getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
377 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
379 for (const User *U : CleanupPad->users()) {
380 const auto *UserI = cast<Instruction>(U);
381 if (UserI->isEHPad())
382 report_fatal_error("Cleanup funclets for the SEH personality cannot "
383 "contain exceptional actions");
388 static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
389 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
390 return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
391 CatchSwitch->unwindsToCaller();
392 if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
393 return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
394 getCleanupRetUnwindDest(CleanupPad) == nullptr;
395 if (isa<CatchPadInst>(EHPad))
397 llvm_unreachable("unexpected EHPad!");
400 void llvm::calculateSEHStateNumbers(const Function *Fn,
401 WinEHFuncInfo &FuncInfo) {
402 // Don't compute state numbers twice.
403 if (!FuncInfo.SEHUnwindMap.empty())
406 for (const BasicBlock &BB : *Fn) {
409 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
410 if (!isTopLevelPadForMSVC(FirstNonPHI))
412 ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
415 calculateStateNumbersForInvokes(Fn, FuncInfo);
418 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
419 WinEHFuncInfo &FuncInfo) {
420 // Return if it's already been done.
421 if (!FuncInfo.EHPadStateMap.empty())
424 for (const BasicBlock &BB : *Fn) {
427 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
428 if (!isTopLevelPadForMSVC(FirstNonPHI))
430 calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
433 calculateStateNumbersForInvokes(Fn, FuncInfo);
436 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
437 ClrHandlerType HandlerType, uint32_t TypeToken,
438 const BasicBlock *Handler) {
439 ClrEHUnwindMapEntry Entry;
440 Entry.Parent = ParentState;
441 Entry.Handler = Handler;
442 Entry.HandlerType = HandlerType;
443 Entry.TypeToken = TypeToken;
444 FuncInfo.ClrEHUnwindMap.push_back(Entry);
445 return FuncInfo.ClrEHUnwindMap.size() - 1;
448 void llvm::calculateClrEHStateNumbers(const Function *Fn,
449 WinEHFuncInfo &FuncInfo) {
450 // Return if it's already been done.
451 if (!FuncInfo.EHPadStateMap.empty())
454 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
456 // Each pad needs to be able to refer to its parent, so scan the function
457 // looking for top-level handlers and seed the worklist with them.
458 for (const BasicBlock &BB : *Fn) {
461 if (BB.isLandingPad())
462 report_fatal_error("CoreCLR EH cannot use landingpads");
463 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
464 if (!isTopLevelPadForMSVC(FirstNonPHI))
466 // queue this with sentinel parent state -1 to mean unwind to caller.
467 Worklist.emplace_back(FirstNonPHI, -1);
470 while (!Worklist.empty()) {
471 const Instruction *Pad;
473 std::tie(Pad, ParentState) = Worklist.pop_back_val();
477 if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
478 // A cleanup can have multiple exits; don't re-process after the first.
479 if (FuncInfo.EHPadStateMap.count(Cleanup))
481 // CoreCLR personality uses arity to distinguish faults from finallies.
482 const BasicBlock *PadBlock = Cleanup->getParent();
483 ClrHandlerType HandlerType =
484 (Cleanup->getNumOperands() ? ClrHandlerType::Fault
485 : ClrHandlerType::Finally);
487 addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
488 FuncInfo.EHPadStateMap[Cleanup] = NewState;
489 // Propagate the new state to all preds of the cleanup
490 ParentPad = Cleanup->getParentPad();
491 PredState = NewState;
492 } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
493 SmallVector<const CatchPadInst *, 1> Handlers;
494 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
495 const auto *Catch = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
496 Handlers.push_back(Catch);
498 FuncInfo.EHPadStateMap[CatchSwitch] = ParentState;
499 int NewState = ParentState;
500 for (auto HandlerI = Handlers.rbegin(), HandlerE = Handlers.rend();
501 HandlerI != HandlerE; ++HandlerI) {
502 const CatchPadInst *Catch = *HandlerI;
503 const BasicBlock *PadBlock = Catch->getParent();
504 uint32_t TypeToken = static_cast<uint32_t>(
505 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
506 NewState = addClrEHHandler(FuncInfo, NewState, ClrHandlerType::Catch,
507 TypeToken, PadBlock);
508 FuncInfo.EHPadStateMap[Catch] = NewState;
510 for (const auto *CatchPad : Handlers) {
511 for (const User *U : CatchPad->users()) {
512 const auto *UserI = cast<Instruction>(U);
513 if (UserI->isEHPad())
514 Worklist.emplace_back(UserI, ParentState);
517 PredState = NewState;
518 ParentPad = CatchSwitch->getParentPad();
520 llvm_unreachable("Unexpected EH pad");
523 // Queue all predecessors with the given state
524 for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
525 if ((Pred = getEHPadFromPredecessor(Pred, ParentPad)))
526 Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
530 calculateStateNumbersForInvokes(Fn, FuncInfo);
533 void WinEHPrepare::colorFunclets(Function &F) {
534 BlockColors = colorEHFunclets(F);
536 // Invert the map from BB to colors to color to BBs.
537 for (BasicBlock &BB : F) {
538 ColorVector &Colors = BlockColors[&BB];
539 for (BasicBlock *Color : Colors)
540 FuncletBlocks[Color].push_back(&BB);
544 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
545 WinEHFuncInfo &FuncInfo) {
546 for (const BasicBlock &BB : *Fn) {
547 const auto *CatchRet = dyn_cast<CatchReturnInst>(BB.getTerminator());
550 // A 'catchret' returns to the outer scope's color.
551 Value *ParentPad = CatchRet->getParentPad();
552 const BasicBlock *Color;
553 if (isa<ConstantTokenNone>(ParentPad))
554 Color = &Fn->getEntryBlock();
556 Color = cast<Instruction>(ParentPad)->getParent();
557 // Record the catchret successor's funclet membership.
558 FuncInfo.CatchRetSuccessorColorMap[CatchRet] = Color;
562 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
563 // Strip PHI nodes off of EH pads.
564 SmallVector<PHINode *, 16> PHINodes;
565 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
566 BasicBlock *BB = &*FI++;
569 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
570 Instruction *I = &*BI++;
571 auto *PN = dyn_cast<PHINode>(I);
572 // Stop at the first non-PHI.
576 AllocaInst *SpillSlot = insertPHILoads(PN, F);
578 insertPHIStores(PN, SpillSlot);
580 PHINodes.push_back(PN);
584 for (auto *PN : PHINodes) {
585 // There may be lingering uses on other EH PHIs being removed
586 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
587 PN->eraseFromParent();
591 void WinEHPrepare::cloneCommonBlocks(Function &F) {
592 // We need to clone all blocks which belong to multiple funclets. Values are
593 // remapped throughout the funclet to propogate both the new instructions
594 // *and* the new basic blocks themselves.
595 for (auto &Funclets : FuncletBlocks) {
596 BasicBlock *FuncletPadBB = Funclets.first;
597 std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
599 std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
600 ValueToValueMapTy VMap;
601 for (BasicBlock *BB : BlocksInFunclet) {
602 ColorVector &ColorsForBB = BlockColors[BB];
603 // We don't need to do anything if the block is monochromatic.
604 size_t NumColorsForBB = ColorsForBB.size();
605 if (NumColorsForBB == 1)
608 DEBUG_WITH_TYPE("winehprepare-coloring",
609 dbgs() << " Cloning block \'" << BB->getName()
610 << "\' for funclet \'" << FuncletPadBB->getName()
613 // Create a new basic block and copy instructions into it!
615 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
616 // Insert the clone immediately after the original to ensure determinism
617 // and to keep the same relative ordering of any funclet's blocks.
618 CBB->insertInto(&F, BB->getNextNode());
620 // Add basic block mapping.
623 // Record delta operations that we need to perform to our color mappings.
624 Orig2Clone.emplace_back(BB, CBB);
627 // If nothing was cloned, we're done cloning in this funclet.
628 if (Orig2Clone.empty())
631 // Update our color mappings to reflect that one block has lost a color and
632 // another has gained a color.
633 for (auto &BBMapping : Orig2Clone) {
634 BasicBlock *OldBlock = BBMapping.first;
635 BasicBlock *NewBlock = BBMapping.second;
637 BlocksInFunclet.push_back(NewBlock);
638 ColorVector &NewColors = BlockColors[NewBlock];
639 assert(NewColors.empty() && "A new block should only have one color!");
640 NewColors.push_back(FuncletPadBB);
642 DEBUG_WITH_TYPE("winehprepare-coloring",
643 dbgs() << " Assigned color \'" << FuncletPadBB->getName()
644 << "\' to block \'" << NewBlock->getName()
647 BlocksInFunclet.erase(
648 std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
649 BlocksInFunclet.end());
650 ColorVector &OldColors = BlockColors[OldBlock];
652 std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
655 DEBUG_WITH_TYPE("winehprepare-coloring",
656 dbgs() << " Removed color \'" << FuncletPadBB->getName()
657 << "\' from block \'" << OldBlock->getName()
661 // Loop over all of the instructions in this funclet, fixing up operand
662 // references as we go. This uses VMap to do all the hard work.
663 for (BasicBlock *BB : BlocksInFunclet)
664 // Loop over all instructions, fixing each one as we find it...
665 for (Instruction &I : *BB)
666 RemapInstruction(&I, VMap,
667 RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
669 auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
670 unsigned NumPreds = PN->getNumIncomingValues();
671 for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
673 BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
674 ColorVector &IncomingColors = BlockColors[IncomingBlock];
675 bool BlockInFunclet = IncomingColors.size() == 1 &&
676 IncomingColors.front() == FuncletPadBB;
677 if (IsForOldBlock != BlockInFunclet)
679 PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
680 // Revisit the next entry.
686 for (auto &BBMapping : Orig2Clone) {
687 BasicBlock *OldBlock = BBMapping.first;
688 BasicBlock *NewBlock = BBMapping.second;
689 for (Instruction &OldI : *OldBlock) {
690 auto *OldPN = dyn_cast<PHINode>(&OldI);
693 UpdatePHIOnClonedBlock(OldPN, /*IsForOldBlock=*/true);
695 for (Instruction &NewI : *NewBlock) {
696 auto *NewPN = dyn_cast<PHINode>(&NewI);
699 UpdatePHIOnClonedBlock(NewPN, /*IsForOldBlock=*/false);
703 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
704 // the PHI nodes for NewBB now.
705 for (auto &BBMapping : Orig2Clone) {
706 BasicBlock *OldBlock = BBMapping.first;
707 BasicBlock *NewBlock = BBMapping.second;
708 for (BasicBlock *SuccBB : successors(NewBlock)) {
709 for (Instruction &SuccI : *SuccBB) {
710 auto *SuccPN = dyn_cast<PHINode>(&SuccI);
714 // Ok, we have a PHI node. Figure out what the incoming value was for
716 int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
717 if (OldBlockIdx == -1)
719 Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
721 // Remap the value if necessary.
722 if (auto *Inst = dyn_cast<Instruction>(IV)) {
723 ValueToValueMapTy::iterator I = VMap.find(Inst);
728 SuccPN->addIncoming(IV, NewBlock);
733 for (ValueToValueMapTy::value_type VT : VMap) {
734 // If there were values defined in BB that are used outside the funclet,
735 // then we now have to update all uses of the value to use either the
736 // original value, the cloned value, or some PHI derived value. This can
737 // require arbitrary PHI insertion, of which we are prepared to do, clean
739 SmallVector<Use *, 16> UsesToRename;
741 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
744 auto *NewI = cast<Instruction>(VT.second);
745 // Scan all uses of this instruction to see if it is used outside of its
746 // funclet, and if so, record them in UsesToRename.
747 for (Use &U : OldI->uses()) {
748 Instruction *UserI = cast<Instruction>(U.getUser());
749 BasicBlock *UserBB = UserI->getParent();
750 ColorVector &ColorsForUserBB = BlockColors[UserBB];
751 assert(!ColorsForUserBB.empty());
752 if (ColorsForUserBB.size() > 1 ||
753 *ColorsForUserBB.begin() != FuncletPadBB)
754 UsesToRename.push_back(&U);
757 // If there are no uses outside the block, we're done with this
759 if (UsesToRename.empty())
762 // We found a use of OldI outside of the funclet. Rename all uses of OldI
763 // that are outside its funclet to be uses of the appropriate PHI node
765 SSAUpdater SSAUpdate;
766 SSAUpdate.Initialize(OldI->getType(), OldI->getName());
767 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
768 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
770 while (!UsesToRename.empty())
771 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
776 void WinEHPrepare::removeImplausibleInstructions(Function &F) {
777 // Remove implausible terminators and replace them with UnreachableInst.
778 for (auto &Funclet : FuncletBlocks) {
779 BasicBlock *FuncletPadBB = Funclet.first;
780 std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
781 Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
782 auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);
783 auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);
784 auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);
786 for (BasicBlock *BB : BlocksInFunclet) {
787 for (Instruction &I : *BB) {
792 Value *FuncletBundleOperand = nullptr;
793 if (auto BU = CS.getOperandBundle(LLVMContext::OB_funclet))
794 FuncletBundleOperand = BU->Inputs.front();
796 if (FuncletBundleOperand == FuncletPad)
799 // Skip call sites which are nounwind intrinsics.
801 dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
802 if (CalledFn && CalledFn->isIntrinsic() && CS.doesNotThrow())
805 // This call site was not part of this funclet, remove it.
807 // Remove the unwind edge if it was an invoke.
808 removeUnwindEdge(BB);
809 // Get a pointer to the new call.
810 BasicBlock::iterator CallI =
811 std::prev(BB->getTerminator()->getIterator());
812 auto *CI = cast<CallInst>(&*CallI);
813 changeToUnreachable(CI, /*UseLLVMTrap=*/false);
815 changeToUnreachable(&I, /*UseLLVMTrap=*/false);
818 // There are no more instructions in the block (except for unreachable),
823 TerminatorInst *TI = BB->getTerminator();
824 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
825 bool IsUnreachableRet = isa<ReturnInst>(TI) && FuncletPad;
826 // The token consumed by a CatchReturnInst must match the funclet token.
827 bool IsUnreachableCatchret = false;
828 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
829 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
830 // The token consumed by a CleanupReturnInst must match the funclet token.
831 bool IsUnreachableCleanupret = false;
832 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
833 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
834 if (IsUnreachableRet || IsUnreachableCatchret ||
835 IsUnreachableCleanupret) {
836 changeToUnreachable(TI, /*UseLLVMTrap=*/false);
837 } else if (isa<InvokeInst>(TI)) {
838 if (Personality == EHPersonality::MSVC_CXX && CleanupPad) {
839 // Invokes within a cleanuppad for the MSVC++ personality never
840 // transfer control to their unwind edge: the personality will
841 // terminate the program.
842 removeUnwindEdge(BB);
849 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
850 // Clean-up some of the mess we made by removing useles PHI nodes, trivial
852 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
853 BasicBlock *BB = &*FI++;
854 SimplifyInstructionsInBlock(BB);
855 ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
856 MergeBlockIntoPredecessor(BB);
859 // We might have some unreachable blocks after cleaning up some impossible
861 removeUnreachableBlocks(F);
864 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
865 // Recolor the CFG to verify that all is well.
866 for (BasicBlock &BB : F) {
867 size_t NumColors = BlockColors[&BB].size();
868 assert(NumColors == 1 && "Expected monochromatic BB!");
870 report_fatal_error("Uncolored BB!");
872 report_fatal_error("Multicolor BB!");
873 if (!DisableDemotion) {
874 bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
875 assert(!EHPadHasPHI && "EH Pad still has a PHI!");
877 report_fatal_error("EH Pad still has a PHI!");
882 bool WinEHPrepare::prepareExplicitEH(Function &F) {
883 // Remove unreachable blocks. It is not valuable to assign them a color and
884 // their existence can trick us into thinking values are alive when they are
886 removeUnreachableBlocks(F);
888 // Determine which blocks are reachable from which funclet entries.
891 cloneCommonBlocks(F);
893 if (!DisableDemotion)
894 demotePHIsOnFunclets(F);
896 if (!DisableCleanups) {
897 removeImplausibleInstructions(F);
899 cleanupPreparedFunclets(F);
902 verifyPreparedFunclets(F);
905 FuncletBlocks.clear();
910 // TODO: Share loads when one use dominates another, or when a catchpad exit
911 // dominates uses (needs dominators).
912 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
913 BasicBlock *PHIBlock = PN->getParent();
914 AllocaInst *SpillSlot = nullptr;
915 Instruction *EHPad = PHIBlock->getFirstNonPHI();
917 if (!isa<TerminatorInst>(EHPad)) {
918 // If the EHPad isn't a terminator, then we can insert a load in this block
919 // that will dominate all uses.
920 SpillSlot = new AllocaInst(PN->getType(), nullptr,
921 Twine(PN->getName(), ".wineh.spillslot"),
922 &F.getEntryBlock().front());
923 Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
924 &*PHIBlock->getFirstInsertionPt());
925 PN->replaceAllUsesWith(V);
929 // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
930 // loads of the slot before every use.
931 DenseMap<BasicBlock *, Value *> Loads;
932 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
935 auto *UsingInst = cast<Instruction>(U.getUser());
936 if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
937 // Use is on an EH pad phi. Leave it alone; we'll insert loads and
938 // stores for it separately.
941 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
946 // TODO: improve store placement. Inserting at def is probably good, but need
947 // to be careful not to introduce interfering stores (needs liveness analysis).
948 // TODO: identify related phi nodes that can share spill slots, and share them
949 // (also needs liveness).
950 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
951 AllocaInst *SpillSlot) {
952 // Use a worklist of (Block, Value) pairs -- the given Value needs to be
953 // stored to the spill slot by the end of the given Block.
954 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
956 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
958 while (!Worklist.empty()) {
961 std::tie(EHBlock, InVal) = Worklist.pop_back_val();
963 PHINode *PN = dyn_cast<PHINode>(InVal);
964 if (PN && PN->getParent() == EHBlock) {
965 // The value is defined by another PHI we need to remove, with no room to
966 // insert a store after the PHI, so each predecessor needs to store its
968 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
969 Value *PredVal = PN->getIncomingValue(i);
971 // Undef can safely be skipped.
972 if (isa<UndefValue>(PredVal))
975 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
978 // We need to store InVal, which dominates EHBlock, but can't put a store
979 // in EHBlock, so need to put stores in each predecessor.
980 for (BasicBlock *PredBlock : predecessors(EHBlock)) {
981 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
987 void WinEHPrepare::insertPHIStore(
988 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
989 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
991 if (PredBlock->isEHPad() &&
992 isa<TerminatorInst>(PredBlock->getFirstNonPHI())) {
993 // Pred is unsplittable, so we need to queue it on the worklist.
994 Worklist.push_back({PredBlock, PredVal});
998 // Otherwise, insert the store at the end of the basic block.
999 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1002 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1003 DenseMap<BasicBlock *, Value *> &Loads,
1005 // Lazilly create the spill slot.
1007 SpillSlot = new AllocaInst(V->getType(), nullptr,
1008 Twine(V->getName(), ".wineh.spillslot"),
1009 &F.getEntryBlock().front());
1011 auto *UsingInst = cast<Instruction>(U.getUser());
1012 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1013 // If this is a PHI node, we can't insert a load of the value before
1014 // the use. Instead insert the load in the predecessor block
1015 // corresponding to the incoming value.
1017 // Note that if there are multiple edges from a basic block to this
1018 // PHI node that we cannot have multiple loads. The problem is that
1019 // the resulting PHI node will have multiple values (from each load)
1020 // coming in from the same block, which is illegal SSA form.
1021 // For this reason, we keep track of and reuse loads we insert.
1022 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1023 if (auto *CatchRet =
1024 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1025 // Putting a load above a catchret and use on the phi would still leave
1026 // a cross-funclet def/use. We need to split the edge, change the
1027 // catchret to target the new block, and put the load there.
1028 BasicBlock *PHIBlock = UsingInst->getParent();
1029 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1030 // SplitEdge gives us:
1033 // br label %NewBlock
1035 // catchret label %PHIBlock
1039 // catchret label %NewBlock
1041 // br label %PHIBlock
1042 // So move the terminators to each others' blocks and swap their
1044 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1045 Goto->removeFromParent();
1046 CatchRet->removeFromParent();
1047 IncomingBlock->getInstList().push_back(CatchRet);
1048 NewBlock->getInstList().push_back(Goto);
1049 Goto->setSuccessor(0, PHIBlock);
1050 CatchRet->setSuccessor(NewBlock);
1051 // Update the color mapping for the newly split edge.
1052 ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1053 BlockColors[NewBlock] = ColorsForPHIBlock;
1054 for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1055 FuncletBlocks[FuncletPad].push_back(NewBlock);
1056 // Treat the new block as incoming for load insertion.
1057 IncomingBlock = NewBlock;
1059 Value *&Load = Loads[IncomingBlock];
1060 // Insert the load into the predecessor block
1062 Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1063 /*Volatile=*/false, IncomingBlock->getTerminator());
1067 // Reload right before the old use.
1068 auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1069 /*Volatile=*/false, UsingInst);
1074 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1075 MCSymbol *InvokeBegin,
1076 MCSymbol *InvokeEnd) {
1077 assert(InvokeStateMap.count(II) &&
1078 "should get invoke with precomputed state");
1079 LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);