1 //===- SjLjEHPass.cpp - Eliminate Invoke & Unwind instructions -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This transformation is designed for use by code generators which use SjLj
11 // based exception handling.
13 //===----------------------------------------------------------------------===//
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/Target/TargetData.h"
26 #include "llvm/Target/TargetLowering.h"
27 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
28 #include "llvm/Transforms/Utils/Local.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/IRBuilder.h"
32 #include "llvm/ADT/DenseMap.h"
33 #include "llvm/ADT/SetVector.h"
34 #include "llvm/ADT/SmallPtrSet.h"
35 #include "llvm/ADT/SmallVector.h"
36 #include "llvm/ADT/Statistic.h"
40 STATISTIC(NumInvokes, "Number of invokes replaced");
41 STATISTIC(NumSpilled, "Number of registers live across unwind edges");
44 class SjLjEHPass : public FunctionPass {
45 const TargetLowering *TLI;
46 Type *FunctionContextTy;
48 Constant *UnregisterFn;
49 Constant *BuiltinSetjmpFn;
50 Constant *FrameAddrFn;
51 Constant *StackAddrFn;
52 Constant *StackRestoreFn;
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);
65 virtual void getAnalysisUsage(AnalysisUsage &AU) const {}
66 const char *getPassName() const {
67 return "SJLJ Exception Handling preparation";
71 bool setupEntryBlockAndCallSites(Function &F);
72 void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal,
73 Value *SelVal, IRBuilder<> &Builder);
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, Value *CallSite);
79 } // end anonymous namespace
81 char SjLjEHPass::ID = 0;
83 // Public Interface To the SjLjEHPass pass.
84 FunctionPass *llvm::createSjLjEHPass(const TargetLowering *TLI) {
85 return new SjLjEHPass(TLI);
87 // doInitialization - Set up decalarations and types needed to process
89 bool SjLjEHPass::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());
95 StructType::get(VoidPtrTy, // __prev
97 ArrayType::get(Int32Ty, 4), // __data
98 VoidPtrTy, // __personality
100 ArrayType::get(VoidPtrTy, 5), // __jbuf
102 RegisterFn = M.getOrInsertFunction("_Unwind_SjLj_Register",
103 Type::getVoidTy(M.getContext()),
104 PointerType::getUnqual(FunctionContextTy),
107 M.getOrInsertFunction("_Unwind_SjLj_Unregister",
108 Type::getVoidTy(M.getContext()),
109 PointerType::getUnqual(FunctionContextTy),
111 FrameAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::frameaddress);
112 StackAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::stacksave);
113 StackRestoreFn = Intrinsic::getDeclaration(&M, Intrinsic::stackrestore);
114 BuiltinSetjmpFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_setjmp);
115 LSDAAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_lsda);
116 CallSiteFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_callsite);
117 FuncCtxFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_functioncontext);
123 /// insertCallSiteStore - Insert a store of the call-site value to the
125 void SjLjEHPass::insertCallSiteStore(Instruction *I, int Number,
127 ConstantInt *CallSiteNoC = ConstantInt::get(Type::getInt32Ty(I->getContext()),
129 // Insert a store of the call-site number
130 new StoreInst(CallSiteNoC, CallSite, true, I); // volatile
133 /// MarkBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until
134 /// we reach blocks we've already seen.
135 static void MarkBlocksLiveIn(BasicBlock *BB,
136 SmallPtrSet<BasicBlock*, 64> &LiveBBs) {
137 if (!LiveBBs.insert(BB)) return; // already been here.
139 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
140 MarkBlocksLiveIn(*PI, LiveBBs);
143 /// substituteLPadValues - Substitute the values returned by the landingpad
144 /// instruction with those returned by the personality function.
145 void SjLjEHPass::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal,
146 Value *SelVal, IRBuilder<> &Builder) {
147 SmallVector<Value*, 8> UseWorkList(LPI->use_begin(), LPI->use_end());
148 while (!UseWorkList.empty()) {
149 Value *Val = UseWorkList.pop_back_val();
150 ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val);
152 if (EVI->getNumIndices() != 1) continue;
153 if (*EVI->idx_begin() == 0)
154 EVI->replaceAllUsesWith(ExnVal);
155 else if (*EVI->idx_begin() == 1)
156 EVI->replaceAllUsesWith(SelVal);
157 if (EVI->getNumUses() == 0)
158 EVI->eraseFromParent();
161 if (LPI->getNumUses() == 0) return;
163 // There are still some uses of LPI. Construct an aggregate with the exception
164 // values and replace the LPI with that aggregate.
165 Type *LPadType = LPI->getType();
166 Value *LPadVal = UndefValue::get(LPadType);
167 LPadVal = Builder.CreateInsertValue(LPadVal, ExnVal, 0, "lpad.val");
168 LPadVal = Builder.CreateInsertValue(LPadVal, SelVal, 1, "lpad.val");
170 LPI->replaceAllUsesWith(LPadVal);
173 /// setupFunctionContext - Allocate the function context on the stack and fill
174 /// it with all of the data that we know at this point.
176 setupFunctionContext(Function &F, ArrayRef<LandingPadInst*> LPads) {
177 BasicBlock *EntryBB = F.begin();
179 // Create an alloca for the incoming jump buffer ptr and the new jump buffer
180 // that needs to be restored on all exits from the function. This is an alloca
181 // because the value needs to be added to the global context list.
183 TLI->getTargetData()->getPrefTypeAlignment(FunctionContextTy);
184 AllocaInst *FuncCtx =
185 new AllocaInst(FunctionContextTy, 0, Align, "fn_context", EntryBB->begin());
187 // Fill in the function context structure.
189 Type *Int32Ty = Type::getInt32Ty(F.getContext());
190 Value *Zero = ConstantInt::get(Int32Ty, 0);
191 Value *One = ConstantInt::get(Int32Ty, 1);
193 // Keep around a reference to the call_site field.
196 CallSite = GetElementPtrInst::Create(FuncCtx, Idxs, "call_site",
197 EntryBB->getTerminator());
199 // Reference the __data field.
200 Idxs[1] = ConstantInt::get(Int32Ty, 2);
201 Value *FCData = GetElementPtrInst::Create(FuncCtx, Idxs, "__data",
202 EntryBB->getTerminator());
204 // The exception value comes back in context->__data[0].
206 Value *ExceptionAddr = GetElementPtrInst::Create(FCData, Idxs,
208 EntryBB->getTerminator());
210 // The exception selector comes back in context->__data[1].
212 Value *SelectorAddr = GetElementPtrInst::Create(FCData, Idxs,
214 EntryBB->getTerminator());
216 for (unsigned I = 0, E = LPads.size(); I != E; ++I) {
217 LandingPadInst *LPI = LPads[I];
218 IRBuilder<> Builder(LPI->getParent()->getFirstInsertionPt());
220 Value *ExnVal = Builder.CreateLoad(ExceptionAddr, true, "exn_val");
221 ExnVal = Builder.CreateIntToPtr(ExnVal, Type::getInt8PtrTy(F.getContext()));
222 Value *SelVal = Builder.CreateLoad(SelectorAddr, true, "exn_selector_val");
224 substituteLPadValues(LPI, ExnVal, SelVal, Builder);
227 // Personality function
228 Idxs[1] = ConstantInt::get(Int32Ty, 3);
230 PersonalityFn = LPads[0]->getPersonalityFn();
231 Value *PersonalityFieldPtr =
232 GetElementPtrInst::Create(FuncCtx, Idxs, "pers_fn_gep",
233 EntryBB->getTerminator());
234 new StoreInst(PersonalityFn, PersonalityFieldPtr, true,
235 EntryBB->getTerminator());
238 Idxs[1] = ConstantInt::get(Int32Ty, 4);
239 Value *LSDAFieldPtr = GetElementPtrInst::Create(FuncCtx, Idxs, "lsda_gep",
240 EntryBB->getTerminator());
241 Value *LSDA = CallInst::Create(LSDAAddrFn, "lsda_addr",
242 EntryBB->getTerminator());
243 new StoreInst(LSDA, LSDAFieldPtr, true, EntryBB->getTerminator());
248 /// lowerIncomingArguments - To avoid having to handle incoming arguments
249 /// specially, we lower each arg to a copy instruction in the entry block. This
250 /// ensures that the argument value itself cannot be live out of the entry
252 void SjLjEHPass::lowerIncomingArguments(Function &F) {
253 BasicBlock::iterator AfterAllocaInsPt = F.begin()->begin();
254 while (isa<AllocaInst>(AfterAllocaInsPt) &&
255 isa<ConstantInt>(cast<AllocaInst>(AfterAllocaInsPt)->getArraySize()))
258 for (Function::arg_iterator
259 AI = F.arg_begin(), AE = F.arg_end(); AI != AE; ++AI) {
260 Type *Ty = AI->getType();
262 // Aggregate types can't be cast, but are legal argument types, so we have
263 // to handle them differently. We use an extract/insert pair as a
264 // lightweight method to achieve the same goal.
265 if (isa<StructType>(Ty) || isa<ArrayType>(Ty) || isa<VectorType>(Ty)) {
266 Instruction *EI = ExtractValueInst::Create(AI, 0, "", AfterAllocaInsPt);
267 Instruction *NI = InsertValueInst::Create(AI, EI, 0);
269 AI->replaceAllUsesWith(NI);
271 // Set the operand of the instructions back to the AllocaInst.
272 EI->setOperand(0, AI);
273 NI->setOperand(0, AI);
275 // This is always a no-op cast because we're casting AI to AI->getType()
276 // so src and destination types are identical. BitCast is the only
279 new BitCastInst(AI, AI->getType(), AI->getName() + ".tmp",
281 AI->replaceAllUsesWith(NC);
283 // Set the operand of the cast instruction back to the AllocaInst.
284 // Normally it's forbidden to replace a CastInst's operand because it
285 // could cause the opcode to reflect an illegal conversion. However, we're
286 // replacing it here with the same value it was constructed with. We do
287 // this because the above replaceAllUsesWith() clobbered the operand, but
288 // we want this one to remain.
289 NC->setOperand(0, AI);
294 /// lowerAcrossUnwindEdges - Find all variables which are alive across an unwind
295 /// edge and spill them.
296 void SjLjEHPass::lowerAcrossUnwindEdges(Function &F,
297 ArrayRef<InvokeInst*> Invokes) {
298 // Finally, scan the code looking for instructions with bad live ranges.
299 for (Function::iterator
300 BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
301 for (BasicBlock::iterator
302 II = BB->begin(), IIE = BB->end(); II != IIE; ++II) {
303 // Ignore obvious cases we don't have to handle. In particular, most
304 // instructions either have no uses or only have a single use inside the
305 // current block. Ignore them quickly.
306 Instruction *Inst = II;
307 if (Inst->use_empty()) continue;
308 if (Inst->hasOneUse() &&
309 cast<Instruction>(Inst->use_back())->getParent() == BB &&
310 !isa<PHINode>(Inst->use_back())) continue;
312 // If this is an alloca in the entry block, it's not a real register
314 if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
315 if (isa<ConstantInt>(AI->getArraySize()) && BB == F.begin())
318 // Avoid iterator invalidation by copying users to a temporary vector.
319 SmallVector<Instruction*, 16> Users;
320 for (Value::use_iterator
321 UI = Inst->use_begin(), E = Inst->use_end(); UI != E; ++UI) {
322 Instruction *User = cast<Instruction>(*UI);
323 if (User->getParent() != BB || isa<PHINode>(User))
324 Users.push_back(User);
327 // Find all of the blocks that this value is live in.
328 SmallPtrSet<BasicBlock*, 64> LiveBBs;
329 LiveBBs.insert(Inst->getParent());
330 while (!Users.empty()) {
331 Instruction *U = Users.back();
334 if (!isa<PHINode>(U)) {
335 MarkBlocksLiveIn(U->getParent(), LiveBBs);
337 // Uses for a PHI node occur in their predecessor block.
338 PHINode *PN = cast<PHINode>(U);
339 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
340 if (PN->getIncomingValue(i) == Inst)
341 MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs);
345 // Now that we know all of the blocks that this thing is live in, see if
346 // it includes any of the unwind locations.
347 bool NeedsSpill = false;
348 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) {
349 BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest();
350 if (UnwindBlock != BB && LiveBBs.count(UnwindBlock)) {
356 // If we decided we need a spill, do it.
357 // FIXME: Spilling this way is overkill, as it forces all uses of
358 // the value to be reloaded from the stack slot, even those that aren't
359 // in the unwind blocks. We should be more selective.
361 DemoteRegToStack(*Inst, true);
367 // Go through the landing pads and remove any PHIs there.
368 for (unsigned i = 0, e = Invokes.size(); i != e; ++i) {
369 BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest();
370 LandingPadInst *LPI = UnwindBlock->getLandingPadInst();
372 // Place PHIs into a set to avoid invalidating the iterator.
373 SmallPtrSet<PHINode*, 8> PHIsToDemote;
374 for (BasicBlock::iterator
375 PN = UnwindBlock->begin(); isa<PHINode>(PN); ++PN)
376 PHIsToDemote.insert(cast<PHINode>(PN));
377 if (PHIsToDemote.empty()) continue;
379 // Demote the PHIs to the stack.
380 for (SmallPtrSet<PHINode*, 8>::iterator
381 I = PHIsToDemote.begin(), E = PHIsToDemote.end(); I != E; ++I)
382 DemotePHIToStack(*I);
384 // Move the landingpad instruction back to the top of the landing pad block.
385 LPI->moveBefore(UnwindBlock->begin());
389 /// setupEntryBlockAndCallSites - Setup the entry block by creating and filling
390 /// the function context and marking the call sites with the appropriate
391 /// values. These values are used by the DWARF EH emitter.
392 bool SjLjEHPass::setupEntryBlockAndCallSites(Function &F) {
393 SmallVector<ReturnInst*, 16> Returns;
394 SmallVector<InvokeInst*, 16> Invokes;
395 SmallSetVector<LandingPadInst*, 16> LPads;
397 // Look through the terminators of the basic blocks to find invokes.
398 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
399 if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
400 Invokes.push_back(II);
401 LPads.insert(II->getUnwindDest()->getLandingPadInst());
402 } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
403 Returns.push_back(RI);
406 if (Invokes.empty()) return false;
408 NumInvokes += Invokes.size();
410 lowerIncomingArguments(F);
411 lowerAcrossUnwindEdges(F, Invokes);
414 setupFunctionContext(F, makeArrayRef(LPads.begin(), LPads.end()));
415 BasicBlock *EntryBB = F.begin();
416 Type *Int32Ty = Type::getInt32Ty(F.getContext());
419 ConstantInt::get(Int32Ty, 0), 0
422 // Get a reference to the jump buffer.
423 Idxs[1] = ConstantInt::get(Int32Ty, 5);
424 Value *JBufPtr = GetElementPtrInst::Create(FuncCtx, Idxs, "jbuf_gep",
425 EntryBB->getTerminator());
427 // Save the frame pointer.
428 Idxs[1] = ConstantInt::get(Int32Ty, 0);
429 Value *FramePtr = GetElementPtrInst::Create(JBufPtr, Idxs, "jbuf_fp_gep",
430 EntryBB->getTerminator());
432 Value *Val = CallInst::Create(FrameAddrFn,
433 ConstantInt::get(Int32Ty, 0),
435 EntryBB->getTerminator());
436 new StoreInst(Val, FramePtr, true, EntryBB->getTerminator());
438 // Save the stack pointer.
439 Idxs[1] = ConstantInt::get(Int32Ty, 2);
440 Value *StackPtr = GetElementPtrInst::Create(JBufPtr, Idxs, "jbuf_sp_gep",
441 EntryBB->getTerminator());
443 Val = CallInst::Create(StackAddrFn, "sp", EntryBB->getTerminator());
444 new StoreInst(Val, StackPtr, true, EntryBB->getTerminator());
446 // Call the setjmp instrinsic. It fills in the rest of the jmpbuf.
447 Value *SetjmpArg = CastInst::Create(Instruction::BitCast, JBufPtr,
448 Type::getInt8PtrTy(F.getContext()), "",
449 EntryBB->getTerminator());
450 CallInst::Create(BuiltinSetjmpFn, SetjmpArg, "", EntryBB->getTerminator());
452 // Store a pointer to the function context so that the back-end will know
453 // where to look for it.
454 Value *FuncCtxArg = CastInst::Create(Instruction::BitCast, FuncCtx,
455 Type::getInt8PtrTy(F.getContext()), "",
456 EntryBB->getTerminator());
457 CallInst::Create(FuncCtxFn, FuncCtxArg, "", EntryBB->getTerminator());
459 // At this point, we are all set up, update the invoke instructions to mark
460 // their call_site values.
461 for (unsigned I = 0, E = Invokes.size(); I != E; ++I) {
462 insertCallSiteStore(Invokes[I], I + 1, CallSite);
464 ConstantInt *CallSiteNum =
465 ConstantInt::get(Type::getInt32Ty(F.getContext()), I + 1);
467 // Record the call site value for the back end so it stays associated with
469 CallInst::Create(CallSiteFn, CallSiteNum, "", Invokes[I]);
472 // Mark call instructions that aren't nounwind as no-action (call_site ==
473 // -1). Skip the entry block, as prior to then, no function context has been
474 // created for this function and any unexpected exceptions thrown will go
475 // directly to the caller's context, which is what we want anyway, so no need
476 // to do anything here.
477 for (Function::iterator BB = F.begin(), E = F.end(); ++BB != E;)
478 for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I)
479 if (CallInst *CI = dyn_cast<CallInst>(I)) {
480 if (!CI->doesNotThrow())
481 insertCallSiteStore(CI, -1, CallSite);
482 } else if (ResumeInst *RI = dyn_cast<ResumeInst>(I)) {
483 insertCallSiteStore(RI, -1, CallSite);
486 // Register the function context and make sure it's known to not throw
487 CallInst *Register = CallInst::Create(RegisterFn, FuncCtx, "",
488 EntryBB->getTerminator());
489 Register->setDoesNotThrow();
491 // Following any allocas not in the entry block, update the saved SP in the
492 // jmpbuf to the new value.
493 for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
496 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
497 if (CallInst *CI = dyn_cast<CallInst>(I)) {
498 if (CI->getCalledFunction() != StackRestoreFn)
500 } else if (!isa<AllocaInst>(I)) {
503 Instruction *StackAddr = CallInst::Create(StackAddrFn, "sp");
504 StackAddr->insertAfter(I);
505 Instruction *StoreStackAddr = new StoreInst(StackAddr, StackPtr, true);
506 StoreStackAddr->insertAfter(StackAddr);
510 // Finally, for any returns from this function, if this function contains an
511 // invoke, add a call to unregister the function context.
512 for (unsigned I = 0, E = Returns.size(); I != E; ++I)
513 CallInst::Create(UnregisterFn, FuncCtx, "", Returns[I]);
518 bool SjLjEHPass::runOnFunction(Function &F) {
519 bool Res = setupEntryBlockAndCallSites(F);