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/MachineBasicBlock.h"
24 #include "llvm/CodeGen/WinEHFuncInfo.h"
25 #include "llvm/IR/Verifier.h"
26 #include "llvm/MC/MCSymbol.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
31 #include "llvm/Transforms/Utils/Cloning.h"
32 #include "llvm/Transforms/Utils/Local.h"
33 #include "llvm/Transforms/Utils/SSAUpdater.h"
37 #define DEBUG_TYPE "winehprepare"
39 static cl::opt<bool> DisableDemotion(
40 "disable-demotion", cl::Hidden,
42 "Clone multicolor basic blocks but do not demote cross funclet values"),
45 static cl::opt<bool> DisableCleanups(
46 "disable-cleanups", cl::Hidden,
47 cl::desc("Do not remove implausible terminators or other similar cleanups"),
52 class WinEHPrepare : public FunctionPass {
54 static char ID; // Pass identification, replacement for typeid.
55 WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
57 bool runOnFunction(Function &Fn) override;
59 bool doFinalization(Module &M) override;
61 void getAnalysisUsage(AnalysisUsage &AU) const override;
63 const char *getPassName() const override {
64 return "Windows exception handling preparation";
68 void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);
70 insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
71 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);
72 AllocaInst *insertPHILoads(PHINode *PN, Function &F);
73 void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
74 DenseMap<BasicBlock *, Value *> &Loads, Function &F);
75 bool prepareExplicitEH(Function &F);
76 void colorFunclets(Function &F);
78 void demotePHIsOnFunclets(Function &F);
79 void cloneCommonBlocks(Function &F);
80 void removeImplausibleInstructions(Function &F);
81 void cleanupPreparedFunclets(Function &F);
82 void verifyPreparedFunclets(Function &F);
84 // All fields are reset by runOnFunction.
85 EHPersonality Personality = EHPersonality::Unknown;
87 DenseMap<BasicBlock *, ColorVector> BlockColors;
88 MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;
91 } // end anonymous namespace
93 char WinEHPrepare::ID = 0;
94 INITIALIZE_TM_PASS(WinEHPrepare, "winehprepare", "Prepare Windows exceptions",
97 FunctionPass *llvm::createWinEHPass(const TargetMachine *TM) {
98 return new WinEHPrepare(TM);
101 bool WinEHPrepare::runOnFunction(Function &Fn) {
102 if (!Fn.hasPersonalityFn())
105 // Classify the personality to see what kind of preparation we need.
106 Personality = classifyEHPersonality(Fn.getPersonalityFn());
108 // Do nothing if this is not a funclet-based personality.
109 if (!isFuncletEHPersonality(Personality))
112 return prepareExplicitEH(Fn);
115 bool WinEHPrepare::doFinalization(Module &M) { return false; }
117 void WinEHPrepare::getAnalysisUsage(AnalysisUsage &AU) const {}
119 static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,
120 const BasicBlock *BB) {
121 CxxUnwindMapEntry UME;
122 UME.ToState = ToState;
124 FuncInfo.CxxUnwindMap.push_back(UME);
125 return FuncInfo.getLastStateNumber();
128 static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,
129 int TryHigh, int CatchHigh,
130 ArrayRef<const CatchPadInst *> Handlers) {
131 WinEHTryBlockMapEntry TBME;
132 TBME.TryLow = TryLow;
133 TBME.TryHigh = TryHigh;
134 TBME.CatchHigh = CatchHigh;
135 assert(TBME.TryLow <= TBME.TryHigh);
136 for (const CatchPadInst *CPI : Handlers) {
138 Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));
139 if (TypeInfo->isNullValue())
140 HT.TypeDescriptor = nullptr;
142 HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());
143 HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();
144 HT.Handler = CPI->getParent();
145 if (isa<ConstantPointerNull>(CPI->getArgOperand(2)))
146 HT.CatchObj.Alloca = nullptr;
148 HT.CatchObj.Alloca = cast<AllocaInst>(CPI->getArgOperand(2));
149 TBME.HandlerArray.push_back(HT);
151 FuncInfo.TryBlockMap.push_back(TBME);
154 static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {
155 for (const User *U : CleanupPad->users())
156 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))
157 return CRI->getUnwindDest();
161 static void calculateStateNumbersForInvokes(const Function *Fn,
162 WinEHFuncInfo &FuncInfo) {
163 auto *F = const_cast<Function *>(Fn);
164 DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);
165 for (BasicBlock &BB : *F) {
166 auto *II = dyn_cast<InvokeInst>(BB.getTerminator());
170 auto &BBColors = BlockColors[&BB];
171 assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");
172 BasicBlock *FuncletEntryBB = BBColors.front();
174 BasicBlock *FuncletUnwindDest;
176 dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
177 assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
179 FuncletUnwindDest = nullptr;
180 else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
181 FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
182 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
183 FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
185 llvm_unreachable("unexpected funclet pad!");
187 BasicBlock *InvokeUnwindDest = II->getUnwindDest();
189 if (FuncletUnwindDest == InvokeUnwindDest) {
190 auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
191 if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
192 BaseState = BaseStateI->second;
195 if (BaseState != -1) {
196 FuncInfo.InvokeStateMap[II] = BaseState;
198 Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
199 assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
200 FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
205 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
206 // to. If the unwind edge came from an invoke, return null.
207 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
209 const TerminatorInst *TI = BB->getTerminator();
210 if (isa<InvokeInst>(TI))
212 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
213 if (CatchSwitch->getParentPad() != ParentPad)
217 assert(!TI->isEHPad() && "unexpected EHPad!");
218 auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
219 if (CleanupPad->getParentPad() != ParentPad)
221 return CleanupPad->getParent();
224 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
225 const Instruction *FirstNonPHI,
227 const BasicBlock *BB = FirstNonPHI->getParent();
228 assert(BB->isEHPad() && "not a funclet!");
230 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
231 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
232 "shouldn't revist catch funclets!");
234 SmallVector<const CatchPadInst *, 2> Handlers;
235 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
236 auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
237 Handlers.push_back(CatchPad);
239 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
240 FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
241 for (const BasicBlock *PredBlock : predecessors(BB))
242 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
243 CatchSwitch->getParentPad())))
244 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
246 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
248 // catchpads are separate funclets in C++ EH due to the way rethrow works.
249 int TryHigh = CatchLow - 1;
250 for (const auto *CatchPad : Handlers) {
251 FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
252 for (const User *U : CatchPad->users()) {
253 const auto *UserI = cast<Instruction>(U);
254 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
255 if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
256 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
257 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
258 if (getCleanupRetUnwindDest(InnerCleanupPad) ==
259 CatchSwitch->getUnwindDest())
260 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
263 int CatchHigh = FuncInfo.getLastStateNumber();
264 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
265 DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
266 DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh << '\n');
267 DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
270 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
272 // It's possible for a cleanup to be visited twice: it might have multiple
273 // cleanupret instructions.
274 if (FuncInfo.EHPadStateMap.count(CleanupPad))
277 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
278 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
279 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
280 << BB->getName() << '\n');
281 for (const BasicBlock *PredBlock : predecessors(BB)) {
282 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
283 CleanupPad->getParentPad()))) {
284 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
288 for (const User *U : CleanupPad->users()) {
289 const auto *UserI = cast<Instruction>(U);
290 if (UserI->isEHPad())
291 report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
292 "contain exceptional actions");
297 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
298 const Function *Filter, const BasicBlock *Handler) {
299 SEHUnwindMapEntry Entry;
300 Entry.ToState = ParentState;
301 Entry.IsFinally = false;
302 Entry.Filter = Filter;
303 Entry.Handler = Handler;
304 FuncInfo.SEHUnwindMap.push_back(Entry);
305 return FuncInfo.SEHUnwindMap.size() - 1;
308 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
309 const BasicBlock *Handler) {
310 SEHUnwindMapEntry Entry;
311 Entry.ToState = ParentState;
312 Entry.IsFinally = true;
313 Entry.Filter = nullptr;
314 Entry.Handler = Handler;
315 FuncInfo.SEHUnwindMap.push_back(Entry);
316 return FuncInfo.SEHUnwindMap.size() - 1;
319 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
320 const Instruction *FirstNonPHI,
322 const BasicBlock *BB = FirstNonPHI->getParent();
323 assert(BB->isEHPad() && "no a funclet!");
325 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
326 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
327 "shouldn't revist catch funclets!");
329 // Extract the filter function and the __except basic block and create a
331 assert(CatchSwitch->getNumHandlers() == 1 &&
332 "SEH doesn't have multiple handlers per __try");
333 const auto *CatchPad =
334 cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
335 const BasicBlock *CatchPadBB = CatchPad->getParent();
336 const Constant *FilterOrNull =
337 cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
338 const Function *Filter = dyn_cast<Function>(FilterOrNull);
339 assert((Filter || FilterOrNull->isNullValue()) &&
340 "unexpected filter value");
341 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
343 // Everything in the __try block uses TryState as its parent state.
344 FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
345 DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
346 << CatchPadBB->getName() << '\n');
347 for (const BasicBlock *PredBlock : predecessors(BB))
348 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
349 CatchSwitch->getParentPad())))
350 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
353 // Everything in the __except block unwinds to ParentState, just like code
354 // outside the __try.
355 for (const User *U : CatchPad->users()) {
356 const auto *UserI = cast<Instruction>(U);
357 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI))
358 if (InnerCatchSwitch->getUnwindDest() == CatchSwitch->getUnwindDest())
359 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
360 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI))
361 if (getCleanupRetUnwindDest(InnerCleanupPad) ==
362 CatchSwitch->getUnwindDest())
363 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
366 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
368 // It's possible for a cleanup to be visited twice: it might have multiple
369 // cleanupret instructions.
370 if (FuncInfo.EHPadStateMap.count(CleanupPad))
373 int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
374 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
375 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
376 << BB->getName() << '\n');
377 for (const BasicBlock *PredBlock : predecessors(BB))
379 getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
380 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
382 for (const User *U : CleanupPad->users()) {
383 const auto *UserI = cast<Instruction>(U);
384 if (UserI->isEHPad())
385 report_fatal_error("Cleanup funclets for the SEH personality cannot "
386 "contain exceptional actions");
391 static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
392 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
393 return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
394 CatchSwitch->unwindsToCaller();
395 if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
396 return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
397 getCleanupRetUnwindDest(CleanupPad) == nullptr;
398 if (isa<CatchPadInst>(EHPad))
400 llvm_unreachable("unexpected EHPad!");
403 void llvm::calculateSEHStateNumbers(const Function *Fn,
404 WinEHFuncInfo &FuncInfo) {
405 // Don't compute state numbers twice.
406 if (!FuncInfo.SEHUnwindMap.empty())
409 for (const BasicBlock &BB : *Fn) {
412 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
413 if (!isTopLevelPadForMSVC(FirstNonPHI))
415 ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
418 calculateStateNumbersForInvokes(Fn, FuncInfo);
421 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
422 WinEHFuncInfo &FuncInfo) {
423 // Return if it's already been done.
424 if (!FuncInfo.EHPadStateMap.empty())
427 for (const BasicBlock &BB : *Fn) {
430 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
431 if (!isTopLevelPadForMSVC(FirstNonPHI))
433 calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
436 calculateStateNumbersForInvokes(Fn, FuncInfo);
439 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
440 ClrHandlerType HandlerType, uint32_t TypeToken,
441 const BasicBlock *Handler) {
442 ClrEHUnwindMapEntry Entry;
443 Entry.Parent = ParentState;
444 Entry.Handler = Handler;
445 Entry.HandlerType = HandlerType;
446 Entry.TypeToken = TypeToken;
447 FuncInfo.ClrEHUnwindMap.push_back(Entry);
448 return FuncInfo.ClrEHUnwindMap.size() - 1;
451 void llvm::calculateClrEHStateNumbers(const Function *Fn,
452 WinEHFuncInfo &FuncInfo) {
453 // Return if it's already been done.
454 if (!FuncInfo.EHPadStateMap.empty())
457 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
459 // Each pad needs to be able to refer to its parent, so scan the function
460 // looking for top-level handlers and seed the worklist with them.
461 for (const BasicBlock &BB : *Fn) {
464 if (BB.isLandingPad())
465 report_fatal_error("CoreCLR EH cannot use landingpads");
466 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
467 if (!isTopLevelPadForMSVC(FirstNonPHI))
469 // queue this with sentinel parent state -1 to mean unwind to caller.
470 Worklist.emplace_back(FirstNonPHI, -1);
473 while (!Worklist.empty()) {
474 const Instruction *Pad;
476 std::tie(Pad, ParentState) = Worklist.pop_back_val();
480 if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
481 // A cleanup can have multiple exits; don't re-process after the first.
482 if (FuncInfo.EHPadStateMap.count(Cleanup))
484 // CoreCLR personality uses arity to distinguish faults from finallies.
485 const BasicBlock *PadBlock = Cleanup->getParent();
486 ClrHandlerType HandlerType =
487 (Cleanup->getNumOperands() ? ClrHandlerType::Fault
488 : ClrHandlerType::Finally);
490 addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
491 FuncInfo.EHPadStateMap[Cleanup] = NewState;
492 // Propagate the new state to all preds of the cleanup
493 ParentPad = Cleanup->getParentPad();
494 PredState = NewState;
495 } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
496 SmallVector<const CatchPadInst *, 1> Handlers;
497 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
498 const auto *Catch = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
499 Handlers.push_back(Catch);
501 FuncInfo.EHPadStateMap[CatchSwitch] = ParentState;
502 int NewState = ParentState;
503 for (auto HandlerI = Handlers.rbegin(), HandlerE = Handlers.rend();
504 HandlerI != HandlerE; ++HandlerI) {
505 const CatchPadInst *Catch = *HandlerI;
506 const BasicBlock *PadBlock = Catch->getParent();
507 uint32_t TypeToken = static_cast<uint32_t>(
508 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
509 NewState = addClrEHHandler(FuncInfo, NewState, ClrHandlerType::Catch,
510 TypeToken, PadBlock);
511 FuncInfo.EHPadStateMap[Catch] = NewState;
513 for (const auto *CatchPad : Handlers) {
514 for (const User *U : CatchPad->users()) {
515 const auto *UserI = cast<Instruction>(U);
516 if (UserI->isEHPad())
517 Worklist.emplace_back(UserI, ParentState);
520 PredState = NewState;
521 ParentPad = CatchSwitch->getParentPad();
523 llvm_unreachable("Unexpected EH pad");
526 // Queue all predecessors with the given state
527 for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
528 if ((Pred = getEHPadFromPredecessor(Pred, ParentPad)))
529 Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
533 calculateStateNumbersForInvokes(Fn, FuncInfo);
536 void WinEHPrepare::colorFunclets(Function &F) {
537 BlockColors = colorEHFunclets(F);
539 // Invert the map from BB to colors to color to BBs.
540 for (BasicBlock &BB : F) {
541 ColorVector &Colors = BlockColors[&BB];
542 for (BasicBlock *Color : Colors)
543 FuncletBlocks[Color].push_back(&BB);
547 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
548 WinEHFuncInfo &FuncInfo) {
549 for (const BasicBlock &BB : *Fn) {
550 const auto *CatchRet = dyn_cast<CatchReturnInst>(BB.getTerminator());
553 // A 'catchret' returns to the outer scope's color.
554 Value *ParentPad = CatchRet->getParentPad();
555 const BasicBlock *Color;
556 if (isa<ConstantTokenNone>(ParentPad))
557 Color = &Fn->getEntryBlock();
559 Color = cast<Instruction>(ParentPad)->getParent();
560 // Record the catchret successor's funclet membership.
561 FuncInfo.CatchRetSuccessorColorMap[CatchRet] = Color;
565 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
566 // Strip PHI nodes off of EH pads.
567 SmallVector<PHINode *, 16> PHINodes;
568 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
569 BasicBlock *BB = &*FI++;
572 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
573 Instruction *I = &*BI++;
574 auto *PN = dyn_cast<PHINode>(I);
575 // Stop at the first non-PHI.
579 AllocaInst *SpillSlot = insertPHILoads(PN, F);
581 insertPHIStores(PN, SpillSlot);
583 PHINodes.push_back(PN);
587 for (auto *PN : PHINodes) {
588 // There may be lingering uses on other EH PHIs being removed
589 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
590 PN->eraseFromParent();
594 void WinEHPrepare::cloneCommonBlocks(Function &F) {
595 // We need to clone all blocks which belong to multiple funclets. Values are
596 // remapped throughout the funclet to propogate both the new instructions
597 // *and* the new basic blocks themselves.
598 for (auto &Funclets : FuncletBlocks) {
599 BasicBlock *FuncletPadBB = Funclets.first;
600 std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
602 std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
603 ValueToValueMapTy VMap;
604 for (BasicBlock *BB : BlocksInFunclet) {
605 ColorVector &ColorsForBB = BlockColors[BB];
606 // We don't need to do anything if the block is monochromatic.
607 size_t NumColorsForBB = ColorsForBB.size();
608 if (NumColorsForBB == 1)
611 DEBUG_WITH_TYPE("winehprepare-coloring",
612 dbgs() << " Cloning block \'" << BB->getName()
613 << "\' for funclet \'" << FuncletPadBB->getName()
616 // Create a new basic block and copy instructions into it!
618 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
619 // Insert the clone immediately after the original to ensure determinism
620 // and to keep the same relative ordering of any funclet's blocks.
621 CBB->insertInto(&F, BB->getNextNode());
623 // Add basic block mapping.
626 // Record delta operations that we need to perform to our color mappings.
627 Orig2Clone.emplace_back(BB, CBB);
630 // If nothing was cloned, we're done cloning in this funclet.
631 if (Orig2Clone.empty())
634 // Update our color mappings to reflect that one block has lost a color and
635 // another has gained a color.
636 for (auto &BBMapping : Orig2Clone) {
637 BasicBlock *OldBlock = BBMapping.first;
638 BasicBlock *NewBlock = BBMapping.second;
640 BlocksInFunclet.push_back(NewBlock);
641 ColorVector &NewColors = BlockColors[NewBlock];
642 assert(NewColors.empty() && "A new block should only have one color!");
643 NewColors.push_back(FuncletPadBB);
645 DEBUG_WITH_TYPE("winehprepare-coloring",
646 dbgs() << " Assigned color \'" << FuncletPadBB->getName()
647 << "\' to block \'" << NewBlock->getName()
650 BlocksInFunclet.erase(
651 std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
652 BlocksInFunclet.end());
653 ColorVector &OldColors = BlockColors[OldBlock];
655 std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
658 DEBUG_WITH_TYPE("winehprepare-coloring",
659 dbgs() << " Removed color \'" << FuncletPadBB->getName()
660 << "\' from block \'" << OldBlock->getName()
664 // Loop over all of the instructions in this funclet, fixing up operand
665 // references as we go. This uses VMap to do all the hard work.
666 for (BasicBlock *BB : BlocksInFunclet)
667 // Loop over all instructions, fixing each one as we find it...
668 for (Instruction &I : *BB)
669 RemapInstruction(&I, VMap,
670 RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
672 auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
673 unsigned NumPreds = PN->getNumIncomingValues();
674 for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
676 BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
677 ColorVector &IncomingColors = BlockColors[IncomingBlock];
678 bool BlockInFunclet = IncomingColors.size() == 1 &&
679 IncomingColors.front() == FuncletPadBB;
680 if (IsForOldBlock != BlockInFunclet)
682 PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
683 // Revisit the next entry.
689 for (auto &BBMapping : Orig2Clone) {
690 BasicBlock *OldBlock = BBMapping.first;
691 BasicBlock *NewBlock = BBMapping.second;
692 for (Instruction &OldI : *OldBlock) {
693 auto *OldPN = dyn_cast<PHINode>(&OldI);
696 UpdatePHIOnClonedBlock(OldPN, /*IsForOldBlock=*/true);
698 for (Instruction &NewI : *NewBlock) {
699 auto *NewPN = dyn_cast<PHINode>(&NewI);
702 UpdatePHIOnClonedBlock(NewPN, /*IsForOldBlock=*/false);
706 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
707 // the PHI nodes for NewBB now.
708 for (auto &BBMapping : Orig2Clone) {
709 BasicBlock *OldBlock = BBMapping.first;
710 BasicBlock *NewBlock = BBMapping.second;
711 for (BasicBlock *SuccBB : successors(NewBlock)) {
712 for (Instruction &SuccI : *SuccBB) {
713 auto *SuccPN = dyn_cast<PHINode>(&SuccI);
717 // Ok, we have a PHI node. Figure out what the incoming value was for
719 int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
720 if (OldBlockIdx == -1)
722 Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
724 // Remap the value if necessary.
725 if (auto *Inst = dyn_cast<Instruction>(IV)) {
726 ValueToValueMapTy::iterator I = VMap.find(Inst);
731 SuccPN->addIncoming(IV, NewBlock);
736 for (ValueToValueMapTy::value_type VT : VMap) {
737 // If there were values defined in BB that are used outside the funclet,
738 // then we now have to update all uses of the value to use either the
739 // original value, the cloned value, or some PHI derived value. This can
740 // require arbitrary PHI insertion, of which we are prepared to do, clean
742 SmallVector<Use *, 16> UsesToRename;
744 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
747 auto *NewI = cast<Instruction>(VT.second);
748 // Scan all uses of this instruction to see if it is used outside of its
749 // funclet, and if so, record them in UsesToRename.
750 for (Use &U : OldI->uses()) {
751 Instruction *UserI = cast<Instruction>(U.getUser());
752 BasicBlock *UserBB = UserI->getParent();
753 ColorVector &ColorsForUserBB = BlockColors[UserBB];
754 assert(!ColorsForUserBB.empty());
755 if (ColorsForUserBB.size() > 1 ||
756 *ColorsForUserBB.begin() != FuncletPadBB)
757 UsesToRename.push_back(&U);
760 // If there are no uses outside the block, we're done with this
762 if (UsesToRename.empty())
765 // We found a use of OldI outside of the funclet. Rename all uses of OldI
766 // that are outside its funclet to be uses of the appropriate PHI node
768 SSAUpdater SSAUpdate;
769 SSAUpdate.Initialize(OldI->getType(), OldI->getName());
770 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
771 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
773 while (!UsesToRename.empty())
774 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
779 void WinEHPrepare::removeImplausibleInstructions(Function &F) {
780 // Remove implausible terminators and replace them with UnreachableInst.
781 for (auto &Funclet : FuncletBlocks) {
782 BasicBlock *FuncletPadBB = Funclet.first;
783 std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
784 Instruction *FirstNonPHI = FuncletPadBB->getFirstNonPHI();
785 auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);
786 auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);
787 auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);
789 for (BasicBlock *BB : BlocksInFunclet) {
790 for (Instruction &I : *BB) {
795 Value *FuncletBundleOperand = nullptr;
796 if (auto BU = CS.getOperandBundle(LLVMContext::OB_funclet))
797 FuncletBundleOperand = BU->Inputs.front();
799 if (FuncletBundleOperand == FuncletPad)
802 // Skip call sites which are nounwind intrinsics.
804 dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
805 if (CalledFn && CalledFn->isIntrinsic() && CS.doesNotThrow())
808 // This call site was not part of this funclet, remove it.
810 // Remove the unwind edge if it was an invoke.
811 removeUnwindEdge(BB);
812 // Get a pointer to the new call.
813 BasicBlock::iterator CallI =
814 std::prev(BB->getTerminator()->getIterator());
815 auto *CI = cast<CallInst>(&*CallI);
816 changeToUnreachable(CI, /*UseLLVMTrap=*/false);
818 changeToUnreachable(&I, /*UseLLVMTrap=*/false);
821 // There are no more instructions in the block (except for unreachable),
826 TerminatorInst *TI = BB->getTerminator();
827 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
828 bool IsUnreachableRet = isa<ReturnInst>(TI) && FuncletPad;
829 // The token consumed by a CatchReturnInst must match the funclet token.
830 bool IsUnreachableCatchret = false;
831 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
832 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
833 // The token consumed by a CleanupReturnInst must match the funclet token.
834 bool IsUnreachableCleanupret = false;
835 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
836 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
837 if (IsUnreachableRet || IsUnreachableCatchret ||
838 IsUnreachableCleanupret) {
839 changeToUnreachable(TI, /*UseLLVMTrap=*/false);
840 } else if (isa<InvokeInst>(TI)) {
841 if (Personality == EHPersonality::MSVC_CXX && CleanupPad) {
842 // Invokes within a cleanuppad for the MSVC++ personality never
843 // transfer control to their unwind edge: the personality will
844 // terminate the program.
845 removeUnwindEdge(BB);
852 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
853 // Clean-up some of the mess we made by removing useles PHI nodes, trivial
855 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
856 BasicBlock *BB = &*FI++;
857 SimplifyInstructionsInBlock(BB);
858 ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
859 MergeBlockIntoPredecessor(BB);
862 // We might have some unreachable blocks after cleaning up some impossible
864 removeUnreachableBlocks(F);
867 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
868 for (BasicBlock &BB : F) {
869 size_t NumColors = BlockColors[&BB].size();
870 assert(NumColors == 1 && "Expected monochromatic BB!");
872 report_fatal_error("Uncolored BB!");
874 report_fatal_error("Multicolor BB!");
875 if (!DisableDemotion) {
876 bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
877 assert(!EHPadHasPHI && "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 DEBUG(verifyFunction(F));
898 removeImplausibleInstructions(F);
900 DEBUG(verifyFunction(F));
901 cleanupPreparedFunclets(F);
904 DEBUG(verifyPreparedFunclets(F));
905 // Recolor the CFG to verify that all is well.
906 DEBUG(colorFunclets(F));
907 DEBUG(verifyPreparedFunclets(F));
910 FuncletBlocks.clear();
915 // TODO: Share loads when one use dominates another, or when a catchpad exit
916 // dominates uses (needs dominators).
917 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
918 BasicBlock *PHIBlock = PN->getParent();
919 AllocaInst *SpillSlot = nullptr;
920 Instruction *EHPad = PHIBlock->getFirstNonPHI();
922 if (!isa<TerminatorInst>(EHPad)) {
923 // If the EHPad isn't a terminator, then we can insert a load in this block
924 // that will dominate all uses.
925 SpillSlot = new AllocaInst(PN->getType(), nullptr,
926 Twine(PN->getName(), ".wineh.spillslot"),
927 &F.getEntryBlock().front());
928 Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
929 &*PHIBlock->getFirstInsertionPt());
930 PN->replaceAllUsesWith(V);
934 // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
935 // loads of the slot before every use.
936 DenseMap<BasicBlock *, Value *> Loads;
937 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
940 auto *UsingInst = cast<Instruction>(U.getUser());
941 if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
942 // Use is on an EH pad phi. Leave it alone; we'll insert loads and
943 // stores for it separately.
946 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
951 // TODO: improve store placement. Inserting at def is probably good, but need
952 // to be careful not to introduce interfering stores (needs liveness analysis).
953 // TODO: identify related phi nodes that can share spill slots, and share them
954 // (also needs liveness).
955 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
956 AllocaInst *SpillSlot) {
957 // Use a worklist of (Block, Value) pairs -- the given Value needs to be
958 // stored to the spill slot by the end of the given Block.
959 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
961 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
963 while (!Worklist.empty()) {
966 std::tie(EHBlock, InVal) = Worklist.pop_back_val();
968 PHINode *PN = dyn_cast<PHINode>(InVal);
969 if (PN && PN->getParent() == EHBlock) {
970 // The value is defined by another PHI we need to remove, with no room to
971 // insert a store after the PHI, so each predecessor needs to store its
973 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
974 Value *PredVal = PN->getIncomingValue(i);
976 // Undef can safely be skipped.
977 if (isa<UndefValue>(PredVal))
980 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
983 // We need to store InVal, which dominates EHBlock, but can't put a store
984 // in EHBlock, so need to put stores in each predecessor.
985 for (BasicBlock *PredBlock : predecessors(EHBlock)) {
986 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
992 void WinEHPrepare::insertPHIStore(
993 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
994 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
996 if (PredBlock->isEHPad() &&
997 isa<TerminatorInst>(PredBlock->getFirstNonPHI())) {
998 // Pred is unsplittable, so we need to queue it on the worklist.
999 Worklist.push_back({PredBlock, PredVal});
1003 // Otherwise, insert the store at the end of the basic block.
1004 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
1007 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
1008 DenseMap<BasicBlock *, Value *> &Loads,
1010 // Lazilly create the spill slot.
1012 SpillSlot = new AllocaInst(V->getType(), nullptr,
1013 Twine(V->getName(), ".wineh.spillslot"),
1014 &F.getEntryBlock().front());
1016 auto *UsingInst = cast<Instruction>(U.getUser());
1017 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
1018 // If this is a PHI node, we can't insert a load of the value before
1019 // the use. Instead insert the load in the predecessor block
1020 // corresponding to the incoming value.
1022 // Note that if there are multiple edges from a basic block to this
1023 // PHI node that we cannot have multiple loads. The problem is that
1024 // the resulting PHI node will have multiple values (from each load)
1025 // coming in from the same block, which is illegal SSA form.
1026 // For this reason, we keep track of and reuse loads we insert.
1027 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
1028 if (auto *CatchRet =
1029 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
1030 // Putting a load above a catchret and use on the phi would still leave
1031 // a cross-funclet def/use. We need to split the edge, change the
1032 // catchret to target the new block, and put the load there.
1033 BasicBlock *PHIBlock = UsingInst->getParent();
1034 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
1035 // SplitEdge gives us:
1038 // br label %NewBlock
1040 // catchret label %PHIBlock
1044 // catchret label %NewBlock
1046 // br label %PHIBlock
1047 // So move the terminators to each others' blocks and swap their
1049 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1050 Goto->removeFromParent();
1051 CatchRet->removeFromParent();
1052 IncomingBlock->getInstList().push_back(CatchRet);
1053 NewBlock->getInstList().push_back(Goto);
1054 Goto->setSuccessor(0, PHIBlock);
1055 CatchRet->setSuccessor(NewBlock);
1056 // Update the color mapping for the newly split edge.
1057 ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1058 BlockColors[NewBlock] = ColorsForPHIBlock;
1059 for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1060 FuncletBlocks[FuncletPad].push_back(NewBlock);
1061 // Treat the new block as incoming for load insertion.
1062 IncomingBlock = NewBlock;
1064 Value *&Load = Loads[IncomingBlock];
1065 // Insert the load into the predecessor block
1067 Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1068 /*Volatile=*/false, IncomingBlock->getTerminator());
1072 // Reload right before the old use.
1073 auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1074 /*Volatile=*/false, UsingInst);
1079 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1080 MCSymbol *InvokeBegin,
1081 MCSymbol *InvokeEnd) {
1082 assert(InvokeStateMap.count(II) &&
1083 "should get invoke with precomputed state");
1084 LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);
1087 WinEHFuncInfo::WinEHFuncInfo() {}