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