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