SjLjEHPrepare.cpp revision 8b818d7e98309125c6058c4ea72a7dc73b031db2
1//===- SjLjEHPass.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/Transforms/Scalar.h" 17#include "llvm/Constants.h" 18#include "llvm/DerivedTypes.h" 19#include "llvm/Instructions.h" 20#include "llvm/Intrinsics.h" 21#include "llvm/LLVMContext.h" 22#include "llvm/Module.h" 23#include "llvm/Pass.h" 24#include "llvm/CodeGen/Passes.h" 25#include "llvm/Transforms/Utils/BasicBlockUtils.h" 26#include "llvm/Transforms/Utils/Local.h" 27#include "llvm/ADT/Statistic.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Support/Compiler.h" 30#include "llvm/Support/Debug.h" 31#include "llvm/Support/raw_ostream.h" 32#include "llvm/Target/TargetLowering.h" 33#include <set> 34using namespace llvm; 35 36STATISTIC(NumInvokes, "Number of invokes replaced"); 37STATISTIC(NumUnwinds, "Number of unwinds replaced"); 38STATISTIC(NumSpilled, "Number of registers live across unwind edges"); 39 40namespace { 41 class VISIBILITY_HIDDEN SjLjEHPass : public FunctionPass { 42 43 const TargetLowering *TLI; 44 45 const Type *FunctionContextTy; 46 Constant *RegisterFn; 47 Constant *UnregisterFn; 48 Constant *ResumeFn; 49 Constant *BuiltinSetjmpFn; 50 Constant *FrameAddrFn; 51 Constant *LSDAAddrFn; 52 Value *PersonalityFn; 53 Constant *Selector32Fn; 54 Constant *Selector64Fn; 55 Constant *ExceptionFn; 56 57 Value *CallSite; 58 public: 59 static char ID; // Pass identification, replacement for typeid 60 explicit SjLjEHPass(const TargetLowering *tli = NULL) 61 : FunctionPass(&ID), TLI(tli) { } 62 bool doInitialization(Module &M); 63 bool runOnFunction(Function &F); 64 65 virtual void getAnalysisUsage(AnalysisUsage &AU) const { } 66 const char *getPassName() const { 67 return "SJLJ Exception Handling preparation"; 68 } 69 70 private: 71 void markInvokeCallSite(InvokeInst *II, unsigned InvokeNo, 72 Value *CallSite, 73 SwitchInst *CatchSwitch); 74 void splitLiveRangesLiveAcrossInvokes(std::vector<InvokeInst*> &Invokes); 75 bool insertSjLjEHSupport(Function &F); 76 }; 77} // end anonymous namespace 78 79char SjLjEHPass::ID = 0; 80 81// Public Interface To the SjLjEHPass pass. 82FunctionPass *llvm::createSjLjEHPass(const TargetLowering *TLI) { 83 return new SjLjEHPass(TLI); 84} 85// doInitialization - Make sure that there is a prototype for abort in the 86// current module. 87bool SjLjEHPass::doInitialization(Module &M) { 88 // Build the function context structure. 89 // builtin_setjmp uses a five word jbuf 90 const Type *VoidPtrTy = 91 PointerType::getUnqual(Type::getInt8Ty(M.getContext())); 92 const Type *Int32Ty = Type::getInt32Ty(M.getContext()); 93 FunctionContextTy = 94 StructType::get(M.getContext(), 95 VoidPtrTy, // __prev 96 Int32Ty, // call_site 97 ArrayType::get(Int32Ty, 4), // __data 98 VoidPtrTy, // __personality 99 VoidPtrTy, // __lsda 100 ArrayType::get(VoidPtrTy, 5), // __jbuf 101 NULL); 102 RegisterFn = M.getOrInsertFunction("_Unwind_SjLj_Register", 103 Type::getVoidTy(M.getContext()), 104 PointerType::getUnqual(FunctionContextTy), 105 (Type *)0); 106 UnregisterFn = 107 M.getOrInsertFunction("_Unwind_SjLj_Unregister", 108 Type::getVoidTy(M.getContext()), 109 PointerType::getUnqual(FunctionContextTy), 110 (Type *)0); 111 ResumeFn = 112 M.getOrInsertFunction("_Unwind_SjLj_Resume", 113 Type::getVoidTy(M.getContext()), 114 VoidPtrTy, 115 (Type *)0); 116 FrameAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::frameaddress); 117 BuiltinSetjmpFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_setjmp); 118 LSDAAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_lsda); 119 Selector32Fn = Intrinsic::getDeclaration(&M, Intrinsic::eh_selector_i32); 120 Selector64Fn = Intrinsic::getDeclaration(&M, Intrinsic::eh_selector_i64); 121 ExceptionFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_exception); 122 123 return true; 124} 125 126/// markInvokeCallSite - Insert code to mark the call_site for this invoke 127void SjLjEHPass::markInvokeCallSite(InvokeInst *II, unsigned InvokeNo, 128 Value *CallSite, 129 SwitchInst *CatchSwitch) { 130 ConstantInt *CallSiteNoC= ConstantInt::get(Type::getInt32Ty(II->getContext()), 131 InvokeNo); 132 // The runtime comes back to the dispatcher with the call_site - 1 in 133 // the context. Odd, but there it is. 134 ConstantInt *SwitchValC = ConstantInt::get(Type::getInt32Ty(II->getContext()), 135 InvokeNo - 1); 136 137 // If the unwind edge has phi nodes, split the edge. 138 if (isa<PHINode>(II->getUnwindDest()->begin())) { 139 SplitCriticalEdge(II, 1, this); 140 141 // If there are any phi nodes left, they must have a single predecessor. 142 while (PHINode *PN = dyn_cast<PHINode>(II->getUnwindDest()->begin())) { 143 PN->replaceAllUsesWith(PN->getIncomingValue(0)); 144 PN->eraseFromParent(); 145 } 146 } 147 148 // Insert a store of the invoke num before the invoke and store zero into the 149 // location afterward. 150 new StoreInst(CallSiteNoC, CallSite, true, II); // volatile 151 152 // Add a switch case to our unwind block. 153 CatchSwitch->addCase(SwitchValC, II->getUnwindDest()); 154 // We still want this to look like an invoke so we emit the LSDA properly 155 // FIXME: ??? Or will this cause strangeness with mis-matched IDs like 156 // when it was in the front end? 157} 158 159/// MarkBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until 160/// we reach blocks we've already seen. 161static void MarkBlocksLiveIn(BasicBlock *BB, std::set<BasicBlock*> &LiveBBs) { 162 if (!LiveBBs.insert(BB).second) return; // already been here. 163 164 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) 165 MarkBlocksLiveIn(*PI, LiveBBs); 166} 167 168// live across unwind edges. Each value that is live across an unwind edge 169// we spill into a stack location, guaranteeing that there is nothing live 170// across the unwind edge. This process also splits all critical edges 171// coming out of invoke's. 172void SjLjEHPass:: 173splitLiveRangesLiveAcrossInvokes(std::vector<InvokeInst*> &Invokes) { 174 // First step, split all critical edges from invoke instructions. 175 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { 176 InvokeInst *II = Invokes[i]; 177 SplitCriticalEdge(II, 0, this); 178 SplitCriticalEdge(II, 1, this); 179 assert(!isa<PHINode>(II->getNormalDest()) && 180 !isa<PHINode>(II->getUnwindDest()) && 181 "critical edge splitting left single entry phi nodes?"); 182 } 183 184 Function *F = Invokes.back()->getParent()->getParent(); 185 186 // To avoid having to handle incoming arguments specially, we lower each arg 187 // to a copy instruction in the entry block. This ensures that the argument 188 // value itself cannot be live across the entry block. 189 BasicBlock::iterator AfterAllocaInsertPt = F->begin()->begin(); 190 while (isa<AllocaInst>(AfterAllocaInsertPt) && 191 isa<ConstantInt>(cast<AllocaInst>(AfterAllocaInsertPt)->getArraySize())) 192 ++AfterAllocaInsertPt; 193 for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); 194 AI != E; ++AI) { 195 // This is always a no-op cast because we're casting AI to AI->getType() so 196 // src and destination types are identical. BitCast is the only possibility. 197 CastInst *NC = new BitCastInst( 198 AI, AI->getType(), AI->getName()+".tmp", AfterAllocaInsertPt); 199 AI->replaceAllUsesWith(NC); 200 // Normally its is forbidden to replace a CastInst's operand because it 201 // could cause the opcode to reflect an illegal conversion. However, we're 202 // replacing it here with the same value it was constructed with to simply 203 // make NC its user. 204 NC->setOperand(0, AI); 205 } 206 207 // Finally, scan the code looking for instructions with bad live ranges. 208 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 209 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { 210 // Ignore obvious cases we don't have to handle. In particular, most 211 // instructions either have no uses or only have a single use inside the 212 // current block. Ignore them quickly. 213 Instruction *Inst = II; 214 if (Inst->use_empty()) continue; 215 if (Inst->hasOneUse() && 216 cast<Instruction>(Inst->use_back())->getParent() == BB && 217 !isa<PHINode>(Inst->use_back())) continue; 218 219 // If this is an alloca in the entry block, it's not a real register 220 // value. 221 if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst)) 222 if (isa<ConstantInt>(AI->getArraySize()) && BB == F->begin()) 223 continue; 224 225 // Avoid iterator invalidation by copying users to a temporary vector. 226 std::vector<Instruction*> Users; 227 for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end(); 228 UI != E; ++UI) { 229 Instruction *User = cast<Instruction>(*UI); 230 if (User->getParent() != BB || isa<PHINode>(User)) 231 Users.push_back(User); 232 } 233 234 // Scan all of the uses and see if the live range is live across an unwind 235 // edge. If we find a use live across an invoke edge, create an alloca 236 // and spill the value. 237 std::set<InvokeInst*> InvokesWithStoreInserted; 238 239 // Find all of the blocks that this value is live in. 240 std::set<BasicBlock*> LiveBBs; 241 LiveBBs.insert(Inst->getParent()); 242 while (!Users.empty()) { 243 Instruction *U = Users.back(); 244 Users.pop_back(); 245 246 if (!isa<PHINode>(U)) { 247 MarkBlocksLiveIn(U->getParent(), LiveBBs); 248 } else { 249 // Uses for a PHI node occur in their predecessor block. 250 PHINode *PN = cast<PHINode>(U); 251 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 252 if (PN->getIncomingValue(i) == Inst) 253 MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs); 254 } 255 } 256 257 // Now that we know all of the blocks that this thing is live in, see if 258 // it includes any of the unwind locations. 259 bool NeedsSpill = false; 260 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { 261 BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest(); 262 if (UnwindBlock != BB && LiveBBs.count(UnwindBlock)) { 263 NeedsSpill = true; 264 } 265 } 266 267 // If we decided we need a spill, do it. 268 if (NeedsSpill) { 269 ++NumSpilled; 270 DemoteRegToStack(*Inst, true); 271 } 272 } 273} 274 275bool SjLjEHPass::insertSjLjEHSupport(Function &F) { 276 std::vector<ReturnInst*> Returns; 277 std::vector<UnwindInst*> Unwinds; 278 std::vector<InvokeInst*> Invokes; 279 280 // Look through the terminators of the basic blocks to find invokes, returns 281 // and unwinds 282 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 283 if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 284 // Remember all return instructions in case we insert an invoke into this 285 // function. 286 Returns.push_back(RI); 287 } else if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) { 288 Invokes.push_back(II); 289 } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) { 290 Unwinds.push_back(UI); 291 } 292 // If we don't have any invokes or unwinds, there's nothing to do. 293 if (Unwinds.empty() && Invokes.empty()) return false; 294 295 NumInvokes += Invokes.size(); 296 NumUnwinds += Unwinds.size(); 297 298 299 if (!Invokes.empty()) { 300 // We have invokes, so we need to add register/unregister calls to get 301 // this function onto the global unwind stack. 302 // 303 // First thing we need to do is scan the whole function for values that are 304 // live across unwind edges. Each value that is live across an unwind edge 305 // we spill into a stack location, guaranteeing that there is nothing live 306 // across the unwind edge. This process also splits all critical edges 307 // coming out of invoke's. 308 splitLiveRangesLiveAcrossInvokes(Invokes); 309 310 BasicBlock *EntryBB = F.begin(); 311 // Create an alloca for the incoming jump buffer ptr and the new jump buffer 312 // that needs to be restored on all exits from the function. This is an 313 // alloca because the value needs to be added to the global context list. 314 unsigned Align = 4; // FIXME: Should be a TLI check? 315 AllocaInst *FunctionContext = 316 new AllocaInst(FunctionContextTy, 0, Align, 317 "fcn_context", F.begin()->begin()); 318 319 Value *Idxs[2]; 320 const Type *Int32Ty = Type::getInt32Ty(F.getContext()); 321 Value *Zero = ConstantInt::get(Int32Ty, 0); 322 // We need to also keep around a reference to the call_site field 323 Idxs[0] = Zero; 324 Idxs[1] = ConstantInt::get(Int32Ty, 1); 325 CallSite = GetElementPtrInst::Create(FunctionContext, Idxs, Idxs+2, 326 "call_site", 327 EntryBB->getTerminator()); 328 329 // The exception selector comes back in context->data[1] 330 Idxs[1] = ConstantInt::get(Int32Ty, 2); 331 Value *FCData = GetElementPtrInst::Create(FunctionContext, Idxs, Idxs+2, 332 "fc_data", 333 EntryBB->getTerminator()); 334 Idxs[1] = ConstantInt::get(Int32Ty, 1); 335 Value *SelectorAddr = GetElementPtrInst::Create(FCData, Idxs, Idxs+2, 336 "exc_selector_gep", 337 EntryBB->getTerminator()); 338 // The exception value comes back in context->data[0] 339 Idxs[1] = Zero; 340 Value *ExceptionAddr = GetElementPtrInst::Create(FCData, Idxs, Idxs+2, 341 "exception_gep", 342 EntryBB->getTerminator()); 343 344 // Find the eh.selector.* and eh.exception calls. We'll use the first 345 // ex.selector to determine the right personality function to use. For 346 // SJLJ, we always use the same personality for the whole function, 347 // not on a per-selector basis. 348 // FIXME: That's a bit ugly. Better way? 349 std::vector<CallInst*> EH_Selectors; 350 std::vector<CallInst*> EH_Exceptions; 351 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) { 352 // for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { 353// BasicBlock *Pad = Invokes[0]->getUnwindDest(); 354 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 355 if (CallInst *CI = dyn_cast<CallInst>(I)) { 356 if (CI->getCalledFunction() == Selector32Fn || 357 CI->getCalledFunction() == Selector64Fn) { 358 if (!PersonalityFn) PersonalityFn = CI->getOperand(2); 359 EH_Selectors.push_back(CI); 360 } else if (CI->getCalledFunction() == ExceptionFn) { 361 EH_Exceptions.push_back(CI); 362 } 363 } 364 } 365 } 366 // The result of the eh.selector call will be replaced with a 367 // a reference to the selector value returned in the function 368 // context. We leave the selector itself so the EH analysis later 369 // can use it. 370 for (int i = 0, e = EH_Selectors.size(); i < e; ++i) { 371 CallInst *I = EH_Selectors[i]; 372 Value *SelectorVal = new LoadInst(SelectorAddr, "select_val", true, I); 373 I->replaceAllUsesWith(SelectorVal); 374 } 375 // eh.exception calls are replaced with references to the proper 376 // location in the context. Unlike eh.selector, the eh.exception 377 // calls are removed entirely. 378 for (int i = 0, e = EH_Exceptions.size(); i < e; ++i) { 379 CallInst *I = EH_Exceptions[i]; 380 // Possible for there to be duplicates, so check to make sure 381 // the instruction hasn't already been removed. 382 if (!I->getParent()) continue; 383 Value *Val = new LoadInst(ExceptionAddr, "exception", true, I); 384 Val = CastInst::Create(Instruction::IntToPtr, Val, 385 PointerType::getUnqual(Type::getInt8Ty(F.getContext())), 386 "", I); 387 388 I->replaceAllUsesWith(Val); 389 I->eraseFromParent(); 390 } 391 392 393 394 395 // The entry block changes to have the eh.sjlj.setjmp, with a conditional 396 // branch to a dispatch block for non-zero returns. If we return normally, 397 // we're not handling an exception and just register the function context 398 // and continue. 399 400 // Create the dispatch block. The dispatch block is basically a big switch 401 // statement that goes to all of the invoke landing pads. 402 BasicBlock *DispatchBlock = 403 BasicBlock::Create(F.getContext(), "eh.sjlj.setjmp.catch", &F); 404 405 // Insert a load in the Catch block, and a switch on its value. By default, 406 // we go to a block that just does an unwind (which is the correct action 407 // for a standard call). 408 BasicBlock *UnwindBlock = BasicBlock::Create(F.getContext(), "unwindbb", &F); 409 Unwinds.push_back(new UnwindInst(F.getContext(), UnwindBlock)); 410 411 Value *DispatchLoad = new LoadInst(CallSite, "invoke.num", true, 412 DispatchBlock); 413 SwitchInst *DispatchSwitch = 414 SwitchInst::Create(DispatchLoad, UnwindBlock, Invokes.size(), DispatchBlock); 415 // Split the entry block to insert the conditional branch for the setjmp. 416 BasicBlock *ContBlock = EntryBB->splitBasicBlock(EntryBB->getTerminator(), 417 "eh.sjlj.setjmp.cont"); 418 419 // Populate the Function Context 420 // 1. LSDA address 421 // 2. Personality function address 422 // 3. jmpbuf (save FP and call eh.sjlj.setjmp) 423 424 // LSDA address 425 Idxs[0] = Zero; 426 Idxs[1] = ConstantInt::get(Int32Ty, 4); 427 Value *LSDAFieldPtr = 428 GetElementPtrInst::Create(FunctionContext, Idxs, Idxs+2, 429 "lsda_gep", 430 EntryBB->getTerminator()); 431 Value *LSDA = CallInst::Create(LSDAAddrFn, "lsda_addr", 432 EntryBB->getTerminator()); 433 new StoreInst(LSDA, LSDAFieldPtr, true, EntryBB->getTerminator()); 434 435 Idxs[1] = ConstantInt::get(Int32Ty, 3); 436 Value *PersonalityFieldPtr = 437 GetElementPtrInst::Create(FunctionContext, Idxs, Idxs+2, 438 "lsda_gep", 439 EntryBB->getTerminator()); 440 new StoreInst(PersonalityFn, PersonalityFieldPtr, true, 441 EntryBB->getTerminator()); 442 443 // Save the frame pointer. 444 Idxs[1] = ConstantInt::get(Int32Ty, 5); 445 Value *FieldPtr 446 = GetElementPtrInst::Create(FunctionContext, Idxs, Idxs+2, 447 "jbuf_gep", 448 EntryBB->getTerminator()); 449 Idxs[1] = ConstantInt::get(Int32Ty, 0); 450 Value *ElemPtr = 451 GetElementPtrInst::Create(FieldPtr, Idxs, Idxs+2, "jbuf_fp_gep", 452 EntryBB->getTerminator()); 453 454 Value *Val = CallInst::Create(FrameAddrFn, 455 ConstantInt::get(Int32Ty, 0), 456 "fp", 457 EntryBB->getTerminator()); 458 new StoreInst(Val, ElemPtr, true, EntryBB->getTerminator()); 459 // Call the setjmp instrinsic. It fills in the rest of the jmpbuf 460 Value *SetjmpArg = 461 CastInst::Create(Instruction::BitCast, FieldPtr, 462 Type::getInt8Ty(F.getContext())->getPointerTo(), "", 463 EntryBB->getTerminator()); 464 Value *DispatchVal = CallInst::Create(BuiltinSetjmpFn, SetjmpArg, 465 "dispatch", 466 EntryBB->getTerminator()); 467 // check the return value of the setjmp. non-zero goes to dispatcher 468 Value *IsNormal = new ICmpInst(EntryBB->getTerminator(), 469 ICmpInst::ICMP_EQ, DispatchVal, Zero, 470 "notunwind"); 471 // Nuke the uncond branch. 472 EntryBB->getTerminator()->eraseFromParent(); 473 474 // Put in a new condbranch in its place. 475 BranchInst::Create(ContBlock, DispatchBlock, IsNormal, EntryBB); 476 477 // Register the function context and make sure it's known to not throw 478 CallInst *Register = 479 CallInst::Create(RegisterFn, FunctionContext, "", 480 ContBlock->getTerminator()); 481 Register->setDoesNotThrow(); 482 483 // At this point, we are all set up, update the invoke instructions 484 // to mark their call_site values, and fill in the dispatch switch 485 // accordingly. 486 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) 487 markInvokeCallSite(Invokes[i], i+1, CallSite, DispatchSwitch); 488 489 // The front end has likely added calls to _Unwind_Resume. We need 490 // to find those calls and mark the call_site as -1 immediately prior. 491 // resume is a noreturn function, so any block that has a call to it 492 // should end in an 'unreachable' instruction with the call immediately 493 // prior. That's how we'll search. 494 // ??? There's got to be a better way. this is fugly. 495 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 496 if ((dyn_cast<UnreachableInst>(BB->getTerminator()))) { 497 BasicBlock::iterator I = BB->getTerminator(); 498 // Check the previous instruction and see if it's a resume call 499 if (I == BB->begin()) continue; 500 if (CallInst *CI = dyn_cast<CallInst>(--I)) { 501 if (CI->getCalledFunction() == ResumeFn) { 502 Value *NegativeOne = ConstantInt::get(Int32Ty, -1); 503 new StoreInst(NegativeOne, CallSite, true, I); // volatile 504 } 505 } 506 } 507 508 // Replace all unwinds with a branch to the unwind handler. 509 // ??? Should this ever happen with sjlj exceptions? 510 for (unsigned i = 0, e = Unwinds.size(); i != e; ++i) { 511 BranchInst::Create(UnwindBlock, Unwinds[i]); 512 Unwinds[i]->eraseFromParent(); 513 } 514 515 // Finally, for any returns from this function, if this function contains an 516 // invoke, add a call to unregister the function context. 517 for (unsigned i = 0, e = Returns.size(); i != e; ++i) 518 CallInst::Create(UnregisterFn, FunctionContext, "", Returns[i]); 519 } 520 521 return true; 522} 523 524bool SjLjEHPass::runOnFunction(Function &F) { 525 bool Res = insertSjLjEHSupport(F); 526 return Res; 527} 528