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