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 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 public: 60 static char ID; // Pass identification, replacement for typeid 61 explicit SjLjEHPrepare(const TargetMachine *TM) 62 : 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 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 TargetMachine *TM) { 86 return new SjLjEHPrepare(TM); 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 const TargetLowering *TLI = TM->getTargetLowering(); 194 unsigned Align = 195 TLI->getDataLayout()->getPrefTypeAlignment(FunctionContextTy); 196 FuncCtx = 197 new AllocaInst(FunctionContextTy, 0, Align, "fn_context", EntryBB->begin()); 198 199 // Fill in the function context structure. 200 for (unsigned I = 0, E = LPads.size(); I != E; ++I) { 201 LandingPadInst *LPI = LPads[I]; 202 IRBuilder<> Builder(LPI->getParent()->getFirstInsertionPt()); 203 204 // Reference the __data field. 205 Value *FCData = Builder.CreateConstGEP2_32(FuncCtx, 0, 2, "__data"); 206 207 // The exception values come back in context->__data[0]. 208 Value *ExceptionAddr = Builder.CreateConstGEP2_32(FCData, 0, 0, 209 "exception_gep"); 210 Value *ExnVal = Builder.CreateLoad(ExceptionAddr, true, "exn_val"); 211 ExnVal = Builder.CreateIntToPtr(ExnVal, Builder.getInt8PtrTy()); 212 213 Value *SelectorAddr = Builder.CreateConstGEP2_32(FCData, 0, 1, 214 "exn_selector_gep"); 215 Value *SelVal = Builder.CreateLoad(SelectorAddr, true, "exn_selector_val"); 216 217 substituteLPadValues(LPI, ExnVal, SelVal); 218 } 219 220 // Personality function 221 IRBuilder<> Builder(EntryBB->getTerminator()); 222 if (!PersonalityFn) 223 PersonalityFn = LPads[0]->getPersonalityFn(); 224 Value *PersonalityFieldPtr = Builder.CreateConstGEP2_32(FuncCtx, 0, 3, 225 "pers_fn_gep"); 226 Builder.CreateStore(Builder.CreateBitCast(PersonalityFn, 227 Builder.getInt8PtrTy()), 228 PersonalityFieldPtr, /*isVolatile=*/true); 229 230 // LSDA address 231 Value *LSDA = Builder.CreateCall(LSDAAddrFn, "lsda_addr"); 232 Value *LSDAFieldPtr = Builder.CreateConstGEP2_32(FuncCtx, 0, 4, "lsda_gep"); 233 Builder.CreateStore(LSDA, LSDAFieldPtr, /*isVolatile=*/true); 234 235 return FuncCtx; 236 } 237 238 /// lowerIncomingArguments - To avoid having to handle incoming arguments 239 /// specially, we lower each arg to a copy instruction in the entry block. This 240 /// ensures that the argument value itself cannot be live out of the entry 241 /// block. 242 void SjLjEHPrepare::lowerIncomingArguments(Function &F) { 243 BasicBlock::iterator AfterAllocaInsPt = F.begin()->begin(); 244 while (isa<AllocaInst>(AfterAllocaInsPt) && 245 isa<ConstantInt>(cast<AllocaInst>(AfterAllocaInsPt)->getArraySize())) 246 ++AfterAllocaInsPt; 247 248 for (Function::arg_iterator 249 AI = F.arg_begin(), AE = F.arg_end(); AI != AE; ++AI) { 250 Type *Ty = AI->getType(); 251 252 // Aggregate types can't be cast, but are legal argument types, so we have 253 // to handle them differently. We use an extract/insert pair as a 254 // lightweight method to achieve the same goal. 255 if (isa<StructType>(Ty) || isa<ArrayType>(Ty) || isa<VectorType>(Ty)) { 256 Instruction *EI = ExtractValueInst::Create(AI, 0, "", AfterAllocaInsPt); 257 Instruction *NI = InsertValueInst::Create(AI, EI, 0); 258 NI->insertAfter(EI); 259 AI->replaceAllUsesWith(NI); 260 261 // Set the operand of the instructions back to the AllocaInst. 262 EI->setOperand(0, AI); 263 NI->setOperand(0, AI); 264 } else { 265 // This is always a no-op cast because we're casting AI to AI->getType() 266 // so src and destination types are identical. BitCast is the only 267 // possibility. 268 CastInst *NC = 269 new BitCastInst(AI, AI->getType(), AI->getName() + ".tmp", 270 AfterAllocaInsPt); 271 AI->replaceAllUsesWith(NC); 272 273 // Set the operand of the cast instruction back to the AllocaInst. 274 // Normally it's forbidden to replace a CastInst's operand because it 275 // could cause the opcode to reflect an illegal conversion. However, we're 276 // replacing it here with the same value it was constructed with. We do 277 // this because the above replaceAllUsesWith() clobbered the operand, but 278 // we want this one to remain. 279 NC->setOperand(0, AI); 280 } 281 } 282 } 283 284 /// lowerAcrossUnwindEdges - Find all variables which are alive across an unwind 285 /// edge and spill them. 286 void SjLjEHPrepare::lowerAcrossUnwindEdges(Function &F, 287 ArrayRef<InvokeInst*> Invokes) { 288 // Finally, scan the code looking for instructions with bad live ranges. 289 for (Function::iterator 290 BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) { 291 for (BasicBlock::iterator 292 II = BB->begin(), IIE = BB->end(); II != IIE; ++II) { 293 // Ignore obvious cases we don't have to handle. In particular, most 294 // instructions either have no uses or only have a single use inside the 295 // current block. Ignore them quickly. 296 Instruction *Inst = II; 297 if (Inst->use_empty()) continue; 298 if (Inst->hasOneUse() && 299 cast<Instruction>(Inst->use_back())->getParent() == BB && 300 !isa<PHINode>(Inst->use_back())) continue; 301 302 // If this is an alloca in the entry block, it's not a real register 303 // value. 304 if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst)) 305 if (isa<ConstantInt>(AI->getArraySize()) && BB == F.begin()) 306 continue; 307 308 // Avoid iterator invalidation by copying users to a temporary vector. 309 SmallVector<Instruction*, 16> Users; 310 for (Value::use_iterator 311 UI = Inst->use_begin(), E = Inst->use_end(); UI != E; ++UI) { 312 Instruction *User = cast<Instruction>(*UI); 313 if (User->getParent() != BB || isa<PHINode>(User)) 314 Users.push_back(User); 315 } 316 317 // Find all of the blocks that this value is live in. 318 SmallPtrSet<BasicBlock*, 64> LiveBBs; 319 LiveBBs.insert(Inst->getParent()); 320 while (!Users.empty()) { 321 Instruction *U = Users.back(); 322 Users.pop_back(); 323 324 if (!isa<PHINode>(U)) { 325 MarkBlocksLiveIn(U->getParent(), LiveBBs); 326 } else { 327 // Uses for a PHI node occur in their predecessor block. 328 PHINode *PN = cast<PHINode>(U); 329 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 330 if (PN->getIncomingValue(i) == Inst) 331 MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs); 332 } 333 } 334 335 // Now that we know all of the blocks that this thing is live in, see if 336 // it includes any of the unwind locations. 337 bool NeedsSpill = false; 338 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { 339 BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest(); 340 if (UnwindBlock != BB && LiveBBs.count(UnwindBlock)) { 341 DEBUG(dbgs() << "SJLJ Spill: " << *Inst << " around " 342 << UnwindBlock->getName() << "\n"); 343 NeedsSpill = true; 344 break; 345 } 346 } 347 348 // If we decided we need a spill, do it. 349 // FIXME: Spilling this way is overkill, as it forces all uses of 350 // the value to be reloaded from the stack slot, even those that aren't 351 // in the unwind blocks. We should be more selective. 352 if (NeedsSpill) { 353 DemoteRegToStack(*Inst, true); 354 ++NumSpilled; 355 } 356 } 357 } 358 359 // Go through the landing pads and remove any PHIs there. 360 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { 361 BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest(); 362 LandingPadInst *LPI = UnwindBlock->getLandingPadInst(); 363 364 // Place PHIs into a set to avoid invalidating the iterator. 365 SmallPtrSet<PHINode*, 8> PHIsToDemote; 366 for (BasicBlock::iterator 367 PN = UnwindBlock->begin(); isa<PHINode>(PN); ++PN) 368 PHIsToDemote.insert(cast<PHINode>(PN)); 369 if (PHIsToDemote.empty()) continue; 370 371 // Demote the PHIs to the stack. 372 for (SmallPtrSet<PHINode*, 8>::iterator 373 I = PHIsToDemote.begin(), E = PHIsToDemote.end(); 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. 384 bool 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()) return false; 408 409 NumInvokes += Invokes.size(); 410 411 lowerIncomingArguments(F); 412 lowerAcrossUnwindEdges(F, Invokes); 413 414 Value *FuncCtx = 415 setupFunctionContext(F, makeArrayRef(LPads.begin(), LPads.end())); 416 BasicBlock *EntryBB = F.begin(); 417 IRBuilder<> Builder(EntryBB->getTerminator()); 418 419 // Get a reference to the jump buffer. 420 Value *JBufPtr = Builder.CreateConstGEP2_32(FuncCtx, 0, 5, "jbuf_gep"); 421 422 // Save the frame pointer. 423 Value *FramePtr = Builder.CreateConstGEP2_32(JBufPtr, 0, 0, "jbuf_fp_gep"); 424 425 Value *Val = Builder.CreateCall(FrameAddrFn, Builder.getInt32(0), "fp"); 426 Builder.CreateStore(Val, FramePtr, /*isVolatile=*/true); 427 428 // Save the stack pointer. 429 Value *StackPtr = Builder.CreateConstGEP2_32(JBufPtr, 0, 2, "jbuf_sp_gep"); 430 431 Val = Builder.CreateCall(StackAddrFn, "sp"); 432 Builder.CreateStore(Val, StackPtr, /*isVolatile=*/true); 433 434 // Call the setjmp instrinsic. It fills in the rest of the jmpbuf. 435 Value *SetjmpArg = Builder.CreateBitCast(JBufPtr, Builder.getInt8PtrTy()); 436 Builder.CreateCall(BuiltinSetjmpFn, SetjmpArg); 437 438 // Store a pointer to the function context so that the back-end will know 439 // where to look for it. 440 Value *FuncCtxArg = Builder.CreateBitCast(FuncCtx, Builder.getInt8PtrTy()); 441 Builder.CreateCall(FuncCtxFn, FuncCtxArg); 442 443 // At this point, we are all set up, update the invoke instructions to mark 444 // their call_site values. 445 for (unsigned I = 0, E = Invokes.size(); I != E; ++I) { 446 insertCallSiteStore(Invokes[I], I + 1); 447 448 ConstantInt *CallSiteNum = 449 ConstantInt::get(Type::getInt32Ty(F.getContext()), I + 1); 450 451 // Record the call site value for the back end so it stays associated with 452 // the invoke. 453 CallInst::Create(CallSiteFn, CallSiteNum, "", Invokes[I]); 454 } 455 456 // Mark call instructions that aren't nounwind as no-action (call_site == 457 // -1). Skip the entry block, as prior to then, no function context has been 458 // created for this function and any unexpected exceptions thrown will go 459 // directly to the caller's context, which is what we want anyway, so no need 460 // to do anything here. 461 for (Function::iterator BB = F.begin(), E = F.end(); ++BB != E;) 462 for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I) 463 if (CallInst *CI = dyn_cast<CallInst>(I)) { 464 if (!CI->doesNotThrow()) 465 insertCallSiteStore(CI, -1); 466 } else if (ResumeInst *RI = dyn_cast<ResumeInst>(I)) { 467 insertCallSiteStore(RI, -1); 468 } 469 470 // Register the function context and make sure it's known to not throw 471 CallInst *Register = CallInst::Create(RegisterFn, FuncCtx, "", 472 EntryBB->getTerminator()); 473 Register->setDoesNotThrow(); 474 475 // Following any allocas not in the entry block, update the saved SP in the 476 // jmpbuf to the new value. 477 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 478 if (BB == F.begin()) 479 continue; 480 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 481 if (CallInst *CI = dyn_cast<CallInst>(I)) { 482 if (CI->getCalledFunction() != StackRestoreFn) 483 continue; 484 } else if (!isa<AllocaInst>(I)) { 485 continue; 486 } 487 Instruction *StackAddr = CallInst::Create(StackAddrFn, "sp"); 488 StackAddr->insertAfter(I); 489 Instruction *StoreStackAddr = new StoreInst(StackAddr, StackPtr, true); 490 StoreStackAddr->insertAfter(StackAddr); 491 } 492 } 493 494 // Finally, for any returns from this function, if this function contains an 495 // invoke, add a call to unregister the function context. 496 for (unsigned I = 0, E = Returns.size(); I != E; ++I) 497 CallInst::Create(UnregisterFn, FuncCtx, "", Returns[I]); 498 499 return true; 500 } 501 502 bool SjLjEHPrepare::runOnFunction(Function &F) { 503 bool Res = setupEntryBlockAndCallSites(F); 504 return Res; 505 } 506
