1452 lines · cpp
1//===-- WinEHPrepare - Prepare exception handling for code generation ---===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass lowers LLVM IR exception handling into something closer to what the10// backend wants for functions using a personality function from a runtime11// provided by MSVC. Functions with other personality functions are left alone12// and may be prepared by other passes. In particular, all supported MSVC13// personality functions require cleanup code to be outlined, and the C++14// personality requires catch handler code to be outlined.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/CodeGen/WinEHPrepare.h"19#include "llvm/ADT/DenseMap.h"20#include "llvm/ADT/MapVector.h"21#include "llvm/ADT/STLExtras.h"22#include "llvm/CodeGen/MachineBasicBlock.h"23#include "llvm/CodeGen/Passes.h"24#include "llvm/CodeGen/WinEHFuncInfo.h"25#include "llvm/IR/Constants.h"26#include "llvm/IR/EHPersonalities.h"27#include "llvm/IR/Instructions.h"28#include "llvm/IR/Module.h"29#include "llvm/IR/Verifier.h"30#include "llvm/InitializePasses.h"31#include "llvm/Pass.h"32#include "llvm/Support/CommandLine.h"33#include "llvm/Support/Debug.h"34#include "llvm/Support/raw_ostream.h"35#include "llvm/TargetParser/Triple.h"36#include "llvm/Transforms/Utils/BasicBlockUtils.h"37#include "llvm/Transforms/Utils/Cloning.h"38#include "llvm/Transforms/Utils/Local.h"39#include "llvm/Transforms/Utils/SSAUpdater.h"40 41using namespace llvm;42 43#define DEBUG_TYPE "win-eh-prepare"44 45static cl::opt<bool> DisableDemotion(46 "disable-demotion", cl::Hidden,47 cl::desc(48 "Clone multicolor basic blocks but do not demote cross scopes"),49 cl::init(false));50 51static cl::opt<bool> DisableCleanups(52 "disable-cleanups", cl::Hidden,53 cl::desc("Do not remove implausible terminators or other similar cleanups"),54 cl::init(false));55 56// TODO: Remove this option when we fully migrate to new pass manager57static cl::opt<bool> DemoteCatchSwitchPHIOnlyOpt(58 "demote-catchswitch-only", cl::Hidden,59 cl::desc("Demote catchswitch BBs only (for wasm EH)"), cl::init(false));60 61namespace {62 63class WinEHPrepareImpl {64public:65 WinEHPrepareImpl(bool DemoteCatchSwitchPHIOnly)66 : DemoteCatchSwitchPHIOnly(DemoteCatchSwitchPHIOnly) {}67 68 bool runOnFunction(Function &Fn);69 70private:71 void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);72 void73 insertPHIStore(BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,74 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist);75 AllocaInst *insertPHILoads(PHINode *PN, Function &F);76 void replaceUseWithLoad(Value *V, Use &U, AllocaInst *&SpillSlot,77 DenseMap<BasicBlock *, Value *> &Loads, Function &F);78 bool prepareExplicitEH(Function &F);79 void colorFunclets(Function &F);80 81 bool demotePHIsOnFunclets(Function &F, bool DemoteCatchSwitchPHIOnly);82 bool cloneCommonBlocks(Function &F);83 bool removeImplausibleInstructions(Function &F);84 bool cleanupPreparedFunclets(Function &F);85 void verifyPreparedFunclets(Function &F);86 87 bool DemoteCatchSwitchPHIOnly;88 89 // All fields are reset by runOnFunction.90 EHPersonality Personality = EHPersonality::Unknown;91 92 const DataLayout *DL = nullptr;93 DenseMap<BasicBlock *, ColorVector> BlockColors;94 MapVector<BasicBlock *, std::vector<BasicBlock *>> FuncletBlocks;95};96 97class WinEHPrepare : public FunctionPass {98 bool DemoteCatchSwitchPHIOnly;99 100public:101 static char ID; // Pass identification, replacement for typeid.102 103 WinEHPrepare(bool DemoteCatchSwitchPHIOnly = false)104 : FunctionPass(ID), DemoteCatchSwitchPHIOnly(DemoteCatchSwitchPHIOnly) {}105 106 StringRef getPassName() const override {107 return "Windows exception handling preparation";108 }109 110 bool runOnFunction(Function &Fn) override {111 return WinEHPrepareImpl(DemoteCatchSwitchPHIOnly).runOnFunction(Fn);112 }113};114 115} // end anonymous namespace116 117PreservedAnalyses WinEHPreparePass::run(Function &F,118 FunctionAnalysisManager &) {119 bool Changed = WinEHPrepareImpl(DemoteCatchSwitchPHIOnly).runOnFunction(F);120 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();121}122 123char WinEHPrepare::ID = 0;124INITIALIZE_PASS(WinEHPrepare, DEBUG_TYPE, "Prepare Windows exceptions", false,125 false)126 127FunctionPass *llvm::createWinEHPass(bool DemoteCatchSwitchPHIOnly) {128 return new WinEHPrepare(DemoteCatchSwitchPHIOnly);129}130 131bool WinEHPrepareImpl::runOnFunction(Function &Fn) {132 if (!Fn.hasPersonalityFn())133 return false;134 135 // Classify the personality to see what kind of preparation we need.136 Personality = classifyEHPersonality(Fn.getPersonalityFn());137 138 // Do nothing if this is not a scope-based personality.139 if (!isScopedEHPersonality(Personality))140 return false;141 142 DL = &Fn.getDataLayout();143 return prepareExplicitEH(Fn);144}145 146static int addUnwindMapEntry(WinEHFuncInfo &FuncInfo, int ToState,147 const BasicBlock *BB) {148 CxxUnwindMapEntry UME;149 UME.ToState = ToState;150 UME.Cleanup = BB;151 FuncInfo.CxxUnwindMap.push_back(UME);152 return FuncInfo.getLastStateNumber();153}154 155static void addTryBlockMapEntry(WinEHFuncInfo &FuncInfo, int TryLow,156 int TryHigh, int CatchHigh,157 ArrayRef<const CatchPadInst *> Handlers) {158 WinEHTryBlockMapEntry TBME;159 TBME.TryLow = TryLow;160 TBME.TryHigh = TryHigh;161 TBME.CatchHigh = CatchHigh;162 assert(TBME.TryLow <= TBME.TryHigh);163 for (const CatchPadInst *CPI : Handlers) {164 WinEHHandlerType HT;165 Constant *TypeInfo = cast<Constant>(CPI->getArgOperand(0));166 if (TypeInfo->isNullValue())167 HT.TypeDescriptor = nullptr;168 else169 HT.TypeDescriptor = cast<GlobalVariable>(TypeInfo->stripPointerCasts());170 HT.Adjectives = cast<ConstantInt>(CPI->getArgOperand(1))->getZExtValue();171 HT.Handler = CPI->getParent();172 if (auto *AI =173 dyn_cast<AllocaInst>(CPI->getArgOperand(2)->stripPointerCasts()))174 HT.CatchObj.Alloca = AI;175 else176 HT.CatchObj.Alloca = nullptr;177 TBME.HandlerArray.push_back(HT);178 }179 FuncInfo.TryBlockMap.push_back(TBME);180}181 182static BasicBlock *getCleanupRetUnwindDest(const CleanupPadInst *CleanupPad) {183 for (const User *U : CleanupPad->users())184 if (const auto *CRI = dyn_cast<CleanupReturnInst>(U))185 return CRI->getUnwindDest();186 return nullptr;187}188 189static void calculateStateNumbersForInvokes(const Function *Fn,190 WinEHFuncInfo &FuncInfo) {191 auto *F = const_cast<Function *>(Fn);192 DenseMap<BasicBlock *, ColorVector> BlockColors = colorEHFunclets(*F);193 for (BasicBlock &BB : *F) {194 auto *II = dyn_cast<InvokeInst>(BB.getTerminator());195 if (!II)196 continue;197 198 auto &BBColors = BlockColors[&BB];199 assert(BBColors.size() == 1 && "multi-color BB not removed by preparation");200 BasicBlock *FuncletEntryBB = BBColors.front();201 202 BasicBlock *FuncletUnwindDest;203 auto *FuncletPad =204 dyn_cast<FuncletPadInst>(FuncletEntryBB->getFirstNonPHIIt());205 assert(FuncletPad || FuncletEntryBB == &Fn->getEntryBlock());206 if (!FuncletPad)207 FuncletUnwindDest = nullptr;208 else if (auto *CatchPad = dyn_cast<CatchPadInst>(FuncletPad))209 FuncletUnwindDest = CatchPad->getCatchSwitch()->getUnwindDest();210 else if (auto *CleanupPad = dyn_cast<CleanupPadInst>(FuncletPad))211 FuncletUnwindDest = getCleanupRetUnwindDest(CleanupPad);212 else213 llvm_unreachable("unexpected funclet pad!");214 215 BasicBlock *InvokeUnwindDest = II->getUnwindDest();216 int BaseState = -1;217 if (FuncletUnwindDest == InvokeUnwindDest) {218 auto BaseStateI = FuncInfo.FuncletBaseStateMap.find(FuncletPad);219 if (BaseStateI != FuncInfo.FuncletBaseStateMap.end())220 BaseState = BaseStateI->second;221 }222 223 if (BaseState != -1) {224 FuncInfo.InvokeStateMap[II] = BaseState;225 } else {226 Instruction *PadInst = &*InvokeUnwindDest->getFirstNonPHIIt();227 assert(FuncInfo.EHPadStateMap.count(PadInst) && "EH Pad has no state!");228 FuncInfo.InvokeStateMap[II] = FuncInfo.EHPadStateMap[PadInst];229 }230 }231}232 233// See comments below for calculateSEHStateForAsynchEH().234// State - incoming State of normal paths235struct WorkItem {236 const BasicBlock *Block;237 int State;238 WorkItem(const BasicBlock *BB, int St) {239 Block = BB;240 State = St;241 }242};243void llvm::calculateCXXStateForAsynchEH(const BasicBlock *BB, int State,244 WinEHFuncInfo &EHInfo) {245 SmallVector<struct WorkItem *, 8> WorkList;246 struct WorkItem *WI = new WorkItem(BB, State);247 WorkList.push_back(WI);248 249 while (!WorkList.empty()) {250 WI = WorkList.pop_back_val();251 const BasicBlock *BB = WI->Block;252 int State = WI->State;253 delete WI;254 auto [StateIt, Inserted] = EHInfo.BlockToStateMap.try_emplace(BB);255 if (!Inserted && StateIt->second <= State)256 continue; // skip blocks already visited by lower State257 258 BasicBlock::const_iterator It = BB->getFirstNonPHIIt();259 const llvm::Instruction *TI = BB->getTerminator();260 if (It->isEHPad())261 State = EHInfo.EHPadStateMap[&*It];262 StateIt->second = State; // Record state, also flag visiting263 264 if ((isa<CleanupReturnInst>(TI) || isa<CatchReturnInst>(TI)) && State > 0) {265 // Retrive the new State266 State = EHInfo.CxxUnwindMap[State].ToState; // Retrive next State267 } else if (isa<InvokeInst>(TI)) {268 auto *Call = cast<CallBase>(TI);269 const Function *Fn = Call->getCalledFunction();270 if (Fn && Fn->isIntrinsic() &&271 (Fn->getIntrinsicID() == Intrinsic::seh_scope_begin ||272 Fn->getIntrinsicID() == Intrinsic::seh_try_begin))273 // Retrive the new State from seh_scope_begin274 State = EHInfo.InvokeStateMap[cast<InvokeInst>(TI)];275 else if (Fn && Fn->isIntrinsic() &&276 (Fn->getIntrinsicID() == Intrinsic::seh_scope_end ||277 Fn->getIntrinsicID() == Intrinsic::seh_try_end)) {278 // In case of conditional ctor, let's retrieve State from Invoke279 State = EHInfo.InvokeStateMap[cast<InvokeInst>(TI)];280 // end of current state, retrive new state from UnwindMap281 State = EHInfo.CxxUnwindMap[State].ToState;282 }283 }284 // Continue push successors into worklist285 for (auto *SuccBB : successors(BB)) {286 WI = new WorkItem(SuccBB, State);287 WorkList.push_back(WI);288 }289 }290}291 292// The central theory of this routine is based on the following:293// A _try scope is always a SEME (Single Entry Multiple Exits) region294// as jumping into a _try is not allowed295// The single entry must start with a seh_try_begin() invoke with a296// correct State number that is the initial state of the SEME.297// Through control-flow, state number is propagated into all blocks.298// Side exits marked by seh_try_end() will unwind to parent state via299// existing SEHUnwindMap[].300// Side exits can ONLY jump into parent scopes (lower state number).301// Thus, when a block succeeds various states from its predecessors,302// the lowest State trumphs others.303// If some exits flow to unreachable, propagation on those paths terminate,304// not affecting remaining blocks.305void llvm::calculateSEHStateForAsynchEH(const BasicBlock *BB, int State,306 WinEHFuncInfo &EHInfo) {307 SmallVector<struct WorkItem *, 8> WorkList;308 struct WorkItem *WI = new WorkItem(BB, State);309 WorkList.push_back(WI);310 311 while (!WorkList.empty()) {312 WI = WorkList.pop_back_val();313 const BasicBlock *BB = WI->Block;314 int State = WI->State;315 delete WI;316 if (auto It = EHInfo.BlockToStateMap.find(BB);317 It != EHInfo.BlockToStateMap.end() && It->second <= State)318 continue; // skip blocks already visited by lower State319 320 BasicBlock::const_iterator It = BB->getFirstNonPHIIt();321 const llvm::Instruction *TI = BB->getTerminator();322 if (It->isEHPad())323 State = EHInfo.EHPadStateMap[&*It];324 EHInfo.BlockToStateMap[BB] = State; // Record state325 326 if (isa<CatchPadInst>(It) && isa<CatchReturnInst>(TI)) {327 const Constant *FilterOrNull = cast<Constant>(328 cast<CatchPadInst>(It)->getArgOperand(0)->stripPointerCasts());329 const Function *Filter = dyn_cast<Function>(FilterOrNull);330 if (!Filter || !Filter->getName().starts_with("__IsLocalUnwind"))331 State = EHInfo.SEHUnwindMap[State].ToState; // Retrive next State332 } else if ((isa<CleanupReturnInst>(TI) || isa<CatchReturnInst>(TI)) &&333 State > 0) {334 // Retrive the new State.335 State = EHInfo.SEHUnwindMap[State].ToState; // Retrive next State336 } else if (isa<InvokeInst>(TI)) {337 auto *Call = cast<CallBase>(TI);338 const Function *Fn = Call->getCalledFunction();339 if (Fn && Fn->isIntrinsic() &&340 Fn->getIntrinsicID() == Intrinsic::seh_try_begin)341 // Retrive the new State from seh_try_begin342 State = EHInfo.InvokeStateMap[cast<InvokeInst>(TI)];343 else if (Fn && Fn->isIntrinsic() &&344 Fn->getIntrinsicID() == Intrinsic::seh_try_end)345 // end of current state, retrive new state from UnwindMap346 State = EHInfo.SEHUnwindMap[State].ToState;347 }348 // Continue push successors into worklist349 for (auto *SuccBB : successors(BB)) {350 WI = new WorkItem(SuccBB, State);351 WorkList.push_back(WI);352 }353 }354}355 356// Given BB which ends in an unwind edge, return the EHPad that this BB belongs357// to. If the unwind edge came from an invoke, return null.358static const BasicBlock *getEHPadFromPredecessor(const BasicBlock *BB,359 Value *ParentPad) {360 const Instruction *TI = BB->getTerminator();361 if (isa<InvokeInst>(TI))362 return nullptr;363 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(TI)) {364 if (CatchSwitch->getParentPad() != ParentPad)365 return nullptr;366 return BB;367 }368 assert(!TI->isEHPad() && "unexpected EHPad!");369 auto *CleanupPad = cast<CleanupReturnInst>(TI)->getCleanupPad();370 if (CleanupPad->getParentPad() != ParentPad)371 return nullptr;372 return CleanupPad->getParent();373}374 375// Starting from a EHPad, Backward walk through control-flow graph376// to produce two primary outputs:377// FuncInfo.EHPadStateMap[] and FuncInfo.CxxUnwindMap[]378static void calculateCXXStateNumbers(WinEHFuncInfo &FuncInfo,379 const Instruction *FirstNonPHI,380 int ParentState) {381 const BasicBlock *BB = FirstNonPHI->getParent();382 assert(BB->isEHPad() && "not a funclet!");383 384 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {385 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&386 "shouldn't revist catch funclets!");387 388 SmallVector<const CatchPadInst *, 2> Handlers;389 for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {390 auto *CatchPad = cast<CatchPadInst>(CatchPadBB->getFirstNonPHIIt());391 Handlers.push_back(CatchPad);392 }393 int TryLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);394 FuncInfo.EHPadStateMap[CatchSwitch] = TryLow;395 for (const BasicBlock *PredBlock : predecessors(BB))396 if ((PredBlock = getEHPadFromPredecessor(PredBlock,397 CatchSwitch->getParentPad())))398 calculateCXXStateNumbers(FuncInfo, &*PredBlock->getFirstNonPHIIt(),399 TryLow);400 int CatchLow = addUnwindMapEntry(FuncInfo, ParentState, nullptr);401 402 // catchpads are separate funclets in C++ EH due to the way rethrow works.403 int TryHigh = CatchLow - 1;404 405 // MSVC FrameHandler3/4 on x64&Arm64 expect Catch Handlers in $tryMap$406 // stored in pre-order (outer first, inner next), not post-order407 // Add to map here. Fix the CatchHigh after children are processed408 const Module *Mod = BB->getParent()->getParent();409 bool IsPreOrder = Mod->getTargetTriple().isArch64Bit();410 if (IsPreOrder)411 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchLow, Handlers);412 unsigned TBMEIdx = FuncInfo.TryBlockMap.size() - 1;413 414 for (const auto *CatchPad : Handlers) {415 FuncInfo.FuncletBaseStateMap[CatchPad] = CatchLow;416 FuncInfo.EHPadStateMap[CatchPad] = CatchLow;417 for (const User *U : CatchPad->users()) {418 const auto *UserI = cast<Instruction>(U);419 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {420 BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();421 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())422 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);423 }424 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {425 BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);426 // If a nested cleanup pad reports a null unwind destination and the427 // enclosing catch pad doesn't it must be post-dominated by an428 // unreachable instruction.429 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())430 calculateCXXStateNumbers(FuncInfo, UserI, CatchLow);431 }432 }433 }434 int CatchHigh = FuncInfo.getLastStateNumber();435 // Now child Catches are processed, update CatchHigh436 if (IsPreOrder)437 FuncInfo.TryBlockMap[TBMEIdx].CatchHigh = CatchHigh;438 else // PostOrder439 addTryBlockMapEntry(FuncInfo, TryLow, TryHigh, CatchHigh, Handlers);440 441 LLVM_DEBUG(dbgs() << "TryLow[" << BB->getName() << "]: " << TryLow << '\n');442 LLVM_DEBUG(dbgs() << "TryHigh[" << BB->getName() << "]: " << TryHigh443 << '\n');444 LLVM_DEBUG(dbgs() << "CatchHigh[" << BB->getName() << "]: " << CatchHigh445 << '\n');446 } else {447 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);448 449 // It's possible for a cleanup to be visited twice: it might have multiple450 // cleanupret instructions.451 auto [It, Inserted] = FuncInfo.EHPadStateMap.try_emplace(CleanupPad);452 if (!Inserted)453 return;454 455 int CleanupState = addUnwindMapEntry(FuncInfo, ParentState, BB);456 It->second = CleanupState;457 LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "458 << BB->getName() << '\n');459 for (const BasicBlock *PredBlock : predecessors(BB)) {460 if ((PredBlock = getEHPadFromPredecessor(PredBlock,461 CleanupPad->getParentPad()))) {462 calculateCXXStateNumbers(FuncInfo, &*PredBlock->getFirstNonPHIIt(),463 CleanupState);464 }465 }466 for (const User *U : CleanupPad->users()) {467 const auto *UserI = cast<Instruction>(U);468 if (UserI->isEHPad())469 report_fatal_error("Cleanup funclets for the MSVC++ personality cannot "470 "contain exceptional actions");471 }472 }473}474 475static int addSEHExcept(WinEHFuncInfo &FuncInfo, int ParentState,476 const Function *Filter, const BasicBlock *Handler) {477 SEHUnwindMapEntry Entry;478 Entry.ToState = ParentState;479 Entry.IsFinally = false;480 Entry.Filter = Filter;481 Entry.Handler = Handler;482 FuncInfo.SEHUnwindMap.push_back(Entry);483 return FuncInfo.SEHUnwindMap.size() - 1;484}485 486static int addSEHFinally(WinEHFuncInfo &FuncInfo, int ParentState,487 const BasicBlock *Handler) {488 SEHUnwindMapEntry Entry;489 Entry.ToState = ParentState;490 Entry.IsFinally = true;491 Entry.Filter = nullptr;492 Entry.Handler = Handler;493 FuncInfo.SEHUnwindMap.push_back(Entry);494 return FuncInfo.SEHUnwindMap.size() - 1;495}496 497// Starting from a EHPad, Backward walk through control-flow graph498// to produce two primary outputs:499// FuncInfo.EHPadStateMap[] and FuncInfo.SEHUnwindMap[]500static void calculateSEHStateNumbers(WinEHFuncInfo &FuncInfo,501 const Instruction *FirstNonPHI,502 int ParentState) {503 const BasicBlock *BB = FirstNonPHI->getParent();504 assert(BB->isEHPad() && "no a funclet!");505 506 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(FirstNonPHI)) {507 assert(FuncInfo.EHPadStateMap.count(CatchSwitch) == 0 &&508 "shouldn't revist catch funclets!");509 510 // Extract the filter function and the __except basic block and create a511 // state for them.512 assert(CatchSwitch->getNumHandlers() == 1 &&513 "SEH doesn't have multiple handlers per __try");514 const auto *CatchPad =515 cast<CatchPadInst>((*CatchSwitch->handler_begin())->getFirstNonPHIIt());516 const BasicBlock *CatchPadBB = CatchPad->getParent();517 const Constant *FilterOrNull =518 cast<Constant>(CatchPad->getArgOperand(0)->stripPointerCasts());519 const Function *Filter = dyn_cast<Function>(FilterOrNull);520 assert((Filter || FilterOrNull->isNullValue()) &&521 "unexpected filter value");522 int TryState = addSEHExcept(FuncInfo, ParentState, Filter, CatchPadBB);523 524 // Everything in the __try block uses TryState as its parent state.525 FuncInfo.EHPadStateMap[CatchSwitch] = TryState;526 FuncInfo.EHPadStateMap[CatchPad] = TryState;527 LLVM_DEBUG(dbgs() << "Assigning state #" << TryState << " to BB "528 << CatchPadBB->getName() << '\n');529 for (const BasicBlock *PredBlock : predecessors(BB))530 if ((PredBlock = getEHPadFromPredecessor(PredBlock,531 CatchSwitch->getParentPad())))532 calculateSEHStateNumbers(FuncInfo, &*PredBlock->getFirstNonPHIIt(),533 TryState);534 535 // Everything in the __except block unwinds to ParentState, just like code536 // outside the __try.537 for (const User *U : CatchPad->users()) {538 const auto *UserI = cast<Instruction>(U);539 if (auto *InnerCatchSwitch = dyn_cast<CatchSwitchInst>(UserI)) {540 BasicBlock *UnwindDest = InnerCatchSwitch->getUnwindDest();541 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())542 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);543 }544 if (auto *InnerCleanupPad = dyn_cast<CleanupPadInst>(UserI)) {545 BasicBlock *UnwindDest = getCleanupRetUnwindDest(InnerCleanupPad);546 // If a nested cleanup pad reports a null unwind destination and the547 // enclosing catch pad doesn't it must be post-dominated by an548 // unreachable instruction.549 if (!UnwindDest || UnwindDest == CatchSwitch->getUnwindDest())550 calculateSEHStateNumbers(FuncInfo, UserI, ParentState);551 }552 }553 } else {554 auto *CleanupPad = cast<CleanupPadInst>(FirstNonPHI);555 556 // It's possible for a cleanup to be visited twice: it might have multiple557 // cleanupret instructions.558 auto [It, Inserted] = FuncInfo.EHPadStateMap.try_emplace(CleanupPad);559 if (!Inserted)560 return;561 562 int CleanupState = addSEHFinally(FuncInfo, ParentState, BB);563 It->second = CleanupState;564 LLVM_DEBUG(dbgs() << "Assigning state #" << CleanupState << " to BB "565 << BB->getName() << '\n');566 for (const BasicBlock *PredBlock : predecessors(BB))567 if ((PredBlock =568 getEHPadFromPredecessor(PredBlock, CleanupPad->getParentPad())))569 calculateSEHStateNumbers(FuncInfo, &*PredBlock->getFirstNonPHIIt(),570 CleanupState);571 for (const User *U : CleanupPad->users()) {572 const auto *UserI = cast<Instruction>(U);573 if (UserI->isEHPad())574 report_fatal_error("Cleanup funclets for the SEH personality cannot "575 "contain exceptional actions");576 }577 }578}579 580static bool isTopLevelPadForMSVC(const Instruction *EHPad) {581 if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(EHPad))582 return isa<ConstantTokenNone>(CatchSwitch->getParentPad()) &&583 CatchSwitch->unwindsToCaller();584 if (auto *CleanupPad = dyn_cast<CleanupPadInst>(EHPad))585 return isa<ConstantTokenNone>(CleanupPad->getParentPad()) &&586 getCleanupRetUnwindDest(CleanupPad) == nullptr;587 if (isa<CatchPadInst>(EHPad))588 return false;589 llvm_unreachable("unexpected EHPad!");590}591 592void llvm::calculateSEHStateNumbers(const Function *Fn,593 WinEHFuncInfo &FuncInfo) {594 // Don't compute state numbers twice.595 if (!FuncInfo.SEHUnwindMap.empty())596 return;597 598 for (const BasicBlock &BB : *Fn) {599 if (!BB.isEHPad())600 continue;601 const Instruction *FirstNonPHI = &*BB.getFirstNonPHIIt();602 if (!isTopLevelPadForMSVC(FirstNonPHI))603 continue;604 ::calculateSEHStateNumbers(FuncInfo, FirstNonPHI, -1);605 }606 607 calculateStateNumbersForInvokes(Fn, FuncInfo);608 609 bool IsEHa = Fn->getParent()->getModuleFlag("eh-asynch");610 if (IsEHa) {611 const BasicBlock *EntryBB = &(Fn->getEntryBlock());612 calculateSEHStateForAsynchEH(EntryBB, -1, FuncInfo);613 }614}615 616void llvm::calculateWinCXXEHStateNumbers(const Function *Fn,617 WinEHFuncInfo &FuncInfo) {618 // Return if it's already been done.619 if (!FuncInfo.EHPadStateMap.empty())620 return;621 622 for (const BasicBlock &BB : *Fn) {623 if (!BB.isEHPad())624 continue;625 const Instruction *FirstNonPHI = &*BB.getFirstNonPHIIt();626 if (!isTopLevelPadForMSVC(FirstNonPHI))627 continue;628 calculateCXXStateNumbers(FuncInfo, FirstNonPHI, -1);629 }630 631 calculateStateNumbersForInvokes(Fn, FuncInfo);632 633 bool IsEHa = Fn->getParent()->getModuleFlag("eh-asynch");634 if (IsEHa) {635 const BasicBlock *EntryBB = &(Fn->getEntryBlock());636 calculateCXXStateForAsynchEH(EntryBB, -1, FuncInfo);637 }638}639 640static int addClrEHHandler(WinEHFuncInfo &FuncInfo, int HandlerParentState,641 int TryParentState, ClrHandlerType HandlerType,642 uint32_t TypeToken, const BasicBlock *Handler) {643 ClrEHUnwindMapEntry Entry;644 Entry.HandlerParentState = HandlerParentState;645 Entry.TryParentState = TryParentState;646 Entry.Handler = Handler;647 Entry.HandlerType = HandlerType;648 Entry.TypeToken = TypeToken;649 FuncInfo.ClrEHUnwindMap.push_back(Entry);650 return FuncInfo.ClrEHUnwindMap.size() - 1;651}652 653void llvm::calculateClrEHStateNumbers(const Function *Fn,654 WinEHFuncInfo &FuncInfo) {655 // Return if it's already been done.656 if (!FuncInfo.EHPadStateMap.empty())657 return;658 659 // This numbering assigns one state number to each catchpad and cleanuppad.660 // It also computes two tree-like relations over states:661 // 1) Each state has a "HandlerParentState", which is the state of the next662 // outer handler enclosing this state's handler (same as nearest ancestor663 // per the ParentPad linkage on EH pads, but skipping over catchswitches).664 // 2) Each state has a "TryParentState", which:665 // a) for a catchpad that's not the last handler on its catchswitch, is666 // the state of the next catchpad on that catchswitch667 // b) for all other pads, is the state of the pad whose try region is the668 // next outer try region enclosing this state's try region. The "try669 // regions are not present as such in the IR, but will be inferred670 // based on the placement of invokes and pads which reach each other671 // by exceptional exits672 // Catchswitches do not get their own states, but each gets mapped to the673 // state of its first catchpad.674 675 // Step one: walk down from outermost to innermost funclets, assigning each676 // catchpad and cleanuppad a state number. Add an entry to the677 // ClrEHUnwindMap for each state, recording its HandlerParentState and678 // handler attributes. Record the TryParentState as well for each catchpad679 // that's not the last on its catchswitch, but initialize all other entries'680 // TryParentStates to a sentinel -1 value that the next pass will update.681 682 // Seed a worklist with pads that have no parent.683 SmallVector<std::pair<const Instruction *, int>, 8> Worklist;684 for (const BasicBlock &BB : *Fn) {685 const Instruction *FirstNonPHI = &*BB.getFirstNonPHIIt();686 const Value *ParentPad;687 if (const auto *CPI = dyn_cast<CleanupPadInst>(FirstNonPHI))688 ParentPad = CPI->getParentPad();689 else if (const auto *CSI = dyn_cast<CatchSwitchInst>(FirstNonPHI))690 ParentPad = CSI->getParentPad();691 else692 continue;693 if (isa<ConstantTokenNone>(ParentPad))694 Worklist.emplace_back(FirstNonPHI, -1);695 }696 697 // Use the worklist to visit all pads, from outer to inner. Record698 // HandlerParentState for all pads. Record TryParentState only for catchpads699 // that aren't the last on their catchswitch (setting all other entries'700 // TryParentStates to an initial value of -1). This loop is also responsible701 // for setting the EHPadStateMap entry for all catchpads, cleanuppads, and702 // catchswitches.703 while (!Worklist.empty()) {704 const Instruction *Pad;705 int HandlerParentState;706 std::tie(Pad, HandlerParentState) = Worklist.pop_back_val();707 708 if (const auto *Cleanup = dyn_cast<CleanupPadInst>(Pad)) {709 // Create the entry for this cleanup with the appropriate handler710 // properties. Finally and fault handlers are distinguished by arity.711 ClrHandlerType HandlerType =712 (Cleanup->arg_size() ? ClrHandlerType::Fault713 : ClrHandlerType::Finally);714 int CleanupState = addClrEHHandler(FuncInfo, HandlerParentState, -1,715 HandlerType, 0, Pad->getParent());716 // Queue any child EH pads on the worklist.717 for (const User *U : Cleanup->users())718 if (const auto *I = dyn_cast<Instruction>(U))719 if (I->isEHPad())720 Worklist.emplace_back(I, CleanupState);721 // Remember this pad's state.722 FuncInfo.EHPadStateMap[Cleanup] = CleanupState;723 } else {724 // Walk the handlers of this catchswitch in reverse order since all but725 // the last need to set the following one as its TryParentState.726 const auto *CatchSwitch = cast<CatchSwitchInst>(Pad);727 int CatchState = -1, FollowerState = -1;728 SmallVector<const BasicBlock *, 4> CatchBlocks(CatchSwitch->handlers());729 for (const BasicBlock *CatchBlock : llvm::reverse(CatchBlocks)) {730 // Create the entry for this catch with the appropriate handler731 // properties.732 const auto *Catch = cast<CatchPadInst>(CatchBlock->getFirstNonPHIIt());733 uint32_t TypeToken = static_cast<uint32_t>(734 cast<ConstantInt>(Catch->getArgOperand(0))->getZExtValue());735 CatchState =736 addClrEHHandler(FuncInfo, HandlerParentState, FollowerState,737 ClrHandlerType::Catch, TypeToken, CatchBlock);738 // Queue any child EH pads on the worklist.739 for (const User *U : Catch->users())740 if (const auto *I = dyn_cast<Instruction>(U))741 if (I->isEHPad())742 Worklist.emplace_back(I, CatchState);743 // Remember this catch's state.744 FuncInfo.EHPadStateMap[Catch] = CatchState;745 FollowerState = CatchState;746 }747 // Associate the catchswitch with the state of its first catch.748 assert(CatchSwitch->getNumHandlers());749 FuncInfo.EHPadStateMap[CatchSwitch] = CatchState;750 }751 }752 753 // Step two: record the TryParentState of each state. For cleanuppads that754 // don't have cleanuprets, we may need to infer this from their child pads,755 // so visit pads in descendant-most to ancestor-most order.756 for (ClrEHUnwindMapEntry &Entry : llvm::reverse(FuncInfo.ClrEHUnwindMap)) {757 const Instruction *Pad =758 &*cast<const BasicBlock *>(Entry.Handler)->getFirstNonPHIIt();759 // For most pads, the TryParentState is the state associated with the760 // unwind dest of exceptional exits from it.761 const BasicBlock *UnwindDest;762 if (const auto *Catch = dyn_cast<CatchPadInst>(Pad)) {763 // If a catch is not the last in its catchswitch, its TryParentState is764 // the state associated with the next catch in the switch, even though765 // that's not the unwind dest of exceptions escaping the catch. Those766 // cases were already assigned a TryParentState in the first pass, so767 // skip them.768 if (Entry.TryParentState != -1)769 continue;770 // Otherwise, get the unwind dest from the catchswitch.771 UnwindDest = Catch->getCatchSwitch()->getUnwindDest();772 } else {773 const auto *Cleanup = cast<CleanupPadInst>(Pad);774 UnwindDest = nullptr;775 for (const User *U : Cleanup->users()) {776 if (auto *CleanupRet = dyn_cast<CleanupReturnInst>(U)) {777 // Common and unambiguous case -- cleanupret indicates cleanup's778 // unwind dest.779 UnwindDest = CleanupRet->getUnwindDest();780 break;781 }782 783 // Get an unwind dest for the user784 const BasicBlock *UserUnwindDest = nullptr;785 if (auto *Invoke = dyn_cast<InvokeInst>(U)) {786 UserUnwindDest = Invoke->getUnwindDest();787 } else if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(U)) {788 UserUnwindDest = CatchSwitch->getUnwindDest();789 } else if (auto *ChildCleanup = dyn_cast<CleanupPadInst>(U)) {790 int UserState = FuncInfo.EHPadStateMap[ChildCleanup];791 int UserUnwindState =792 FuncInfo.ClrEHUnwindMap[UserState].TryParentState;793 if (UserUnwindState != -1)794 UserUnwindDest = cast<const BasicBlock *>(795 FuncInfo.ClrEHUnwindMap[UserUnwindState].Handler);796 }797 798 // Not having an unwind dest for this user might indicate that it799 // doesn't unwind, so can't be taken as proof that the cleanup itself800 // may unwind to caller (see e.g. SimplifyUnreachable and801 // RemoveUnwindEdge).802 if (!UserUnwindDest)803 continue;804 805 // Now we have an unwind dest for the user, but we need to see if it806 // unwinds all the way out of the cleanup or if it stays within it.807 const Instruction *UserUnwindPad = &*UserUnwindDest->getFirstNonPHIIt();808 const Value *UserUnwindParent;809 if (auto *CSI = dyn_cast<CatchSwitchInst>(UserUnwindPad))810 UserUnwindParent = CSI->getParentPad();811 else812 UserUnwindParent =813 cast<CleanupPadInst>(UserUnwindPad)->getParentPad();814 815 // The unwind stays within the cleanup iff it targets a child of the816 // cleanup.817 if (UserUnwindParent == Cleanup)818 continue;819 820 // This unwind exits the cleanup, so its dest is the cleanup's dest.821 UnwindDest = UserUnwindDest;822 break;823 }824 }825 826 // Record the state of the unwind dest as the TryParentState.827 int UnwindDestState;828 829 // If UnwindDest is null at this point, either the pad in question can830 // be exited by unwind to caller, or it cannot be exited by unwind. In831 // either case, reporting such cases as unwinding to caller is correct.832 // This can lead to EH tables that "look strange" -- if this pad's is in833 // a parent funclet which has other children that do unwind to an enclosing834 // pad, the try region for this pad will be missing the "duplicate" EH835 // clause entries that you'd expect to see covering the whole parent. That836 // should be benign, since the unwind never actually happens. If it were837 // an issue, we could add a subsequent pass that pushes unwind dests down838 // from parents that have them to children that appear to unwind to caller.839 if (!UnwindDest) {840 UnwindDestState = -1;841 } else {842 UnwindDestState =843 FuncInfo.EHPadStateMap[&*UnwindDest->getFirstNonPHIIt()];844 }845 846 Entry.TryParentState = UnwindDestState;847 }848 849 // Step three: transfer information from pads to invokes.850 calculateStateNumbersForInvokes(Fn, FuncInfo);851}852 853void WinEHPrepareImpl::colorFunclets(Function &F) {854 BlockColors = colorEHFunclets(F);855 856 // Invert the map from BB to colors to color to BBs.857 for (BasicBlock &BB : F) {858 ColorVector &Colors = BlockColors[&BB];859 for (BasicBlock *Color : Colors)860 FuncletBlocks[Color].push_back(&BB);861 }862}863 864bool WinEHPrepareImpl::demotePHIsOnFunclets(Function &F,865 bool DemoteCatchSwitchPHIOnly) {866 bool Changed = false;867 868 // Strip PHI nodes off of EH pads.869 SmallVector<PHINode *, 16> PHINodes;870 for (BasicBlock &BB : make_early_inc_range(F)) {871 if (!BB.isEHPad())872 continue;873 874 for (Instruction &I : make_early_inc_range(BB)) {875 auto *PN = dyn_cast<PHINode>(&I);876 // Stop at the first non-PHI.877 if (!PN)878 break;879 880 // If DemoteCatchSwitchPHIOnly is true, we only demote a PHI when881 // 1. The PHI is within a catchswitch BB882 // 2. The PHI has a catchswitch BB has one of its incoming blocks883 if (DemoteCatchSwitchPHIOnly) {884 bool IsCatchSwitchBB = isa<CatchSwitchInst>(BB.getFirstNonPHIIt());885 bool HasIncomingCatchSwitchBB = false;886 for (unsigned I = 0, E = PN->getNumIncomingValues(); I < E; ++I) {887 if (isa<CatchSwitchInst>(888 PN->getIncomingBlock(I)->getFirstNonPHIIt())) {889 HasIncomingCatchSwitchBB = true;890 break;891 }892 }893 if (!IsCatchSwitchBB && !HasIncomingCatchSwitchBB)894 break;895 }896 897 Changed = true;898 899 AllocaInst *SpillSlot = insertPHILoads(PN, F);900 if (SpillSlot)901 insertPHIStores(PN, SpillSlot);902 903 PHINodes.push_back(PN);904 }905 }906 907 for (auto *PN : PHINodes) {908 // There may be lingering uses on other EH PHIs being removed909 PN->replaceAllUsesWith(PoisonValue::get(PN->getType()));910 PN->eraseFromParent();911 }912 913 return Changed;914}915 916bool WinEHPrepareImpl::cloneCommonBlocks(Function &F) {917 bool Changed = false;918 919 // We need to clone all blocks which belong to multiple funclets. Values are920 // remapped throughout the funclet to propagate both the new instructions921 // *and* the new basic blocks themselves.922 for (auto &Funclets : FuncletBlocks) {923 BasicBlock *FuncletPadBB = Funclets.first;924 std::vector<BasicBlock *> &BlocksInFunclet = Funclets.second;925 Value *FuncletToken;926 if (FuncletPadBB == &F.getEntryBlock())927 FuncletToken = ConstantTokenNone::get(F.getContext());928 else929 FuncletToken = &*FuncletPadBB->getFirstNonPHIIt();930 931 std::vector<std::pair<BasicBlock *, BasicBlock *>> Orig2Clone;932 ValueToValueMapTy VMap;933 for (BasicBlock *BB : BlocksInFunclet) {934 ColorVector &ColorsForBB = BlockColors[BB];935 // We don't need to do anything if the block is monochromatic.936 size_t NumColorsForBB = ColorsForBB.size();937 if (NumColorsForBB == 1)938 continue;939 940 DEBUG_WITH_TYPE("win-eh-prepare-coloring",941 dbgs() << " Cloning block \'" << BB->getName()942 << "\' for funclet \'" << FuncletPadBB->getName()943 << "\'.\n");944 945 // Create a new basic block and copy instructions into it!946 BasicBlock *CBB =947 CloneBasicBlock(BB, VMap, Twine(".for.", FuncletPadBB->getName()));948 // Insert the clone immediately after the original to ensure determinism949 // and to keep the same relative ordering of any funclet's blocks.950 CBB->insertInto(&F, BB->getNextNode());951 952 // Add basic block mapping.953 VMap[BB] = CBB;954 955 // Record delta operations that we need to perform to our color mappings.956 Orig2Clone.emplace_back(BB, CBB);957 }958 959 // If nothing was cloned, we're done cloning in this funclet.960 if (Orig2Clone.empty())961 continue;962 963 Changed = true;964 965 // Update our color mappings to reflect that one block has lost a color and966 // another has gained a color.967 for (auto &BBMapping : Orig2Clone) {968 BasicBlock *OldBlock = BBMapping.first;969 BasicBlock *NewBlock = BBMapping.second;970 971 BlocksInFunclet.push_back(NewBlock);972 ColorVector &NewColors = BlockColors[NewBlock];973 assert(NewColors.empty() && "A new block should only have one color!");974 NewColors.push_back(FuncletPadBB);975 976 DEBUG_WITH_TYPE("win-eh-prepare-coloring",977 dbgs() << " Assigned color \'" << FuncletPadBB->getName()978 << "\' to block \'" << NewBlock->getName()979 << "\'.\n");980 981 llvm::erase(BlocksInFunclet, OldBlock);982 ColorVector &OldColors = BlockColors[OldBlock];983 llvm::erase(OldColors, FuncletPadBB);984 985 DEBUG_WITH_TYPE("win-eh-prepare-coloring",986 dbgs() << " Removed color \'" << FuncletPadBB->getName()987 << "\' from block \'" << OldBlock->getName()988 << "\'.\n");989 }990 991 // Loop over all of the instructions in this funclet, fixing up operand992 // references as we go. This uses VMap to do all the hard work.993 for (BasicBlock *BB : BlocksInFunclet)994 // Loop over all instructions, fixing each one as we find it...995 for (Instruction &I : *BB)996 RemapInstruction(&I, VMap,997 RF_IgnoreMissingLocals | RF_NoModuleLevelChanges);998 999 // Catchrets targeting cloned blocks need to be updated separately from1000 // the loop above because they are not in the current funclet.1001 SmallVector<CatchReturnInst *, 2> FixupCatchrets;1002 for (auto &BBMapping : Orig2Clone) {1003 BasicBlock *OldBlock = BBMapping.first;1004 BasicBlock *NewBlock = BBMapping.second;1005 1006 FixupCatchrets.clear();1007 for (BasicBlock *Pred : predecessors(OldBlock))1008 if (auto *CatchRet = dyn_cast<CatchReturnInst>(Pred->getTerminator()))1009 if (CatchRet->getCatchSwitchParentPad() == FuncletToken)1010 FixupCatchrets.push_back(CatchRet);1011 1012 for (CatchReturnInst *CatchRet : FixupCatchrets)1013 CatchRet->setSuccessor(NewBlock);1014 }1015 1016 auto UpdatePHIOnClonedBlock = [&](PHINode *PN, bool IsForOldBlock) {1017 unsigned NumPreds = PN->getNumIncomingValues();1018 for (unsigned PredIdx = 0, PredEnd = NumPreds; PredIdx != PredEnd;1019 ++PredIdx) {1020 BasicBlock *IncomingBlock = PN->getIncomingBlock(PredIdx);1021 bool EdgeTargetsFunclet;1022 if (auto *CRI =1023 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {1024 EdgeTargetsFunclet = (CRI->getCatchSwitchParentPad() == FuncletToken);1025 } else {1026 ColorVector &IncomingColors = BlockColors[IncomingBlock];1027 assert(!IncomingColors.empty() && "Block not colored!");1028 assert((IncomingColors.size() == 1 ||1029 !llvm::is_contained(IncomingColors, FuncletPadBB)) &&1030 "Cloning should leave this funclet's blocks monochromatic");1031 EdgeTargetsFunclet = (IncomingColors.front() == FuncletPadBB);1032 }1033 if (IsForOldBlock != EdgeTargetsFunclet)1034 continue;1035 PN->removeIncomingValue(IncomingBlock, /*DeletePHIIfEmpty=*/false);1036 // Revisit the next entry.1037 --PredIdx;1038 --PredEnd;1039 }1040 };1041 1042 for (auto &BBMapping : Orig2Clone) {1043 BasicBlock *OldBlock = BBMapping.first;1044 BasicBlock *NewBlock = BBMapping.second;1045 for (PHINode &OldPN : OldBlock->phis()) {1046 UpdatePHIOnClonedBlock(&OldPN, /*IsForOldBlock=*/true);1047 }1048 for (PHINode &NewPN : NewBlock->phis()) {1049 UpdatePHIOnClonedBlock(&NewPN, /*IsForOldBlock=*/false);1050 }1051 }1052 1053 // Check to see if SuccBB has PHI nodes. If so, we need to add entries to1054 // the PHI nodes for NewBB now.1055 for (auto &BBMapping : Orig2Clone) {1056 BasicBlock *OldBlock = BBMapping.first;1057 BasicBlock *NewBlock = BBMapping.second;1058 for (BasicBlock *SuccBB : successors(NewBlock)) {1059 for (PHINode &SuccPN : SuccBB->phis()) {1060 // Ok, we have a PHI node. Figure out what the incoming value was for1061 // the OldBlock.1062 int OldBlockIdx = SuccPN.getBasicBlockIndex(OldBlock);1063 if (OldBlockIdx == -1)1064 break;1065 Value *IV = SuccPN.getIncomingValue(OldBlockIdx);1066 1067 // Remap the value if necessary.1068 if (auto *Inst = dyn_cast<Instruction>(IV)) {1069 ValueToValueMapTy::iterator I = VMap.find(Inst);1070 if (I != VMap.end())1071 IV = I->second;1072 }1073 1074 SuccPN.addIncoming(IV, NewBlock);1075 }1076 }1077 }1078 1079 for (ValueToValueMapTy::value_type VT : VMap) {1080 // If there were values defined in BB that are used outside the funclet,1081 // then we now have to update all uses of the value to use either the1082 // original value, the cloned value, or some PHI derived value. This can1083 // require arbitrary PHI insertion, of which we are prepared to do, clean1084 // these up now.1085 SmallVector<Use *, 16> UsesToRename;1086 1087 auto *OldI = dyn_cast<Instruction>(const_cast<Value *>(VT.first));1088 if (!OldI)1089 continue;1090 auto *NewI = cast<Instruction>(VT.second);1091 // Scan all uses of this instruction to see if it is used outside of its1092 // funclet, and if so, record them in UsesToRename.1093 for (Use &U : OldI->uses()) {1094 Instruction *UserI = cast<Instruction>(U.getUser());1095 BasicBlock *UserBB = UserI->getParent();1096 ColorVector &ColorsForUserBB = BlockColors[UserBB];1097 assert(!ColorsForUserBB.empty());1098 if (ColorsForUserBB.size() > 1 ||1099 *ColorsForUserBB.begin() != FuncletPadBB)1100 UsesToRename.push_back(&U);1101 }1102 1103 // If there are no uses outside the block, we're done with this1104 // instruction.1105 if (UsesToRename.empty())1106 continue;1107 1108 // We found a use of OldI outside of the funclet. Rename all uses of OldI1109 // that are outside its funclet to be uses of the appropriate PHI node1110 // etc.1111 SSAUpdater SSAUpdate;1112 SSAUpdate.Initialize(OldI->getType(), OldI->getName());1113 SSAUpdate.AddAvailableValue(OldI->getParent(), OldI);1114 SSAUpdate.AddAvailableValue(NewI->getParent(), NewI);1115 1116 while (!UsesToRename.empty())1117 SSAUpdate.RewriteUseAfterInsertions(*UsesToRename.pop_back_val());1118 }1119 }1120 1121 return Changed;1122}1123 1124bool WinEHPrepareImpl::removeImplausibleInstructions(Function &F) {1125 bool Changed = false;1126 1127 // Remove implausible terminators and replace them with UnreachableInst.1128 for (auto &Funclet : FuncletBlocks) {1129 BasicBlock *FuncletPadBB = Funclet.first;1130 std::vector<BasicBlock *> &BlocksInFunclet = Funclet.second;1131 Instruction *FirstNonPHI = &*FuncletPadBB->getFirstNonPHIIt();1132 auto *FuncletPad = dyn_cast<FuncletPadInst>(FirstNonPHI);1133 auto *CatchPad = dyn_cast_or_null<CatchPadInst>(FuncletPad);1134 auto *CleanupPad = dyn_cast_or_null<CleanupPadInst>(FuncletPad);1135 1136 for (BasicBlock *BB : BlocksInFunclet) {1137 for (Instruction &I : *BB) {1138 auto *CB = dyn_cast<CallBase>(&I);1139 if (!CB)1140 continue;1141 1142 Value *FuncletBundleOperand = nullptr;1143 if (auto BU = CB->getOperandBundle(LLVMContext::OB_funclet))1144 FuncletBundleOperand = BU->Inputs.front();1145 1146 if (FuncletBundleOperand == FuncletPad)1147 continue;1148 1149 // Skip call sites which are nounwind intrinsics or inline asm.1150 auto *CalledFn =1151 dyn_cast<Function>(CB->getCalledOperand()->stripPointerCasts());1152 if (CB->isInlineAsm() ||1153 (CalledFn && CalledFn->isIntrinsic() && CB->doesNotThrow()))1154 continue;1155 1156 Changed = true;1157 1158 // This call site was not part of this funclet, remove it.1159 if (isa<InvokeInst>(CB)) {1160 // Remove the unwind edge if it was an invoke.1161 removeUnwindEdge(BB);1162 // Get a pointer to the new call.1163 BasicBlock::iterator CallI =1164 std::prev(BB->getTerminator()->getIterator());1165 auto *CI = cast<CallInst>(&*CallI);1166 changeToUnreachable(CI);1167 } else {1168 changeToUnreachable(&I);1169 }1170 1171 // There are no more instructions in the block (except for unreachable),1172 // we are done.1173 break;1174 }1175 1176 Instruction *TI = BB->getTerminator();1177 // CatchPadInst and CleanupPadInst can't transfer control to a ReturnInst.1178 bool IsUnreachableRet = isa<ReturnInst>(TI) && FuncletPad;1179 // The token consumed by a CatchReturnInst must match the funclet token.1180 bool IsUnreachableCatchret = false;1181 if (auto *CRI = dyn_cast<CatchReturnInst>(TI))1182 IsUnreachableCatchret = CRI->getCatchPad() != CatchPad;1183 // The token consumed by a CleanupReturnInst must match the funclet token.1184 bool IsUnreachableCleanupret = false;1185 if (auto *CRI = dyn_cast<CleanupReturnInst>(TI))1186 IsUnreachableCleanupret = CRI->getCleanupPad() != CleanupPad;1187 if (IsUnreachableRet || IsUnreachableCatchret ||1188 IsUnreachableCleanupret) {1189 Changed = true;1190 changeToUnreachable(TI);1191 } else if (isa<InvokeInst>(TI)) {1192 if (Personality == EHPersonality::MSVC_CXX && CleanupPad) {1193 Changed = true;1194 // Invokes within a cleanuppad for the MSVC++ personality never1195 // transfer control to their unwind edge: the personality will1196 // terminate the program.1197 removeUnwindEdge(BB);1198 }1199 }1200 }1201 }1202 1203 return Changed;1204}1205 1206bool WinEHPrepareImpl::cleanupPreparedFunclets(Function &F) {1207 bool Changed = false;1208 1209 // Clean-up some of the mess we made by removing useles PHI nodes, trivial1210 // branches, etc.1211 for (BasicBlock &BB : llvm::make_early_inc_range(F)) {1212 Changed |= SimplifyInstructionsInBlock(&BB);1213 Changed |= ConstantFoldTerminator(&BB, /*DeleteDeadConditions=*/true);1214 Changed |= MergeBlockIntoPredecessor(&BB);1215 }1216 1217 // We might have some unreachable blocks after cleaning up some impossible1218 // control flow.1219 Changed |= removeUnreachableBlocks(F);1220 1221 return Changed;1222}1223 1224#ifndef NDEBUG1225void WinEHPrepareImpl::verifyPreparedFunclets(Function &F) {1226 for (BasicBlock &BB : F) {1227 size_t NumColors = BlockColors[&BB].size();1228 assert(NumColors == 1 && "Expected monochromatic BB!");1229 if (NumColors == 0)1230 report_fatal_error("Uncolored BB!");1231 if (NumColors > 1)1232 report_fatal_error("Multicolor BB!");1233 assert((DisableDemotion || !(BB.isEHPad() && isa<PHINode>(BB.begin()))) &&1234 "EH Pad still has a PHI!");1235 }1236}1237#endif1238 1239bool WinEHPrepareImpl::prepareExplicitEH(Function &F) {1240 // Remove unreachable blocks. It is not valuable to assign them a color and1241 // their existence can trick us into thinking values are alive when they are1242 // not.1243 bool Changed = removeUnreachableBlocks(F);1244 1245 // Determine which blocks are reachable from which funclet entries.1246 colorFunclets(F);1247 1248 Changed |= cloneCommonBlocks(F);1249 1250 if (!DisableDemotion)1251 Changed |= demotePHIsOnFunclets(F, DemoteCatchSwitchPHIOnly ||1252 DemoteCatchSwitchPHIOnlyOpt);1253 1254 if (!DisableCleanups) {1255 assert(!verifyFunction(F, &dbgs()));1256 Changed |= removeImplausibleInstructions(F);1257 1258 assert(!verifyFunction(F, &dbgs()));1259 Changed |= cleanupPreparedFunclets(F);1260 }1261 1262 LLVM_DEBUG(verifyPreparedFunclets(F));1263 // Recolor the CFG to verify that all is well.1264 LLVM_DEBUG(colorFunclets(F));1265 LLVM_DEBUG(verifyPreparedFunclets(F));1266 1267 return Changed;1268}1269 1270// TODO: Share loads when one use dominates another, or when a catchpad exit1271// dominates uses (needs dominators).1272AllocaInst *WinEHPrepareImpl::insertPHILoads(PHINode *PN, Function &F) {1273 BasicBlock *PHIBlock = PN->getParent();1274 AllocaInst *SpillSlot = nullptr;1275 Instruction *EHPad = &*PHIBlock->getFirstNonPHIIt();1276 1277 if (!EHPad->isTerminator()) {1278 // If the EHPad isn't a terminator, then we can insert a load in this block1279 // that will dominate all uses.1280 SpillSlot = new AllocaInst(PN->getType(), DL->getAllocaAddrSpace(), nullptr,1281 Twine(PN->getName(), ".wineh.spillslot"),1282 F.getEntryBlock().begin());1283 Value *V = new LoadInst(PN->getType(), SpillSlot,1284 Twine(PN->getName(), ".wineh.reload"),1285 PHIBlock->getFirstInsertionPt());1286 PN->replaceAllUsesWith(V);1287 return SpillSlot;1288 }1289 1290 // Otherwise, we have a PHI on a terminator EHPad, and we give up and insert1291 // loads of the slot before every use.1292 DenseMap<BasicBlock *, Value *> Loads;1293 for (Use &U : llvm::make_early_inc_range(PN->uses())) {1294 auto *UsingInst = cast<Instruction>(U.getUser());1295 if (isa<PHINode>(UsingInst) && UsingInst->getParent()->isEHPad()) {1296 // Use is on an EH pad phi. Leave it alone; we'll insert loads and1297 // stores for it separately.1298 continue;1299 }1300 replaceUseWithLoad(PN, U, SpillSlot, Loads, F);1301 }1302 return SpillSlot;1303}1304 1305// TODO: improve store placement. Inserting at def is probably good, but need1306// to be careful not to introduce interfering stores (needs liveness analysis).1307// TODO: identify related phi nodes that can share spill slots, and share them1308// (also needs liveness).1309void WinEHPrepareImpl::insertPHIStores(PHINode *OriginalPHI,1310 AllocaInst *SpillSlot) {1311 // Use a worklist of (Block, Value) pairs -- the given Value needs to be1312 // stored to the spill slot by the end of the given Block.1313 SmallVector<std::pair<BasicBlock *, Value *>, 4> Worklist;1314 1315 Worklist.push_back({OriginalPHI->getParent(), OriginalPHI});1316 1317 while (!Worklist.empty()) {1318 BasicBlock *EHBlock;1319 Value *InVal;1320 std::tie(EHBlock, InVal) = Worklist.pop_back_val();1321 1322 PHINode *PN = dyn_cast<PHINode>(InVal);1323 if (PN && PN->getParent() == EHBlock) {1324 // The value is defined by another PHI we need to remove, with no room to1325 // insert a store after the PHI, so each predecessor needs to store its1326 // incoming value.1327 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {1328 Value *PredVal = PN->getIncomingValue(i);1329 1330 // Undef can safely be skipped.1331 if (isa<UndefValue>(PredVal))1332 continue;1333 1334 insertPHIStore(PN->getIncomingBlock(i), PredVal, SpillSlot, Worklist);1335 }1336 } else {1337 // We need to store InVal, which dominates EHBlock, but can't put a store1338 // in EHBlock, so need to put stores in each predecessor.1339 for (BasicBlock *PredBlock : predecessors(EHBlock)) {1340 insertPHIStore(PredBlock, InVal, SpillSlot, Worklist);1341 }1342 }1343 }1344}1345 1346void WinEHPrepareImpl::insertPHIStore(1347 BasicBlock *PredBlock, Value *PredVal, AllocaInst *SpillSlot,1348 SmallVectorImpl<std::pair<BasicBlock *, Value *>> &Worklist) {1349 1350 if (PredBlock->isEHPad() && PredBlock->getFirstNonPHIIt()->isTerminator()) {1351 // Pred is unsplittable, so we need to queue it on the worklist.1352 Worklist.push_back({PredBlock, PredVal});1353 return;1354 }1355 1356 // Otherwise, insert the store at the end of the basic block.1357 new StoreInst(PredVal, SpillSlot, PredBlock->getTerminator()->getIterator());1358}1359 1360void WinEHPrepareImpl::replaceUseWithLoad(1361 Value *V, Use &U, AllocaInst *&SpillSlot,1362 DenseMap<BasicBlock *, Value *> &Loads, Function &F) {1363 // Lazilly create the spill slot.1364 if (!SpillSlot)1365 SpillSlot = new AllocaInst(V->getType(), DL->getAllocaAddrSpace(), nullptr,1366 Twine(V->getName(), ".wineh.spillslot"),1367 F.getEntryBlock().begin());1368 1369 auto *UsingInst = cast<Instruction>(U.getUser());1370 if (auto *UsingPHI = dyn_cast<PHINode>(UsingInst)) {1371 // If this is a PHI node, we can't insert a load of the value before1372 // the use. Instead insert the load in the predecessor block1373 // corresponding to the incoming value.1374 //1375 // Note that if there are multiple edges from a basic block to this1376 // PHI node that we cannot have multiple loads. The problem is that1377 // the resulting PHI node will have multiple values (from each load)1378 // coming in from the same block, which is illegal SSA form.1379 // For this reason, we keep track of and reuse loads we insert.1380 BasicBlock *IncomingBlock = UsingPHI->getIncomingBlock(U);1381 if (auto *CatchRet =1382 dyn_cast<CatchReturnInst>(IncomingBlock->getTerminator())) {1383 // Putting a load above a catchret and use on the phi would still leave1384 // a cross-funclet def/use. We need to split the edge, change the1385 // catchret to target the new block, and put the load there.1386 BasicBlock *PHIBlock = UsingInst->getParent();1387 BasicBlock *NewBlock = SplitEdge(IncomingBlock, PHIBlock);1388 // SplitEdge gives us:1389 // IncomingBlock:1390 // ...1391 // br label %NewBlock1392 // NewBlock:1393 // catchret label %PHIBlock1394 // But we need:1395 // IncomingBlock:1396 // ...1397 // catchret label %NewBlock1398 // NewBlock:1399 // br label %PHIBlock1400 // So move the terminators to each others' blocks and swap their1401 // successors.1402 BranchInst *Goto = cast<BranchInst>(IncomingBlock->getTerminator());1403 Goto->removeFromParent();1404 CatchRet->removeFromParent();1405 CatchRet->insertInto(IncomingBlock, IncomingBlock->end());1406 Goto->insertInto(NewBlock, NewBlock->end());1407 Goto->setSuccessor(0, PHIBlock);1408 CatchRet->setSuccessor(NewBlock);1409 // Update the color mapping for the newly split edge.1410 // Grab a reference to the ColorVector to be inserted before getting the1411 // reference to the vector we are copying because inserting the new1412 // element in BlockColors might cause the map to be reallocated.1413 ColorVector &ColorsForNewBlock = BlockColors[NewBlock];1414 ColorVector &ColorsForPHIBlock = BlockColors[PHIBlock];1415 ColorsForNewBlock = ColorsForPHIBlock;1416 for (BasicBlock *FuncletPad : ColorsForPHIBlock)1417 FuncletBlocks[FuncletPad].push_back(NewBlock);1418 // Treat the new block as incoming for load insertion.1419 IncomingBlock = NewBlock;1420 }1421 Value *&Load = Loads[IncomingBlock];1422 // Insert the load into the predecessor block1423 if (!Load)1424 Load = new LoadInst(1425 V->getType(), SpillSlot, Twine(V->getName(), ".wineh.reload"),1426 /*isVolatile=*/false, IncomingBlock->getTerminator()->getIterator());1427 1428 U.set(Load);1429 } else {1430 // Reload right before the old use.1431 auto *Load = new LoadInst(V->getType(), SpillSlot,1432 Twine(V->getName(), ".wineh.reload"),1433 /*isVolatile=*/false, UsingInst->getIterator());1434 U.set(Load);1435 }1436}1437 1438void WinEHFuncInfo::addIPToStateRange(const InvokeInst *II,1439 MCSymbol *InvokeBegin,1440 MCSymbol *InvokeEnd) {1441 assert(InvokeStateMap.count(II) &&1442 "should get invoke with precomputed state");1443 LabelToStateMap[InvokeBegin] = std::make_pair(InvokeStateMap[II], InvokeEnd);1444}1445 1446void WinEHFuncInfo::addIPToStateRange(int State, MCSymbol* InvokeBegin,1447 MCSymbol* InvokeEnd) {1448 LabelToStateMap[InvokeBegin] = std::make_pair(State, InvokeEnd);1449}1450 1451WinEHFuncInfo::WinEHFuncInfo() = default;1452