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