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