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