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