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 removeImplausibleTerminators(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 &&
169 "multi-color BB not removed by preparation");
170 BasicBlock *FuncletEntryBB = BBColors.front();
172 BasicBlock *FuncletUnwindDest;
174 dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHI());
175 assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());
177 FuncletUnwindDest = nullptr;
178 else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))
179 FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();
180 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))
181 FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);
183 llvm_unreachable("unexpected funclet pad!");
185 BasicBlock *InvokeUnwindDest = II->getUnwindDest();
187 if (FuncletUnwindDest == InvokeUnwindDest) {
188 auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);
189 if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())
190 BaseState = BaseStateI->second;
193 if (BaseState != -1) {
194 FuncInfo.InvokeStateMap[II] = BaseState;
196 Instruction *PadInst = InvokeUnwindDest->getFirstNonPHI();
197 assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");
198 FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];
203 // Given BB which ends in an unwind edge, return the EHPad that this BB belongs
204 // to. If the unwind edge came from an invoke, return null.
205 static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,
207 const TerminatorInst *TI = BB->getTerminator();
208 if (isa<InvokeInst>(TI))
210 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {
211 if (CatchSwitch->getParentPad() != ParentPad)
215 assert(!TI->isEHPad() && "unexpected EHPad!");
216 auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();
217 if (CleanupPad->getParentPad() != ParentPad)
219 return CleanupPad->getParent();
222 static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,
223 const Instruction *FirstNonPHI,
225 const BasicBlock *BB = FirstNonPHI->getParent();
226 assert(BB->isEHPad() && "not a funclet!");
228 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
229 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
230 "shouldn't revist catch funclets!");
232 SmallVector<const CatchPadInst *, 2> Handlers;
233 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
234 auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
235 Handlers.push_back(CatchPad);
237 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
238 FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;
239 for (const BasicBlock *PredBlock : predecessors(BB))
240 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
241 CatchSwitch->getParentPad())))
242 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
244 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);
246 // catchpads are separate funclets in C++ EH due to the way rethrow works.
247 int TryHigh = CatchLow - 1;
248 for (const auto *CatchPad : Handlers) {
249 FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;
250 for (const User *U : CatchPad->users()) {
251 const auto *UserI = cast<Instruction>(U);
252 if (UserI->isEHPad())
253 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);
256 int CatchHigh = FuncInfo.getLastStateNumber();
257 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);
258 DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');
259 DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh << '\n');
260 DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh
263 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
265 // It's possible for a cleanup to be visited twice: it might have multiple
266 // cleanupret instructions.
267 if (FuncInfo.EHPadStateMap.count(CleanupPad))
270 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);
271 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
272 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
273 << BB->getName() << '\n');
274 for (const BasicBlock *PredBlock : predecessors(BB)) {
275 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
276 CleanupPad->getParentPad()))) {
277 calculateCXXStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
281 for (const User *U : CleanupPad->users()) {
282 const auto *UserI = cast<Instruction>(U);
283 if (UserI->isEHPad())
284 report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "
285 "contain exceptional actions");
290 static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,
291 const Function *Filter, const BasicBlock *Handler) {
292 SEHUnwindMapEntry Entry;
293 Entry.ToState = ParentState;
294 Entry.IsFinally = false;
295 Entry.Filter = Filter;
296 Entry.Handler = Handler;
297 FuncInfo.SEHUnwindMap.push_back(Entry);
298 return FuncInfo.SEHUnwindMap.size() - 1;
301 static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,
302 const BasicBlock *Handler) {
303 SEHUnwindMapEntry Entry;
304 Entry.ToState = ParentState;
305 Entry.IsFinally = true;
306 Entry.Filter = nullptr;
307 Entry.Handler = Handler;
308 FuncInfo.SEHUnwindMap.push_back(Entry);
309 return FuncInfo.SEHUnwindMap.size() - 1;
312 static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,
313 const Instruction *FirstNonPHI,
315 const BasicBlock *BB = FirstNonPHI->getParent();
316 assert(BB->isEHPad() && "no a funclet!");
318 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {
319 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&
320 "shouldn't revist catch funclets!");
322 // Extract the filter function and the __except basic block and create a
324 assert(CatchSwitch->getNumHandlers() == 1 &&
325 "SEH doesn't have multiple handlers per __try");
326 const auto *CatchPad =
327 cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHI());
328 const BasicBlock *CatchPadBB = CatchPad->getParent();
329 const Constant *FilterOrNull =
330 cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());
331 const Function *Filter = dyn_cast<Function>(FilterOrNull);
332 assert((Filter || FilterOrNull->isNullValue()) &&
333 "unexpected filter value");
334 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);
336 // Everything in the __try block uses TryState as its parent state.
337 FuncInfo.EHPadStateMap[CatchSwitch] = TryState;
338 DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "
339 << CatchPadBB->getName() << '\n');
340 for (const BasicBlock *PredBlock : predecessors(BB))
341 if ((PredBlock = getEHPadFromPredecessor(PredBlock,
342 CatchSwitch->getParentPad())))
343 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
346 // Everything in the __except block unwinds to ParentState, just like code
347 // outside the __try.
348 for (const User *U : CatchPad->users()) {
349 const auto *UserI = cast<Instruction>(U);
350 if (UserI->isEHPad()) {
351 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);
355 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);
357 // It's possible for a cleanup to be visited twice: it might have multiple
358 // cleanupret instructions.
359 if (FuncInfo.EHPadStateMap.count(CleanupPad))
362 int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);
363 FuncInfo.EHPadStateMap[CleanupPad] = CleanupState;
364 DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "
365 << BB->getName() << '\n');
366 for (const BasicBlock *PredBlock : predecessors(BB))
368 getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))
369 calculateSEHStateNumbers(FuncInfo, PredBlock->getFirstNonPHI(),
371 for (const User *U : CleanupPad->users()) {
372 const auto *UserI = cast<Instruction>(U);
373 if (UserI->isEHPad())
374 report_fatal_error("Cleanup funclets for the SEH personality cannot "
375 "contain exceptional actions");
380 static bool isTopLevelPadForMSVC(const Instruction *EHPad) {
381 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))
382 return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&
383 CatchSwitch->unwindsToCaller();
384 if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))
385 return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&
386 getCleanupRetUnwindDest(CleanupPad) == nullptr;
387 if (isa<CatchPadInst>(EHPad))
389 llvm_unreachable("unexpected EHPad!");
392 void llvm::calculateSEHStateNumbers(const Function *Fn,
393 WinEHFuncInfo &FuncInfo) {
394 // Don't compute state numbers twice.
395 if (!FuncInfo.SEHUnwindMap.empty())
398 for (const BasicBlock &BB : *Fn) {
401 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
402 if (!isTopLevelPadForMSVC(FirstNonPHI))
404 ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);
407 calculateStateNumbersForInvokes(Fn, FuncInfo);
410 void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,
411 WinEHFuncInfo &FuncInfo) {
412 // Return if it's already been done.
413 if (!FuncInfo.EHPadStateMap.empty())
416 for (const BasicBlock &BB : *Fn) {
419 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
420 if (!isTopLevelPadForMSVC(FirstNonPHI))
422 calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);
425 calculateStateNumbersForInvokes(Fn, FuncInfo);
428 static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int ParentState,
429 ClrHandlerType HandlerType, uint32_t TypeToken,
430 const BasicBlock *Handler) {
431 ClrEHUnwindMapEntry Entry;
432 Entry.Parent = ParentState;
433 Entry.Handler = Handler;
434 Entry.HandlerType = HandlerType;
435 Entry.TypeToken = TypeToken;
436 FuncInfo.ClrEHUnwindMap.push_back(Entry);
437 return FuncInfo.ClrEHUnwindMap.size() - 1;
440 void llvm::calculateClrEHStateNumbers(const Function *Fn,
441 WinEHFuncInfo &FuncInfo) {
442 // Return if it's already been done.
443 if (!FuncInfo.EHPadStateMap.empty())
446 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;
448 // Each pad needs to be able to refer to its parent, so scan the function
449 // looking for top-level handlers and seed the worklist with them.
450 for (const BasicBlock &BB : *Fn) {
453 if (BB.isLandingPad())
454 report_fatal_error("CoreCLR EH cannot use landingpads");
455 const Instruction *FirstNonPHI = BB.getFirstNonPHI();
456 if (!isTopLevelPadForMSVC(FirstNonPHI))
458 // queue this with sentinel parent state -1 to mean unwind to caller.
459 Worklist.emplace_back(FirstNonPHI, -1);
462 while (!Worklist.empty()) {
463 const Instruction *Pad;
465 std::tie(Pad, ParentState) = Worklist.pop_back_val();
469 if (const CleanupPadInst *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {
470 // A cleanup can have multiple exits; don't re-process after the first.
471 if (FuncInfo.EHPadStateMap.count(Cleanup))
473 // CoreCLR personality uses arity to distinguish faults from finallies.
474 const BasicBlock *PadBlock = Cleanup->getParent();
475 ClrHandlerType HandlerType =
476 (Cleanup->getNumOperands() ? ClrHandlerType::Fault
477 : ClrHandlerType::Finally);
479 addClrEHHandler(FuncInfo, ParentState, HandlerType, 0, PadBlock);
480 FuncInfo.EHPadStateMap[Cleanup] = NewState;
481 // Propagate the new state to all preds of the cleanup
482 ParentPad = Cleanup->getParentPad();
483 PredState = NewState;
484 } else if (const auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
485 SmallVector<const CatchPadInst *, 1> Handlers;
486 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
487 const auto *Catch = cast<CatchPadInst>(CatchPadBB->getFirstNonPHI());
488 Handlers.push_back(Catch);
490 FuncInfo.EHPadStateMap[CatchSwitch] = ParentState;
491 int NewState = ParentState;
492 for (auto HandlerI = Handlers.rbegin(), HandlerE = Handlers.rend();
493 HandlerI != HandlerE; ++HandlerI) {
494 const CatchPadInst *Catch = *HandlerI;
495 const BasicBlock *PadBlock = Catch->getParent();
496 uint32_t TypeToken = static_cast<uint32_t>(
497 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());
498 NewState = addClrEHHandler(FuncInfo, NewState, ClrHandlerType::Catch,
499 TypeToken, PadBlock);
500 FuncInfo.EHPadStateMap[Catch] = NewState;
502 for (const auto *CatchPad : Handlers) {
503 for (const User *U : CatchPad->users()) {
504 const auto *UserI = cast<Instruction>(U);
505 if (UserI->isEHPad())
506 Worklist.emplace_back(UserI, ParentState);
509 PredState = NewState;
510 ParentPad = CatchSwitch->getParentPad();
512 llvm_unreachable("Unexpected EH pad");
515 // Queue all predecessors with the given state
516 for (const BasicBlock *Pred : predecessors(Pad->getParent())) {
517 if ((Pred = getEHPadFromPredecessor(Pred, ParentPad)))
518 Worklist.emplace_back(Pred->getFirstNonPHI(), PredState);
522 calculateStateNumbersForInvokes(Fn, FuncInfo);
525 void WinEHPrepare::colorFunclets(Function &F) {
526 BlockColors = colorEHFunclets(F);
528 // Invert the map from BB to colors to color to BBs.
529 for (BasicBlock &BB : F) {
530 ColorVector &Colors = BlockColors[&BB];
531 for (BasicBlock *Color : Colors)
532 FuncletBlocks[Color].push_back(&BB);
536 void llvm::calculateCatchReturnSuccessorColors(const Function *Fn,
537 WinEHFuncInfo &FuncInfo) {
538 for (const BasicBlock &BB : *Fn) {
539 const auto *CatchRet = dyn_cast<CatchReturnInst>(BB.getTerminator());
542 // A 'catchret' returns to the outer scope's color.
543 Value *ParentPad = CatchRet->getParentPad();
544 const BasicBlock *Color;
545 if (isa<ConstantTokenNone>(ParentPad))
546 Color = &Fn->getEntryBlock();
548 Color = cast<Instruction>(ParentPad)->getParent();
549 // Record the catchret successor's funclet membership.
550 FuncInfo.CatchRetSuccessorColorMap[CatchRet] = Color;
554 void WinEHPrepare::demotePHIsOnFunclets(Function &F) {
555 // Strip PHI nodes off of EH pads.
556 SmallVector<PHINode *, 16> PHINodes;
557 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
558 BasicBlock *BB = &*FI++;
561 for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
562 Instruction *I = &*BI++;
563 auto *PN = dyn_cast<PHINode>(I);
564 // Stop at the first non-PHI.
568 AllocaInst *SpillSlot = insertPHILoads(PN, F);
570 insertPHIStores(PN, SpillSlot);
572 PHINodes.push_back(PN);
576 for (auto *PN : PHINodes) {
577 // There may be lingering uses on other EH PHIs being removed
578 PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
579 PN->eraseFromParent();
583 void WinEHPrepare::cloneCommonBlocks(Function &F) {
584 // We need to clone all blocks which belong to multiple funclets. Values are
585 // remapped throughout the funclet to propogate both the new instructions
586 // *and* the new basic blocks themselves.
587 for (auto &Funclets : FuncletBlocks) {
588 BasicBlock *FuncletPadBB = Funclets.first;
589 std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;
591 std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;
592 ValueToValueMapTy VMap;
593 for (BasicBlock *BB : BlocksInFunclet) {
594 ColorVector &ColorsForBB = BlockColors[BB];
595 // We don't need to do anything if the block is monochromatic.
596 size_t NumColorsForBB = ColorsForBB.size();
597 if (NumColorsForBB == 1)
600 DEBUG_WITH_TYPE("winehprepare-coloring",
601 dbgs() << " Cloning block \'" << BB->getName()
602 << "\' for funclet \'" << FuncletPadBB->getName()
605 // Create a new basic block and copy instructions into it!
607 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));
608 // Insert the clone immediately after the original to ensure determinism
609 // and to keep the same relative ordering of any funclet's blocks.
610 CBB->insertInto(&F, BB->getNextNode());
612 // Add basic block mapping.
615 // Record delta operations that we need to perform to our color mappings.
616 Orig2Clone.emplace_back(BB, CBB);
619 // If nothing was cloned, we're done cloning in this funclet.
620 if (Orig2Clone.empty())
623 // Update our color mappings to reflect that one block has lost a color and
624 // another has gained a color.
625 for (auto &BBMapping : Orig2Clone) {
626 BasicBlock *OldBlock = BBMapping.first;
627 BasicBlock *NewBlock = BBMapping.second;
629 BlocksInFunclet.push_back(NewBlock);
630 ColorVector &NewColors = BlockColors[NewBlock];
631 assert(NewColors.empty() && "A new block should only have one color!");
632 NewColors.push_back(FuncletPadBB);
634 DEBUG_WITH_TYPE("winehprepare-coloring",
635 dbgs() << " Assigned color \'" << FuncletPadBB->getName()
636 << "\' to block \'" << NewBlock->getName()
639 BlocksInFunclet.erase(
640 std::remove(BlocksInFunclet.begin(), BlocksInFunclet.end(), OldBlock),
641 BlocksInFunclet.end());
642 ColorVector &OldColors = BlockColors[OldBlock];
644 std::remove(OldColors.begin(), OldColors.end(), FuncletPadBB),
647 DEBUG_WITH_TYPE("winehprepare-coloring",
648 dbgs() << " Removed color \'" << FuncletPadBB->getName()
649 << "\' from block \'" << OldBlock->getName()
653 // Loop over all of the instructions in this funclet, fixing up operand
654 // references as we go. This uses VMap to do all the hard work.
655 for (BasicBlock *BB : BlocksInFunclet)
656 // Loop over all instructions, fixing each one as we find it...
657 for (Instruction &I : *BB)
658 RemapInstruction(&I, VMap,
659 RF_IgnoreMissingEntries | RF_NoModuleLevelChanges);
661 auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {
662 unsigned NumPreds = PN->getNumIncomingValues();
663 for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;
665 BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);
666 ColorVector &IncomingColors = BlockColors[IncomingBlock];
667 bool BlockInFunclet = IncomingColors.size() == 1 &&
668 IncomingColors.front() == FuncletPadBB;
669 if (IsForOldBlock != BlockInFunclet)
671 PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);
672 // Revisit the next entry.
678 for (auto &BBMapping : Orig2Clone) {
679 BasicBlock *OldBlock = BBMapping.first;
680 BasicBlock *NewBlock = BBMapping.second;
681 for (Instruction &OldI : *OldBlock) {
682 auto *OldPN = dyn_cast<PHINode>(&OldI);
685 UpdatePHIOnClonedBlock(OldPN, /*IsForOldBlock=*/true);
687 for (Instruction &NewI : *NewBlock) {
688 auto *NewPN = dyn_cast<PHINode>(&NewI);
691 UpdatePHIOnClonedBlock(NewPN, /*IsForOldBlock=*/false);
695 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to
696 // the PHI nodes for NewBB now.
697 for (auto &BBMapping : Orig2Clone) {
698 BasicBlock *OldBlock = BBMapping.first;
699 BasicBlock *NewBlock = BBMapping.second;
700 for (BasicBlock *SuccBB : successors(NewBlock)) {
701 for (Instruction &SuccI : *SuccBB) {
702 auto *SuccPN = dyn_cast<PHINode>(&SuccI);
706 // Ok, we have a PHI node. Figure out what the incoming value was for
708 int OldBlockIdx = SuccPN->getBasicBlockIndex(OldBlock);
709 if (OldBlockIdx == -1)
711 Value *IV = SuccPN->getIncomingValue(OldBlockIdx);
713 // Remap the value if necessary.
714 if (auto *Inst = dyn_cast<Instruction>(IV)) {
715 ValueToValueMapTy::iterator I = VMap.find(Inst);
720 SuccPN->addIncoming(IV, NewBlock);
725 for (ValueToValueMapTy::value_type VT : VMap) {
726 // If there were values defined in BB that are used outside the funclet,
727 // then we now have to update all uses of the value to use either the
728 // original value, the cloned value, or some PHI derived value. This can
729 // require arbitrary PHI insertion, of which we are prepared to do, clean
731 SmallVector<Use *, 16> UsesToRename;
733 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));
736 auto *NewI = cast<Instruction>(VT.second);
737 // Scan all uses of this instruction to see if it is used outside of its
738 // funclet, and if so, record them in UsesToRename.
739 for (Use &U : OldI->uses()) {
740 Instruction *UserI = cast<Instruction>(U.getUser());
741 BasicBlock *UserBB = UserI->getParent();
742 ColorVector &ColorsForUserBB = BlockColors[UserBB];
743 assert(!ColorsForUserBB.empty());
744 if (ColorsForUserBB.size() > 1 ||
745 *ColorsForUserBB.begin() != FuncletPadBB)
746 UsesToRename.push_back(&U);
749 // If there are no uses outside the block, we're done with this
751 if (UsesToRename.empty())
754 // We found a use of OldI outside of the funclet. Rename all uses of OldI
755 // that are outside its funclet to be uses of the appropriate PHI node
757 SSAUpdater SSAUpdate;
758 SSAUpdate.Initialize(OldI->getType(), OldI->getName());
759 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);
760 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);
762 while (!UsesToRename.empty())
763 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());
768 void WinEHPrepare::removeImplausibleTerminators(Function &F) {
769 // Remove implausible terminators and replace them with UnreachableInst.
770 for (auto &Funclet : FuncletBlocks) {
771 BasicBlock *FuncletPadBB = Funclet.first;
772 std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;
773 Instruction *FuncletPadInst = FuncletPadBB->getFirstNonPHI();
774 auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPadInst);
775 auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPadInst);
777 for (BasicBlock *BB : BlocksInFunclet) {
778 TerminatorInst *TI = BB->getTerminator();
779 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.
780 bool IsUnreachableRet = isa<ReturnInst>(TI) && (CatchPad || CleanupPad);
781 // The token consumed by a CatchReturnInst must match the funclet token.
782 bool IsUnreachableCatchret = false;
783 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))
784 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;
785 // The token consumed by a CleanupReturnInst must match the funclet token.
786 bool IsUnreachableCleanupret = false;
787 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))
788 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;
789 if (IsUnreachableRet || IsUnreachableCatchret ||
790 IsUnreachableCleanupret) {
791 // Loop through all of our successors and make sure they know that one
792 // of their predecessors is going away.
793 for (BasicBlock *SuccBB : TI->successors())
794 SuccBB->removePredecessor(BB);
796 new UnreachableInst(BB->getContext(), TI);
797 TI->eraseFromParent();
798 } else if (isa<InvokeInst>(TI)) {
799 // Invokes within a cleanuppad for the MSVC++ personality never
800 // transfer control to their unwind edge: the personality will
801 // terminate the program.
802 if (Personality == EHPersonality::MSVC_CXX && CleanupPad)
803 removeUnwindEdge(BB);
809 void WinEHPrepare::cleanupPreparedFunclets(Function &F) {
810 // Clean-up some of the mess we made by removing useles PHI nodes, trivial
812 for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE;) {
813 BasicBlock *BB = &*FI++;
814 SimplifyInstructionsInBlock(BB);
815 ConstantFoldTerminator(BB, /*DeleteDeadConditions=*/true);
816 MergeBlockIntoPredecessor(BB);
819 // We might have some unreachable blocks after cleaning up some impossible
821 removeUnreachableBlocks(F);
824 void WinEHPrepare::verifyPreparedFunclets(Function &F) {
825 // Recolor the CFG to verify that all is well.
826 for (BasicBlock &BB : F) {
827 size_t NumColors = BlockColors[&BB].size();
828 assert(NumColors == 1 && "Expected monochromatic BB!");
830 report_fatal_error("Uncolored BB!");
832 report_fatal_error("Multicolor BB!");
833 if (!DisableDemotion) {
834 bool EHPadHasPHI = BB.isEHPad() && isa<PHINode>(BB.begin());
835 assert(!EHPadHasPHI && "EH Pad still has a PHI!");
837 report_fatal_error("EH Pad still has a PHI!");
842 bool WinEHPrepare::prepareExplicitEH(Function &F) {
843 // Remove unreachable blocks. It is not valuable to assign them a color and
844 // their existence can trick us into thinking values are alive when they are
846 removeUnreachableBlocks(F);
848 // Determine which blocks are reachable from which funclet entries.
851 cloneCommonBlocks(F);
853 if (!DisableDemotion)
854 demotePHIsOnFunclets(F);
856 if (!DisableCleanups) {
857 removeImplausibleTerminators(F);
859 cleanupPreparedFunclets(F);
862 verifyPreparedFunclets(F);
865 FuncletBlocks.clear();
870 // TODO: Share loads when one use dominates another, or when a catchpad exit
871 // dominates uses (needs dominators).
872 AllocaInst *WinEHPrepare::insertPHILoads(PHINode *PN, Function &F) {
873 BasicBlock *PHIBlock = PN->getParent();
874 AllocaInst *SpillSlot = nullptr;
875 Instruction *EHPad = PHIBlock->getFirstNonPHI();
877 if (!isa<TerminatorInst>(EHPad)) {
878 // If the EHPad isn't a terminator, then we can insert a load in this block
879 // that will dominate all uses.
880 SpillSlot = new AllocaInst(PN->getType(), nullptr,
881 Twine(PN->getName(), ".wineh.spillslot"),
882 &F.getEntryBlock().front());
883 Value *V = new LoadInst(SpillSlot, Twine(PN->getName(), ".wineh.reload"),
884 &*PHIBlock->getFirstInsertionPt());
885 PN->replaceAllUsesWith(V);
889 // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert
890 // loads of the slot before every use.
891 DenseMap<BasicBlock *, Value *> Loads;
892 for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
895 auto *UsingInst = cast<Instruction>(U.getUser());
896 if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {
897 // Use is on an EH pad phi. Leave it alone; we'll insert loads and
898 // stores for it separately.
901 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);
906 // TODO: improve store placement. Inserting at def is probably good, but need
907 // to be careful not to introduce interfering stores (needs liveness analysis).
908 // TODO: identify related phi nodes that can share spill slots, and share them
909 // (also needs liveness).
910 void WinEHPrepare::insertPHIStores(PHINode *OriginalPHI,
911 AllocaInst *SpillSlot) {
912 // Use a worklist of (Block, Value) pairs -- the given Value needs to be
913 // stored to the spill slot by the end of the given Block.
914 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;
916 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});
918 while (!Worklist.empty()) {
921 std::tie(EHBlock, InVal) = Worklist.pop_back_val();
923 PHINode *PN = dyn_cast<PHINode>(InVal);
924 if (PN && PN->getParent() == EHBlock) {
925 // The value is defined by another PHI we need to remove, with no room to
926 // insert a store after the PHI, so each predecessor needs to store its
928 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
929 Value *PredVal = PN->getIncomingValue(i);
931 // Undef can safely be skipped.
932 if (isa<UndefValue>(PredVal))
935 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);
938 // We need to store InVal, which dominates EHBlock, but can't put a store
939 // in EHBlock, so need to put stores in each predecessor.
940 for (BasicBlock *PredBlock : predecessors(EHBlock)) {
941 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);
947 void WinEHPrepare::insertPHIStore(
948 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,
949 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {
951 if (PredBlock->isEHPad() &&
952 isa<TerminatorInst>(PredBlock->getFirstNonPHI())) {
953 // Pred is unsplittable, so we need to queue it on the worklist.
954 Worklist.push_back({PredBlock, PredVal});
958 // Otherwise, insert the store at the end of the basic block.
959 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator());
962 void WinEHPrepare::replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,
963 DenseMap<BasicBlock *, Value *> &Loads,
965 // Lazilly create the spill slot.
967 SpillSlot = new AllocaInst(V->getType(), nullptr,
968 Twine(V->getName(), ".wineh.spillslot"),
969 &F.getEntryBlock().front());
971 auto *UsingInst = cast<Instruction>(U.getUser());
972 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {
973 // If this is a PHI node, we can't insert a load of the value before
974 // the use. Instead insert the load in the predecessor block
975 // corresponding to the incoming value.
977 // Note that if there are multiple edges from a basic block to this
978 // PHI node that we cannot have multiple loads. The problem is that
979 // the resulting PHI node will have multiple values (from each load)
980 // coming in from the same block, which is illegal SSA form.
981 // For this reason, we keep track of and reuse loads we insert.
982 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);
984 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {
985 // Putting a load above a catchret and use on the phi would still leave
986 // a cross-funclet def/use. We need to split the edge, change the
987 // catchret to target the new block, and put the load there.
988 BasicBlock *PHIBlock = UsingInst->getParent();
989 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);
990 // SplitEdge gives us:
993 // br label %NewBlock
995 // catchret label %PHIBlock
999 // catchret label %NewBlock
1001 // br label %PHIBlock
1002 // So move the terminators to each others' blocks and swap their
1004 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());
1005 Goto->removeFromParent();
1006 CatchRet->removeFromParent();
1007 IncomingBlock->getInstList().push_back(CatchRet);
1008 NewBlock->getInstList().push_back(Goto);
1009 Goto->setSuccessor(0, PHIBlock);
1010 CatchRet->setSuccessor(NewBlock);
1011 // Update the color mapping for the newly split edge.
1012 ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];
1013 BlockColors[NewBlock] = ColorsForPHIBlock;
1014 for (BasicBlock *FuncletPad : ColorsForPHIBlock)
1015 FuncletBlocks[FuncletPad].push_back(NewBlock);
1016 // Treat the new block as incoming for load insertion.
1017 IncomingBlock = NewBlock;
1019 Value *&Load = Loads[IncomingBlock];
1020 // Insert the load into the predecessor block
1022 Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1023 /*Volatile=*/false, IncomingBlock->getTerminator());
1027 // Reload right before the old use.
1028 auto *Load = new LoadInst(SpillSlot, Twine(V->getName(), ".wineh.reload"),
1029 /*Volatile=*/false, UsingInst);
1034 void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,
1035 MCSymbol *InvokeBegin,
1036 MCSymbol *InvokeEnd) {
1037 assert(InvokeStateMap.count(II) &&
1038 "should get invoke with precomputed state");
1039 LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);