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