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