1 //===- SjLjEHPrepare.cpp - Eliminate Invoke & Unwind instructions ---------===// 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 transformation is designed for use by code generators which use SjLj 11 // based exception handling. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/CodeGen/Passes.h" 16 #include "llvm/ADT/DenseMap.h" 17 #include "llvm/ADT/SetVector.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/IR/Constants.h" 22 #include "llvm/IR/DataLayout.h" 23 #include "llvm/IR/DerivedTypes.h" 24 #include "llvm/IR/IRBuilder.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/Intrinsics.h" 27 #include "llvm/IR/LLVMContext.h" 28 #include "llvm/IR/Module.h" 29 #include "llvm/Pass.h" 30 #include "llvm/Support/CommandLine.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include "llvm/Target/TargetLowering.h" 34 #include "llvm/Target/TargetSubtargetInfo.h" 35 #include "llvm/Transforms/Scalar.h" 36 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 37 #include "llvm/Transforms/Utils/Local.h" 38 #include <set> 39 using namespace llvm; 40 41 #define DEBUG_TYPE "sjljehprepare" 42 43 STATISTIC(NumInvokes, "Number of invokes replaced"); 44 STATISTIC(NumSpilled, "Number of registers live across unwind edges"); 45 46 namespace { 47 class SjLjEHPrepare : public FunctionPass { 48 Type *doubleUnderDataTy; 49 Type *doubleUnderJBufTy; 50 Type *FunctionContextTy; 51 Constant *RegisterFn; 52 Constant *UnregisterFn; 53 Constant *BuiltinSetupDispatchFn; 54 Constant *FrameAddrFn; 55 Constant *StackAddrFn; 56 Constant *StackRestoreFn; 57 Constant *LSDAAddrFn; 58 Value *PersonalityFn; 59 Constant *CallSiteFn; 60 Constant *FuncCtxFn; 61 AllocaInst *FuncCtx; 62 63 public: 64 static char ID; // Pass identification, replacement for typeid 65 explicit SjLjEHPrepare() : FunctionPass(ID) {} 66 bool doInitialization(Module &M) override; 67 bool runOnFunction(Function &F) override; 68 69 void getAnalysisUsage(AnalysisUsage &AU) const override {} 70 const char *getPassName() const override { 71 return "SJLJ Exception Handling preparation"; 72 } 73 74 private: 75 bool setupEntryBlockAndCallSites(Function &F); 76 void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, Value *SelVal); 77 Value *setupFunctionContext(Function &F, ArrayRef<LandingPadInst *> LPads); 78 void lowerIncomingArguments(Function &F); 79 void lowerAcrossUnwindEdges(Function &F, ArrayRef<InvokeInst *> Invokes); 80 void insertCallSiteStore(Instruction *I, int Number); 81 }; 82 } // end anonymous namespace 83 84 char SjLjEHPrepare::ID = 0; 85 INITIALIZE_PASS(SjLjEHPrepare, "sjljehprepare", "Prepare SjLj exceptions", 86 false, false) 87 88 // Public Interface To the SjLjEHPrepare pass. 89 FunctionPass *llvm::createSjLjEHPreparePass() { return new SjLjEHPrepare(); } 90 // doInitialization - Set up decalarations and types needed to process 91 // exceptions. 92 bool SjLjEHPrepare::doInitialization(Module &M) { 93 // Build the function context structure. 94 // builtin_setjmp uses a five word jbuf 95 Type *VoidPtrTy = Type::getInt8PtrTy(M.getContext()); 96 Type *Int32Ty = Type::getInt32Ty(M.getContext()); 97 doubleUnderDataTy = ArrayType::get(Int32Ty, 4); 98 doubleUnderJBufTy = ArrayType::get(VoidPtrTy, 5); 99 FunctionContextTy = StructType::get(VoidPtrTy, // __prev 100 Int32Ty, // call_site 101 doubleUnderDataTy, // __data 102 VoidPtrTy, // __personality 103 VoidPtrTy, // __lsda 104 doubleUnderJBufTy, // __jbuf 105 nullptr); 106 RegisterFn = M.getOrInsertFunction( 107 "_Unwind_SjLj_Register", Type::getVoidTy(M.getContext()), 108 PointerType::getUnqual(FunctionContextTy), (Type *)nullptr); 109 UnregisterFn = M.getOrInsertFunction( 110 "_Unwind_SjLj_Unregister", Type::getVoidTy(M.getContext()), 111 PointerType::getUnqual(FunctionContextTy), (Type *)nullptr); 112 FrameAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::frameaddress); 113 StackAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::stacksave); 114 StackRestoreFn = Intrinsic::getDeclaration(&M, Intrinsic::stackrestore); 115 BuiltinSetupDispatchFn = 116 Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_setup_dispatch); 117 LSDAAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_lsda); 118 CallSiteFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_callsite); 119 FuncCtxFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_functioncontext); 120 PersonalityFn = nullptr; 121 122 return true; 123 } 124 125 /// insertCallSiteStore - Insert a store of the call-site value to the 126 /// function context 127 void SjLjEHPrepare::insertCallSiteStore(Instruction *I, int Number) { 128 IRBuilder<> Builder(I); 129 130 // Get a reference to the call_site field. 131 Type *Int32Ty = Type::getInt32Ty(I->getContext()); 132 Value *Zero = ConstantInt::get(Int32Ty, 0); 133 Value *One = ConstantInt::get(Int32Ty, 1); 134 Value *Idxs[2] = { Zero, One }; 135 Value *CallSite = 136 Builder.CreateGEP(FunctionContextTy, FuncCtx, Idxs, "call_site"); 137 138 // Insert a store of the call-site number 139 ConstantInt *CallSiteNoC = 140 ConstantInt::get(Type::getInt32Ty(I->getContext()), Number); 141 Builder.CreateStore(CallSiteNoC, CallSite, true /*volatile*/); 142 } 143 144 /// MarkBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until 145 /// we reach blocks we've already seen. 146 static void MarkBlocksLiveIn(BasicBlock *BB, 147 SmallPtrSetImpl<BasicBlock *> &LiveBBs) { 148 if (!LiveBBs.insert(BB).second) 149 return; // already been here. 150 151 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 152 MarkBlocksLiveIn(*PI, LiveBBs); 153 } 154 155 /// substituteLPadValues - Substitute the values returned by the landingpad 156 /// instruction with those returned by the personality function. 157 void SjLjEHPrepare::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, 158 Value *SelVal) { 159 SmallVector<Value *, 8> UseWorkList(LPI->user_begin(), LPI->user_end()); 160 while (!UseWorkList.empty()) { 161 Value *Val = UseWorkList.pop_back_val(); 162 ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val); 163 if (!EVI) 164 continue; 165 if (EVI->getNumIndices() != 1) 166 continue; 167 if (*EVI->idx_begin() == 0) 168 EVI->replaceAllUsesWith(ExnVal); 169 else if (*EVI->idx_begin() == 1) 170 EVI->replaceAllUsesWith(SelVal); 171 if (EVI->getNumUses() == 0) 172 EVI->eraseFromParent(); 173 } 174 175 if (LPI->getNumUses() == 0) 176 return; 177 178 // There are still some uses of LPI. Construct an aggregate with the exception 179 // values and replace the LPI with that aggregate. 180 Type *LPadType = LPI->getType(); 181 Value *LPadVal = UndefValue::get(LPadType); 182 auto *SelI = cast<Instruction>(SelVal); 183 IRBuilder<> Builder(SelI->getParent(), std::next(SelI->getIterator())); 184 LPadVal = Builder.CreateInsertValue(LPadVal, ExnVal, 0, "lpad.val"); 185 LPadVal = Builder.CreateInsertValue(LPadVal, SelVal, 1, "lpad.val"); 186 187 LPI->replaceAllUsesWith(LPadVal); 188 } 189 190 /// setupFunctionContext - Allocate the function context on the stack and fill 191 /// it with all of the data that we know at this point. 192 Value *SjLjEHPrepare::setupFunctionContext(Function &F, 193 ArrayRef<LandingPadInst *> LPads) { 194 BasicBlock *EntryBB = &F.front(); 195 196 // Create an alloca for the incoming jump buffer ptr and the new jump buffer 197 // that needs to be restored on all exits from the function. This is an alloca 198 // because the value needs to be added to the global context list. 199 auto &DL = F.getParent()->getDataLayout(); 200 unsigned Align = DL.getPrefTypeAlignment(FunctionContextTy); 201 FuncCtx = new AllocaInst(FunctionContextTy, nullptr, Align, "fn_context", 202 &EntryBB->front()); 203 204 // Fill in the function context structure. 205 for (unsigned I = 0, E = LPads.size(); I != E; ++I) { 206 LandingPadInst *LPI = LPads[I]; 207 IRBuilder<> Builder(LPI->getParent(), 208 LPI->getParent()->getFirstInsertionPt()); 209 210 // Reference the __data field. 211 Value *FCData = 212 Builder.CreateConstGEP2_32(FunctionContextTy, FuncCtx, 0, 2, "__data"); 213 214 // The exception values come back in context->__data[0]. 215 Value *ExceptionAddr = Builder.CreateConstGEP2_32(doubleUnderDataTy, FCData, 216 0, 0, "exception_gep"); 217 Value *ExnVal = Builder.CreateLoad(ExceptionAddr, true, "exn_val"); 218 ExnVal = Builder.CreateIntToPtr(ExnVal, Builder.getInt8PtrTy()); 219 220 Value *SelectorAddr = Builder.CreateConstGEP2_32(doubleUnderDataTy, FCData, 221 0, 1, "exn_selector_gep"); 222 Value *SelVal = Builder.CreateLoad(SelectorAddr, true, "exn_selector_val"); 223 224 substituteLPadValues(LPI, ExnVal, SelVal); 225 } 226 227 // Personality function 228 IRBuilder<> Builder(EntryBB->getTerminator()); 229 if (!PersonalityFn) 230 PersonalityFn = F.getPersonalityFn(); 231 Value *PersonalityFieldPtr = Builder.CreateConstGEP2_32( 232 FunctionContextTy, FuncCtx, 0, 3, "pers_fn_gep"); 233 Builder.CreateStore( 234 Builder.CreateBitCast(PersonalityFn, Builder.getInt8PtrTy()), 235 PersonalityFieldPtr, /*isVolatile=*/true); 236 237 // LSDA address 238 Value *LSDA = Builder.CreateCall(LSDAAddrFn, {}, "lsda_addr"); 239 Value *LSDAFieldPtr = 240 Builder.CreateConstGEP2_32(FunctionContextTy, FuncCtx, 0, 4, "lsda_gep"); 241 Builder.CreateStore(LSDA, LSDAFieldPtr, /*isVolatile=*/true); 242 243 return FuncCtx; 244 } 245 246 /// lowerIncomingArguments - To avoid having to handle incoming arguments 247 /// specially, we lower each arg to a copy instruction in the entry block. This 248 /// ensures that the argument value itself cannot be live out of the entry 249 /// block. 250 void SjLjEHPrepare::lowerIncomingArguments(Function &F) { 251 BasicBlock::iterator AfterAllocaInsPt = F.begin()->begin(); 252 while (isa<AllocaInst>(AfterAllocaInsPt) && 253 isa<ConstantInt>(cast<AllocaInst>(AfterAllocaInsPt)->getArraySize())) 254 ++AfterAllocaInsPt; 255 assert(AfterAllocaInsPt != F.front().end()); 256 257 for (auto &AI : F.args()) { 258 Type *Ty = AI.getType(); 259 260 // Use 'select i8 true, %arg, undef' to simulate a 'no-op' instruction. 261 Value *TrueValue = ConstantInt::getTrue(F.getContext()); 262 Value *UndefValue = UndefValue::get(Ty); 263 Instruction *SI = SelectInst::Create( 264 TrueValue, &AI, UndefValue, AI.getName() + ".tmp", &*AfterAllocaInsPt); 265 AI.replaceAllUsesWith(SI); 266 267 // Reset the operand, because it was clobbered by the RAUW above. 268 SI->setOperand(1, &AI); 269 } 270 } 271 272 /// lowerAcrossUnwindEdges - Find all variables which are alive across an unwind 273 /// edge and spill them. 274 void SjLjEHPrepare::lowerAcrossUnwindEdges(Function &F, 275 ArrayRef<InvokeInst *> Invokes) { 276 // Finally, scan the code looking for instructions with bad live ranges. 277 for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) { 278 for (BasicBlock::iterator II = BB->begin(), IIE = BB->end(); II != IIE; 279 ++II) { 280 // Ignore obvious cases we don't have to handle. In particular, most 281 // instructions either have no uses or only have a single use inside the 282 // current block. Ignore them quickly. 283 Instruction *Inst = &*II; 284 if (Inst->use_empty()) 285 continue; 286 if (Inst->hasOneUse() && 287 cast<Instruction>(Inst->user_back())->getParent() == BB && 288 !isa<PHINode>(Inst->user_back())) 289 continue; 290 291 // If this is an alloca in the entry block, it's not a real register 292 // value. 293 if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst)) 294 if (isa<ConstantInt>(AI->getArraySize()) && BB == F.begin()) 295 continue; 296 297 // Avoid iterator invalidation by copying users to a temporary vector. 298 SmallVector<Instruction *, 16> Users; 299 for (User *U : Inst->users()) { 300 Instruction *UI = cast<Instruction>(U); 301 if (UI->getParent() != BB || isa<PHINode>(UI)) 302 Users.push_back(UI); 303 } 304 305 // Find all of the blocks that this value is live in. 306 SmallPtrSet<BasicBlock *, 64> LiveBBs; 307 LiveBBs.insert(Inst->getParent()); 308 while (!Users.empty()) { 309 Instruction *U = Users.back(); 310 Users.pop_back(); 311 312 if (!isa<PHINode>(U)) { 313 MarkBlocksLiveIn(U->getParent(), LiveBBs); 314 } else { 315 // Uses for a PHI node occur in their predecessor block. 316 PHINode *PN = cast<PHINode>(U); 317 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 318 if (PN->getIncomingValue(i) == Inst) 319 MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs); 320 } 321 } 322 323 // Now that we know all of the blocks that this thing is live in, see if 324 // it includes any of the unwind locations. 325 bool NeedsSpill = false; 326 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { 327 BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest(); 328 if (UnwindBlock != BB && LiveBBs.count(UnwindBlock)) { 329 DEBUG(dbgs() << "SJLJ Spill: " << *Inst << " around " 330 << UnwindBlock->getName() << "\n"); 331 NeedsSpill = true; 332 break; 333 } 334 } 335 336 // If we decided we need a spill, do it. 337 // FIXME: Spilling this way is overkill, as it forces all uses of 338 // the value to be reloaded from the stack slot, even those that aren't 339 // in the unwind blocks. We should be more selective. 340 if (NeedsSpill) { 341 DemoteRegToStack(*Inst, true); 342 ++NumSpilled; 343 } 344 } 345 } 346 347 // Go through the landing pads and remove any PHIs there. 348 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { 349 BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest(); 350 LandingPadInst *LPI = UnwindBlock->getLandingPadInst(); 351 352 // Place PHIs into a set to avoid invalidating the iterator. 353 SmallPtrSet<PHINode *, 8> PHIsToDemote; 354 for (BasicBlock::iterator PN = UnwindBlock->begin(); isa<PHINode>(PN); ++PN) 355 PHIsToDemote.insert(cast<PHINode>(PN)); 356 if (PHIsToDemote.empty()) 357 continue; 358 359 // Demote the PHIs to the stack. 360 for (PHINode *PN : PHIsToDemote) 361 DemotePHIToStack(PN); 362 363 // Move the landingpad instruction back to the top of the landing pad block. 364 LPI->moveBefore(&UnwindBlock->front()); 365 } 366 } 367 368 /// setupEntryBlockAndCallSites - Setup the entry block by creating and filling 369 /// the function context and marking the call sites with the appropriate 370 /// values. These values are used by the DWARF EH emitter. 371 bool SjLjEHPrepare::setupEntryBlockAndCallSites(Function &F) { 372 SmallVector<ReturnInst *, 16> Returns; 373 SmallVector<InvokeInst *, 16> Invokes; 374 SmallSetVector<LandingPadInst *, 16> LPads; 375 376 // Look through the terminators of the basic blocks to find invokes. 377 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 378 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { 379 if (Function *Callee = II->getCalledFunction()) 380 if (Callee->isIntrinsic() && 381 Callee->getIntrinsicID() == Intrinsic::donothing) { 382 // Remove the NOP invoke. 383 BranchInst::Create(II->getNormalDest(), II); 384 II->eraseFromParent(); 385 continue; 386 } 387 388 Invokes.push_back(II); 389 LPads.insert(II->getUnwindDest()->getLandingPadInst()); 390 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 391 Returns.push_back(RI); 392 } 393 394 if (Invokes.empty()) 395 return false; 396 397 NumInvokes += Invokes.size(); 398 399 lowerIncomingArguments(F); 400 lowerAcrossUnwindEdges(F, Invokes); 401 402 Value *FuncCtx = 403 setupFunctionContext(F, makeArrayRef(LPads.begin(), LPads.end())); 404 BasicBlock *EntryBB = &F.front(); 405 IRBuilder<> Builder(EntryBB->getTerminator()); 406 407 // Get a reference to the jump buffer. 408 Value *JBufPtr = 409 Builder.CreateConstGEP2_32(FunctionContextTy, FuncCtx, 0, 5, "jbuf_gep"); 410 411 // Save the frame pointer. 412 Value *FramePtr = Builder.CreateConstGEP2_32(doubleUnderJBufTy, JBufPtr, 0, 0, 413 "jbuf_fp_gep"); 414 415 Value *Val = Builder.CreateCall(FrameAddrFn, Builder.getInt32(0), "fp"); 416 Builder.CreateStore(Val, FramePtr, /*isVolatile=*/true); 417 418 // Save the stack pointer. 419 Value *StackPtr = Builder.CreateConstGEP2_32(doubleUnderJBufTy, JBufPtr, 0, 2, 420 "jbuf_sp_gep"); 421 422 Val = Builder.CreateCall(StackAddrFn, {}, "sp"); 423 Builder.CreateStore(Val, StackPtr, /*isVolatile=*/true); 424 425 // Call the setup_dispatch instrinsic. It fills in the rest of the jmpbuf. 426 Builder.CreateCall(BuiltinSetupDispatchFn, {}); 427 428 // Store a pointer to the function context so that the back-end will know 429 // where to look for it. 430 Value *FuncCtxArg = Builder.CreateBitCast(FuncCtx, Builder.getInt8PtrTy()); 431 Builder.CreateCall(FuncCtxFn, FuncCtxArg); 432 433 // At this point, we are all set up, update the invoke instructions to mark 434 // their call_site values. 435 for (unsigned I = 0, E = Invokes.size(); I != E; ++I) { 436 insertCallSiteStore(Invokes[I], I + 1); 437 438 ConstantInt *CallSiteNum = 439 ConstantInt::get(Type::getInt32Ty(F.getContext()), I + 1); 440 441 // Record the call site value for the back end so it stays associated with 442 // the invoke. 443 CallInst::Create(CallSiteFn, CallSiteNum, "", Invokes[I]); 444 } 445 446 // Mark call instructions that aren't nounwind as no-action (call_site == 447 // -1). Skip the entry block, as prior to then, no function context has been 448 // created for this function and any unexpected exceptions thrown will go 449 // directly to the caller's context, which is what we want anyway, so no need 450 // to do anything here. 451 for (Function::iterator BB = F.begin(), E = F.end(); ++BB != E;) 452 for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I) 453 if (CallInst *CI = dyn_cast<CallInst>(I)) { 454 if (!CI->doesNotThrow()) 455 insertCallSiteStore(CI, -1); 456 } else if (ResumeInst *RI = dyn_cast<ResumeInst>(I)) { 457 insertCallSiteStore(RI, -1); 458 } 459 460 // Register the function context and make sure it's known to not throw 461 CallInst *Register = 462 CallInst::Create(RegisterFn, FuncCtx, "", EntryBB->getTerminator()); 463 Register->setDoesNotThrow(); 464 465 // Following any allocas not in the entry block, update the saved SP in the 466 // jmpbuf to the new value. 467 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 468 if (BB == F.begin()) 469 continue; 470 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 471 if (CallInst *CI = dyn_cast<CallInst>(I)) { 472 if (CI->getCalledFunction() != StackRestoreFn) 473 continue; 474 } else if (!isa<AllocaInst>(I)) { 475 continue; 476 } 477 Instruction *StackAddr = CallInst::Create(StackAddrFn, "sp"); 478 StackAddr->insertAfter(&*I); 479 Instruction *StoreStackAddr = new StoreInst(StackAddr, StackPtr, true); 480 StoreStackAddr->insertAfter(StackAddr); 481 } 482 } 483 484 // Finally, for any returns from this function, if this function contains an 485 // invoke, add a call to unregister the function context. 486 for (unsigned I = 0, E = Returns.size(); I != E; ++I) 487 CallInst::Create(UnregisterFn, FuncCtx, "", Returns[I]); 488 489 return true; 490 } 491 492 bool SjLjEHPrepare::runOnFunction(Function &F) { 493 bool Res = setupEntryBlockAndCallSites(F); 494 return Res; 495 } 496