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 replaceTerminatePadWithCleanup(Function &F);
74 void colorFunclets(Function &F);
76 void demotePHIsOnFunclets(Function &F);
77 void cloneCommonBlocks(Function &F);
78 void removeImplausibleTerminators(Function &F);
79 void cleanupPreparedFunclets(Function &F);
80 void verifyPreparedFunclets(Function &F);
82 // All fields are reset by runOnFunction.
83 EHPersonality Personality = EHPersonality::Unknown;
85 DenseMap<BasicBlock *, ColorVector> BlockColors;
86 MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
89 } // end anonymous namespace
91 char WinEHPrepare::ID = 0;
92 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
95 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
96 return new WinEHPrepare(TM);
99 bool WinEHPrepare::runOnFunction(Function &Fn) {
100 if (!Fn.hasPersonalityFn())
103 // Classify the personality to see what kind of preparation we need.
104 Personality = classifyEHPersonality(Fn.getPersonalityFn());
106 // Do nothing if this is not a funclet-based personality.
107 if (!isFuncletEHPersonality(Personality))
110 return prepareExplicitEH(Fn);
113 bool WinEHPrepare::doFinalization(Module &M) { return false; }
115 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
117 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
118 const BasicBlock *BB) {
119 CxxUnwindMapEntry UME;
120 UME.ToState = ToState;
122 FuncInfo.CxxUnwindMap.push_back(UME);
123 return FuncInfo.getLastStateNumber();
126 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
127 int TryHigh, int CatchHigh,
128 ArrayRef<const CatchPadInst *> Handlers) {
129 WinEHTryBlockMapEntry TBME;
130 TBME.TryLow = TryLow;
131 TBME.TryHigh = TryHigh;
132 TBME.CatchHigh = CatchHigh;
133 assert(TBME.TryLow <= TBME.TryHigh);
134 for (const CatchPadInst *CPI : Handlers) {
136 Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
137 if (TypeInfo->isNullValue())
138 HT.TypeDescriptor = nullptr;
140 HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
141 HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
142 HT.Handler = CPI->getParent();
143 if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
144 HT.CatchObj.Alloca = nullptr;
146 HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
147 TBME.HandlerArray.push_back(HT);
149 FuncInfo.TryBlockMap.push_back(TBME);
152 static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
153 for (const User *U : CleanupPad->users())
154 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
155 return CRI->getUnwindDest();
159 static void calculateStateNumbersForInvokes(const Function *Fn,
160 WinEHFuncInfo &FuncInfo) {
161 auto *F = const_cast<Function *>(Fn);
162 DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
163 for (BasicBlock &BB : *F) {
164 auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
168 auto &BBColors = BlockColors[&BB];
169 assert(BBColors.size() == 1 &&
170 "multi-color BB not removed by preparation");
171 BasicBlock *FuncletEntryBB = BBColors.front();
173 BasicBlock *FuncletUnwindDest;
175 dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
176 assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
178 FuncletUnwindDest = nullptr;
179 else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
180 FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
181 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
182 FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
184 llvm_unreachable("unexpected funclet pad!");
186 BasicBlock *InvokeUnwindDest = II->getUnwindDest();
188 if (FuncletUnwindDest == InvokeUnwindDest) {
189 auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
190 if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
191 BaseState = BaseStateI->second;
194 if (BaseState != -1) {
195 FuncInfo.InvokeStateMap[II] = BaseState;
197 Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
198 assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
199 FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
204 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
205 // to. If the unwind edge came from an invoke, return null.
206 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
208 const TerminatorInst *TI = BB->getTerminator();
209 if (isa<InvokeInst>(TI))
211 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
212 if (CatchSwitch->getParentPad() != ParentPad)
216 assert(!TI->isEHPad() && "unexpected EHPad!");
217 auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
218 if (CleanupPad->getParentPad() != ParentPad)
220 return CleanupPad->getParent();
223 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
224 const Instruction *FirstNonPHI,
226 const BasicBlock *BB = FirstNonPHI->getParent();
227 assert(BB->isEHPad() && "not a funclet!");
229 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
230 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
231 "shouldn't revist catch funclets!");
233 SmallVector<const CatchPadInst *, 2> Handlers;
234 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
235 auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
236 Handlers.push_back(CatchPad);
238 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
239 FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
240 for (const BasicBlock *PredBlock : predecessors(BB))
241 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
242 CatchSwitch->getParentPad())))
243 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
245 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
247 // catchpads are separate funclets in C++ EH due to the way rethrow works.
248 int TryHigh = CatchLow - 1;
249 for (const auto *CatchPad : Handlers) {
250 FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
251 for (const User *U : CatchPad->users()) {
252 const auto *UserI = cast<Instruction>(U);
253 if (UserI->isEHPad())
254 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
257 int CatchHigh = FuncInfo.getLastStateNumber();
258 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
259 DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
260 DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh << '\n');
261 DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
264 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
266 // It's possible for a cleanup to be visited twice: it might have multiple
267 // cleanupret instructions.
268 if (FuncInfo.EHPadStateMap.count(CleanupPad))
271 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
272 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
273 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
274 << BB->getName() << '\n');
275 for (const BasicBlock *PredBlock : predecessors(BB)) {
276 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
277 CleanupPad->getParentPad()))) {
278 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
282 for (const User *U : CleanupPad->users()) {
283 const auto *UserI = cast<Instruction>(U);
284 if (UserI->isEHPad())
285 report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
286 "contain exceptional actions");
291 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
292 const Function *Filter, const BasicBlock *Handler) {
293 SEHUnwindMapEntry Entry;
294 Entry.ToState = ParentState;
295 Entry.IsFinally = false;
296 Entry.Filter = Filter;
297 Entry.Handler = Handler;
298 FuncInfo.SEHUnwindMap.push_back(Entry);
299 return FuncInfo.SEHUnwindMap.size() - 1;
302 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
303 const BasicBlock *Handler) {
304 SEHUnwindMapEntry Entry;
305 Entry.ToState = ParentState;
306 Entry.IsFinally = true;
307 Entry.Filter = nullptr;
308 Entry.Handler = Handler;
309 FuncInfo.SEHUnwindMap.push_back(Entry);
310 return FuncInfo.SEHUnwindMap.size() - 1;
313 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
314 const Instruction *FirstNonPHI,
316 const BasicBlock *BB = FirstNonPHI->getParent();
317 assert(BB->isEHPad() && "no a funclet!");
319 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
320 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
321 "shouldn't revist catch funclets!");
323 // Extract the filter function and the __except basic block and create a
325 assert(CatchSwitch->getNumHandlers() == 1 &&
326 "SEH doesn't have multiple handlers per __try");
327 const auto *CatchPad =
328 cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
329 const BasicBlock *CatchPadBB = CatchPad->getParent();
330 const Constant *FilterOrNull =
331 cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
332 const Function *Filter = dyn_cast<Function>(FilterOrNull);
333 assert((Filter || FilterOrNull->isNullValue()) &&
334 "unexpected filter value");
335 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
337 // Everything in the __try block uses TryState as its parent state.
338 FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
339 DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
340 << CatchPadBB->getName() << '\n');
341 for (const BasicBlock *PredBlock : predecessors(BB))
342 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
343 CatchSwitch->getParentPad())))
344 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
347 // Everything in the __except block unwinds to ParentState, just like code
348 // outside the __try.
349 for (const User *U : CatchPad->users()) {
350 const auto *UserI = cast<Instruction>(U);
351 if (UserI->isEHPad()) {
352 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
356 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
358 // It's possible for a cleanup to be visited twice: it might have multiple
359 // cleanupret instructions.
360 if (FuncInfo.EHPadStateMap.count(CleanupPad))
363 int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
364 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
365 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
366 << BB->getName() << '\n');
367 for (const BasicBlock *PredBlock : predecessors(BB))
369 getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
370 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
372 for (const User *U : CleanupPad->users()) {
373 const auto *UserI = cast<Instruction>(U);
374 if (UserI->isEHPad())
375 report_fatal_error("Cleanup funclets for the SEH personality cannot "
376 "contain exceptional actions");
381 static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
382 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
383 return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
384 CatchSwitch->unwindsToCaller();
385 if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
386 return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
387 getCleanupRetUnwindDest(CleanupPad) == nullptr;
388 if (isa<CatchPadInst>(EHPad))
390 llvm_unreachable("unexpected EHPad!");
393 void llvm::calculateSEHStateNumbers(const Function *Fn,
394 WinEHFuncInfo &FuncInfo) {
395 // Don't compute state numbers twice.
396 if (!FuncInfo.SEHUnwindMap.empty())
399 for (const BasicBlock &BB : *Fn) {
402 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
403 if (!isTopLevelPadForMSVC(FirstNonPHI))
405 ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
408 calculateStateNumbersForInvokes(Fn, FuncInfo);
411 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
412 WinEHFuncInfo &FuncInfo) {
413 // Return if it's already been done.
414 if (!FuncInfo.EHPadStateMap.empty())
417 for (const BasicBlock &BB : *Fn) {
420 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
421 if (!isTopLevelPadForMSVC(FirstNonPHI))
423 calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
426 calculateStateNumbersForInvokes(Fn, FuncInfo);
429 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
430 ClrHandlerType HandlerType, uint32_t TypeToken,
431 const BasicBlock *Handler) {
432 ClrEHUnwindMapEntry Entry;
433 Entry.Parent = ParentState;
434 Entry.Handler = Handler;
435 Entry.HandlerType = HandlerType;
436 Entry.TypeToken = TypeToken;
437 FuncInfo.ClrEHUnwindMap.push_back(Entry);
438 return FuncInfo.ClrEHUnwindMap.size() - 1;
441 void llvm::calculateClrEHStateNumbers(const Function *Fn,
442 WinEHFuncInfo &FuncInfo) {
443 // Return if it's already been done.
444 if (!FuncInfo.EHPadStateMap.empty())
447 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
449 // Each pad needs to be able to refer to its parent, so scan the function
450 // looking for top-level handlers and seed the worklist with them.
451 for (const BasicBlock &BB : *Fn) {
454 if (BB.isLandingPad())
455 report_fatal_error("CoreCLR EH cannot use landingpads");
456 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
457 if (!isTopLevelPadForMSVC(FirstNonPHI))
459 // queue this with sentinel parent state -1 to mean unwind to caller.
460 Worklist.emplace_back(FirstNonPHI, -1);
463 while (!Worklist.empty()) {
464 const Instruction *Pad;
466 std::tie(Pad, ParentState) = Worklist.pop_back_val();
470 if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
471 // A cleanup can have multiple exits; don't re-process after the first.
472 if (FuncInfo.EHPadStateMap.count(Cleanup))
474 // CoreCLR personality uses arity to distinguish faults from finallies.
475 const BasicBlock *PadBlock = Cleanup->getParent();
476 ClrHandlerType HandlerType =
477 (Cleanup->getNumOperands() ? ClrHandlerType::Fault
478 : ClrHandlerType::Finally);
480 addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
481 FuncInfo.EHPadStateMap[Cleanup] = NewState;
482 // Propagate the new state to all preds of the cleanup
483 ParentPad = Cleanup->getParentPad();
484 PredState = NewState;
485 } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
486 SmallVector<const CatchPadInst *, 1> Handlers;
487 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
488 const auto *Catch = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
489 Handlers.push_back(Catch);
491 FuncInfo.EHPadStateMap[CatchSwitch] = ParentState;
492 int NewState = ParentState;
493 for (auto HandlerI = Handlers.rbegin(), HandlerE = Handlers.rend();
494 HandlerI != HandlerE; ++HandlerI) {
495 const CatchPadInst *Catch = *HandlerI;
496 const BasicBlock *PadBlock = Catch->getParent();
497 uint32_t TypeToken = static_cast<uint32_t>(
498 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
499 NewState = addClrEHHandler(FuncInfo, NewState, ClrHandlerType::Catch,
500 TypeToken, PadBlock);
501 FuncInfo.EHPadStateMap[Catch] = NewState;
503 for (const auto *CatchPad : Handlers) {
504 for (const User *U : CatchPad->users()) {
505 const auto *UserI = cast<Instruction>(U);
506 if (UserI->isEHPad())
507 Worklist.emplace_back(UserI, ParentState);
510 PredState = NewState;
511 ParentPad = CatchSwitch->getParentPad();
513 llvm_unreachable("Unexpected EH pad");
516 // Queue all predecessors with the given state
517 for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
518 if ((Pred = getEHPadFromPredecessor(Pred, ParentPad)))
519 Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
523 calculateStateNumbersForInvokes(Fn, FuncInfo);
526 void WinEHPrepare::replaceTerminatePadWithCleanup(Function &F) {
527 if (Personality != EHPersonality::MSVC_CXX)
529 for (BasicBlock &BB : F) {
530 Instruction *First = BB.getFirstNonPHI();
531 auto *TPI = dyn_cast<TerminatePadInst>(First);
535 if (TPI->getNumArgOperands() != 1)
537 "Expected a unary terminatepad for MSVC C++ personalities!");
539 auto *TerminateFn = dyn_cast<Function>(TPI->getArgOperand(0));
541 report_fatal_error("Function operand expected in terminatepad for MSVC "
542 "C++ personalities!");
544 // Insert the cleanuppad instruction.
546 CleanupPadInst::Create(TPI->getParentPad(), {},
547 Twine("terminatepad.for.", BB.getName()), &BB);
549 // Insert the call to the terminate instruction.
550 auto *CallTerminate = CallInst::Create(TerminateFn, {}, &BB);
551 CallTerminate->setDoesNotThrow();
552 CallTerminate->setDoesNotReturn();
553 CallTerminate->setCallingConv(TerminateFn->getCallingConv());
555 // Insert a new terminator for the cleanuppad using the same successor as
557 CleanupReturnInst::Create(CPI, TPI->getUnwindDest(), &BB);
559 // Let's remove the terminatepad now that we've inserted the new
561 TPI->eraseFromParent();
565 void WinEHPrepare::colorFunclets(Function &F) {
566 BlockColors = colorEHFunclets(F);
568 // Invert the map from BB to colors to color to BBs.
569 for (BasicBlock &BB : F) {
570 ColorVector &Colors = BlockColors[&BB];
571 for (BasicBlock *Color : Colors)
572 FuncletBlocks[Color].push_back(&BB);
576 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
577 WinEHFuncInfo &FuncInfo) {
578 for (const BasicBlock &BB : *Fn) {
579 const auto *CatchRet = dyn_cast<CatchReturnInst>(BB.getTerminator());
582 // A 'catchret' returns to the outer scope's color.
583 Value *ParentPad = CatchRet->getParentPad();
584 const BasicBlock *Color;
585 if (isa<ConstantTokenNone>(ParentPad))
586 Color = &Fn->getEntryBlock();
588 Color = cast<Instruction>(ParentPad)->getParent();
589 // Record the catchret successor's funclet membership.
590 FuncInfo.CatchRetSuccessorColorMap[CatchRet] = Color;
594 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
595 // Strip PHI nodes off of EH pads.
596 SmallVector<PHINode *, 16> PHINodes;
597 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
598 BasicBlock *BB = &*FI++;
601 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
602 Instruction *I = &*BI++;
603 auto *PN = dyn_cast<PHINode>(I);
604 // Stop at the first non-PHI.
608 AllocaInst *SpillSlot = insertPHILoads(PN, F);
610 insertPHIStores(PN, SpillSlot);
612 PHINodes.push_back(PN);
616 for (auto *PN : PHINodes) {
617 // There may be lingering uses on other EH PHIs being removed
618 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
619 PN->eraseFromParent();
623 void WinEHPrepare::cloneCommonBlocks(Function &F) {
624 // We need to clone all blocks which belong to multiple funclets. Values are
625 // remapped throughout the funclet to propogate both the new instructions
626 // *and* the new basic blocks themselves.
627 for (auto &Funclets : FuncletBlocks) {
628 BasicBlock *FuncletPadBB = Funclets.first;
629 std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
631 std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
632 ValueToValueMapTy VMap;
633 for (BasicBlock *BB : BlocksInFunclet) {
634 ColorVector &ColorsForBB = BlockColors[BB];
635 // We don't need to do anything if the block is monochromatic.
636 size_t NumColorsForBB = ColorsForBB.size();
637 if (NumColorsForBB == 1)
640 DEBUG_WITH_TYPE("winehprepare-coloring",
641 dbgs() << " Cloning block \'" << BB->getName()
642 << "\' for funclet \'" << FuncletPadBB->getName()
645 // Create a new basic block and copy instructions into it!
647 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
648 // Insert the clone immediately after the original to ensure determinism
649 // and to keep the same relative ordering of any funclet's blocks.
650 CBB->insertInto(&F, BB->getNextNode());
652 // Add basic block mapping.
655 // Record delta operations that we need to perform to our color mappings.
656 Orig2Clone.emplace_back(BB, CBB);
659 // If nothing was cloned, we're done cloning in this funclet.
660 if (Orig2Clone.empty())
663 // Update our color mappings to reflect that one block has lost a color and
664 // another has gained a color.
665 for (auto &BBMapping : Orig2Clone) {
666 BasicBlock *OldBlock = BBMapping.first;
667 BasicBlock *NewBlock = BBMapping.second;
669 BlocksInFunclet.push_back(NewBlock);
670 ColorVector &NewColors = BlockColors[NewBlock];
671 assert(NewColors.empty() && "A new block should only have one color!");
672 NewColors.push_back(FuncletPadBB);
674 DEBUG_WITH_TYPE("winehprepare-coloring",
675 dbgs() << " Assigned color \'" << FuncletPadBB->getName()
676 << "\' to block \'" << NewBlock->getName()
679 BlocksInFunclet.erase(
680 std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
681 BlocksInFunclet.end());
682 ColorVector &OldColors = BlockColors[OldBlock];
684 std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
687 DEBUG_WITH_TYPE("winehprepare-coloring",
688 dbgs() << " Removed color \'" << FuncletPadBB->getName()
689 << "\' from block \'" << OldBlock->getName()
693 // Loop over all of the instructions in this funclet, fixing up operand
694 // references as we go. This uses VMap to do all the hard work.
695 for (BasicBlock *BB : BlocksInFunclet)
696 // Loop over all instructions, fixing each one as we find it...
697 for (Instruction &I : *BB)
698 RemapInstruction(&I, VMap,
699 RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
701 auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
702 unsigned NumPreds = PN->getNumIncomingValues();
703 for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
705 BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
706 ColorVector &IncomingColors = BlockColors[IncomingBlock];
707 bool BlockInFunclet = IncomingColors.size() == 1 &&
708 IncomingColors.front() == FuncletPadBB;
709 if (IsForOldBlock != BlockInFunclet)
711 PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
712 // Revisit the next entry.
718 for (auto &BBMapping : Orig2Clone) {
719 BasicBlock *OldBlock = BBMapping.first;
720 BasicBlock *NewBlock = BBMapping.second;
721 for (Instruction &OldI : *OldBlock) {
722 auto *OldPN = dyn_cast<PHINode>(&OldI);
725 UpdatePHIOnClonedBlock(OldPN, /*IsForOldBlock=*/true);
727 for (Instruction &NewI : *NewBlock) {
728 auto *NewPN = dyn_cast<PHINode>(&NewI);
731 UpdatePHIOnClonedBlock(NewPN, /*IsForOldBlock=*/false);
735 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
736 // the PHI nodes for NewBB now.
737 for (auto &BBMapping : Orig2Clone) {
738 BasicBlock *OldBlock = BBMapping.first;
739 BasicBlock *NewBlock = BBMapping.second;
740 for (BasicBlock *SuccBB : successors(NewBlock)) {
741 for (Instruction &SuccI : *SuccBB) {
742 auto *SuccPN = dyn_cast<PHINode>(&SuccI);
746 // Ok, we have a PHI node. Figure out what the incoming value was for
748 int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
749 if (OldBlockIdx == -1)
751 Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
753 // Remap the value if necessary.
754 if (auto *Inst = dyn_cast<Instruction>(IV)) {
755 ValueToValueMapTy::iterator I = VMap.find(Inst);
760 SuccPN->addIncoming(IV, NewBlock);
765 for (ValueToValueMapTy::value_type VT : VMap) {
766 // If there were values defined in BB that are used outside the funclet,
767 // then we now have to update all uses of the value to use either the
768 // original value, the cloned value, or some PHI derived value. This can
769 // require arbitrary PHI insertion, of which we are prepared to do, clean
771 SmallVector<Use *, 16> UsesToRename;
773 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
776 auto *NewI = cast<Instruction>(VT.second);
777 // Scan all uses of this instruction to see if it is used outside of its
778 // funclet, and if so, record them in UsesToRename.
779 for (Use &U : OldI->uses()) {
780 Instruction *UserI = cast<Instruction>(U.getUser());
781 BasicBlock *UserBB = UserI->getParent();
782 ColorVector &ColorsForUserBB = BlockColors[UserBB];
783 assert(!ColorsForUserBB.empty());
784 if (ColorsForUserBB.size() > 1 ||
785 *ColorsForUserBB.begin() != FuncletPadBB)
786 UsesToRename.push_back(&U);
789 // If there are no uses outside the block, we're done with this
791 if (UsesToRename.empty())
794 // We found a use of OldI outside of the funclet. Rename all uses of OldI
795 // that are outside its funclet to be uses of the appropriate PHI node
797 SSAUpdater SSAUpdate;
798 SSAUpdate.Initialize(OldI->getType(), OldI->getName());
799 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
800 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
802 while (!UsesToRename.empty())
803 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
808 void WinEHPrepare::removeImplausibleTerminators(Function &F) {
809 // Remove implausible terminators and replace them with UnreachableInst.
810 for (auto &Funclet : FuncletBlocks) {
811 BasicBlock *FuncletPadBB = Funclet.first;
812 std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
813 Instruction *FuncletPadInst = FuncletPadBB->getFirstNonPHI();
814 auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPadInst);
815 auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPadInst);
817 for (BasicBlock *BB : BlocksInFunclet) {
818 TerminatorInst *TI = BB->getTerminator();
819 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
820 bool IsUnreachableRet = isa<ReturnInst>(TI) && (CatchPad || CleanupPad);
821 // The token consumed by a CatchReturnInst must match the funclet token.
822 bool IsUnreachableCatchret = false;
823 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
824 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
825 // The token consumed by a CleanupReturnInst must match the funclet token.
826 bool IsUnreachableCleanupret = false;
827 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
828 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
829 if (IsUnreachableRet || IsUnreachableCatchret ||
830 IsUnreachableCleanupret) {
831 // Loop through all of our successors and make sure they know that one
832 // of their predecessors is going away.
833 for (BasicBlock *SuccBB : TI->successors())
834 SuccBB->removePredecessor(BB);
836 new UnreachableInst(BB->getContext(), TI);
837 TI->eraseFromParent();
838 } else if (isa<InvokeInst>(TI)) {
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 if (Personality == EHPersonality::MSVC_CXX && CleanupPad)
843 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 replaceTerminatePadWithCleanup(F);
890 // Determine which blocks are reachable from which funclet entries.
893 cloneCommonBlocks(F);
895 if (!DisableDemotion)
896 demotePHIsOnFunclets(F);
898 if (!DisableCleanups) {
899 removeImplausibleTerminators(F);
901 cleanupPreparedFunclets(F);
904 verifyPreparedFunclets(F);
907 FuncletBlocks.clear();
912 // TODO: Share loads when one use dominates another, or when a catchpad exit
913 // dominates uses (needs dominators).
914 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
915 BasicBlock *PHIBlock = PN->getParent();
916 AllocaInst *SpillSlot = nullptr;
917 Instruction *EHPad = PHIBlock->getFirstNonPHI();
919 if (!isa<TerminatorInst>(EHPad)) {
920 // If the EHPad isn't a terminator, then we can insert a load in this block
921 // that will dominate all uses.
922 SpillSlot = new AllocaInst(PN->getType(), nullptr,
923 Twine(PN->getName(), ".wineh.spillslot"),
924 &F.getEntryBlock().front());
925 Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
926 &*PHIBlock->getFirstInsertionPt());
927 PN->replaceAllUsesWith(V);
931 // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
932 // loads of the slot before every use.
933 DenseMap<BasicBlock *, Value *> Loads;
934 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
937 auto *UsingInst = cast<Instruction>(U.getUser());
938 if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
939 // Use is on an EH pad phi. Leave it alone; we'll insert loads and
940 // stores for it separately.
943 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
948 // TODO: improve store placement. Inserting at def is probably good, but need
949 // to be careful not to introduce interfering stores (needs liveness analysis).
950 // TODO: identify related phi nodes that can share spill slots, and share them
951 // (also needs liveness).
952 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
953 AllocaInst *SpillSlot) {
954 // Use a worklist of (Block, Value) pairs -- the given Value needs to be
955 // stored to the spill slot by the end of the given Block.
956 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
958 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
960 while (!Worklist.empty()) {
963 std::tie(EHBlock, InVal) = Worklist.pop_back_val();
965 PHINode *PN = dyn_cast<PHINode>(InVal);
966 if (PN && PN->getParent() == EHBlock) {
967 // The value is defined by another PHI we need to remove, with no room to
968 // insert a store after the PHI, so each predecessor needs to store its
970 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
971 Value *PredVal = PN->getIncomingValue(i);
973 // Undef can safely be skipped.
974 if (isa<UndefValue>(PredVal))
977 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
980 // We need to store InVal, which dominates EHBlock, but can't put a store
981 // in EHBlock, so need to put stores in each predecessor.
982 for (BasicBlock *PredBlock : predecessors(EHBlock)) {
983 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
989 void WinEHPrepare::insertPHIStore(
990 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
991 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
993 if (PredBlock->isEHPad() &&
994 isa<TerminatorInst>(PredBlock->getFirstNonPHI())) {
995 // Pred is unsplittable, so we need to queue it on the worklist.
996 Worklist.push_back({PredBlock, PredVal});
1000 // Otherwise, insert the store at the end of the basic block.
1001 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1004 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1005 DenseMap<BasicBlock *, Value *> &Loads,
1007 // Lazilly create the spill slot.
1009 SpillSlot = new AllocaInst(V->getType(), nullptr,
1010 Twine(V->getName(), ".wineh.spillslot"),
1011 &F.getEntryBlock().front());
1013 auto *UsingInst = cast<Instruction>(U.getUser());
1014 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1015 // If this is a PHI node, we can't insert a load of the value before
1016 // the use. Instead insert the load in the predecessor block
1017 // corresponding to the incoming value.
1019 // Note that if there are multiple edges from a basic block to this
1020 // PHI node that we cannot have multiple loads. The problem is that
1021 // the resulting PHI node will have multiple values (from each load)
1022 // coming in from the same block, which is illegal SSA form.
1023 // For this reason, we keep track of and reuse loads we insert.
1024 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1025 if (auto *CatchRet =
1026 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1027 // Putting a load above a catchret and use on the phi would still leave
1028 // a cross-funclet def/use. We need to split the edge, change the
1029 // catchret to target the new block, and put the load there.
1030 BasicBlock *PHIBlock = UsingInst->getParent();
1031 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1032 // SplitEdge gives us:
1035 // br label %NewBlock
1037 // catchret label %PHIBlock
1041 // catchret label %NewBlock
1043 // br label %PHIBlock
1044 // So move the terminators to each others' blocks and swap their
1046 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1047 Goto->removeFromParent();
1048 CatchRet->removeFromParent();
1049 IncomingBlock->getInstList().push_back(CatchRet);
1050 NewBlock->getInstList().push_back(Goto);
1051 Goto->setSuccessor(0, PHIBlock);
1052 CatchRet->setSuccessor(NewBlock);
1053 // Update the color mapping for the newly split edge.
1054 ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1055 BlockColors[NewBlock] = ColorsForPHIBlock;
1056 for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1057 FuncletBlocks[FuncletPad].push_back(NewBlock);
1058 // Treat the new block as incoming for load insertion.
1059 IncomingBlock = NewBlock;
1061 Value *&Load = Loads[IncomingBlock];
1062 // Insert the load into the predecessor block
1064 Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1065 /*Volatile=*/false, IncomingBlock->getTerminator());
1069 // Reload right before the old use.
1070 auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1071 /*Volatile=*/false, UsingInst);
1076 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1077 MCSymbol *InvokeBegin,
1078 MCSymbol *InvokeEnd) {
1079 assert(InvokeStateMap.count(II) &&
1080 "should get invoke with precomputed state");
1081 LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);