SjLjEHPrepare.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338 
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 {
45class SjLjEHPrepare : public FunctionPass {
46  const TargetMachine *TM;
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
60public:
61  static char ID; // Pass identification, replacement for typeid
62  explicit SjLjEHPrepare(const TargetMachine *TM) : FunctionPass(ID), TM(TM) {}
63  bool doInitialization(Module &M) override;
64  bool runOnFunction(Function &F) override;
65
66  void getAnalysisUsage(AnalysisUsage &AU) const override {}
67  const char *getPassName() const override {
68    return "SJLJ Exception Handling preparation";
69  }
70
71private:
72  bool setupEntryBlockAndCallSites(Function &F);
73  void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, 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);
78};
79} // end anonymous namespace
80
81char SjLjEHPrepare::ID = 0;
82
83// Public Interface To the SjLjEHPrepare pass.
84FunctionPass *llvm::createSjLjEHPreparePass(const TargetMachine *TM) {
85  return new SjLjEHPrepare(TM);
86}
87// doInitialization - Set up decalarations and types needed to process
88// exceptions.
89bool SjLjEHPrepare::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 = StructType::get(VoidPtrTy,                  // __prev
95                                      Int32Ty,                    // call_site
96                                      ArrayType::get(Int32Ty, 4), // __data
97                                      VoidPtrTy, // __personality
98                                      VoidPtrTy, // __lsda
99                                      ArrayType::get(VoidPtrTy, 5), // __jbuf
100                                      NULL);
101  RegisterFn = M.getOrInsertFunction(
102      "_Unwind_SjLj_Register", Type::getVoidTy(M.getContext()),
103      PointerType::getUnqual(FunctionContextTy), (Type *)0);
104  UnregisterFn = M.getOrInsertFunction(
105      "_Unwind_SjLj_Unregister", Type::getVoidTy(M.getContext()),
106      PointerType::getUnqual(FunctionContextTy), (Type *)0);
107  FrameAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::frameaddress);
108  StackAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::stacksave);
109  StackRestoreFn = Intrinsic::getDeclaration(&M, Intrinsic::stackrestore);
110  BuiltinSetjmpFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_setjmp);
111  LSDAAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_lsda);
112  CallSiteFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_callsite);
113  FuncCtxFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_functioncontext);
114  PersonalityFn = 0;
115
116  return true;
117}
118
119/// insertCallSiteStore - Insert a store of the call-site value to the
120/// function context
121void SjLjEHPrepare::insertCallSiteStore(Instruction *I, int Number) {
122  IRBuilder<> Builder(I);
123
124  // Get a reference to the call_site field.
125  Type *Int32Ty = Type::getInt32Ty(I->getContext());
126  Value *Zero = ConstantInt::get(Int32Ty, 0);
127  Value *One = ConstantInt::get(Int32Ty, 1);
128  Value *Idxs[2] = { Zero, One };
129  Value *CallSite = Builder.CreateGEP(FuncCtx, Idxs, "call_site");
130
131  // Insert a store of the call-site number
132  ConstantInt *CallSiteNoC =
133      ConstantInt::get(Type::getInt32Ty(I->getContext()), Number);
134  Builder.CreateStore(CallSiteNoC, CallSite, true /*volatile*/);
135}
136
137/// MarkBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until
138/// we reach blocks we've already seen.
139static void MarkBlocksLiveIn(BasicBlock *BB,
140                             SmallPtrSet<BasicBlock *, 64> &LiveBBs) {
141  if (!LiveBBs.insert(BB))
142    return; // already been here.
143
144  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
145    MarkBlocksLiveIn(*PI, LiveBBs);
146}
147
148/// substituteLPadValues - Substitute the values returned by the landingpad
149/// instruction with those returned by the personality function.
150void SjLjEHPrepare::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal,
151                                         Value *SelVal) {
152  SmallVector<Value *, 8> UseWorkList(LPI->user_begin(), LPI->user_end());
153  while (!UseWorkList.empty()) {
154    Value *Val = UseWorkList.pop_back_val();
155    ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val);
156    if (!EVI)
157      continue;
158    if (EVI->getNumIndices() != 1)
159      continue;
160    if (*EVI->idx_begin() == 0)
161      EVI->replaceAllUsesWith(ExnVal);
162    else if (*EVI->idx_begin() == 1)
163      EVI->replaceAllUsesWith(SelVal);
164    if (EVI->getNumUses() == 0)
165      EVI->eraseFromParent();
166  }
167
168  if (LPI->getNumUses() == 0)
169    return;
170
171  // There are still some uses of LPI. Construct an aggregate with the exception
172  // values and replace the LPI with that aggregate.
173  Type *LPadType = LPI->getType();
174  Value *LPadVal = UndefValue::get(LPadType);
175  IRBuilder<> Builder(
176      std::next(BasicBlock::iterator(cast<Instruction>(SelVal))));
177  LPadVal = Builder.CreateInsertValue(LPadVal, ExnVal, 0, "lpad.val");
178  LPadVal = Builder.CreateInsertValue(LPadVal, SelVal, 1, "lpad.val");
179
180  LPI->replaceAllUsesWith(LPadVal);
181}
182
183/// setupFunctionContext - Allocate the function context on the stack and fill
184/// it with all of the data that we know at this point.
185Value *SjLjEHPrepare::setupFunctionContext(Function &F,
186                                           ArrayRef<LandingPadInst *> LPads) {
187  BasicBlock *EntryBB = F.begin();
188
189  // Create an alloca for the incoming jump buffer ptr and the new jump buffer
190  // that needs to be restored on all exits from the function. This is an alloca
191  // because the value needs to be added to the global context list.
192  const TargetLowering *TLI = TM->getTargetLowering();
193  unsigned Align =
194      TLI->getDataLayout()->getPrefTypeAlignment(FunctionContextTy);
195  FuncCtx = new AllocaInst(FunctionContextTy, 0, Align, "fn_context",
196                           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 =
208        Builder.CreateConstGEP2_32(FCData, 0, 0, "exception_gep");
209    Value *ExnVal = Builder.CreateLoad(ExceptionAddr, true, "exn_val");
210    ExnVal = Builder.CreateIntToPtr(ExnVal, Builder.getInt8PtrTy());
211
212    Value *SelectorAddr =
213        Builder.CreateConstGEP2_32(FCData, 0, 1, "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 =
224      Builder.CreateConstGEP2_32(FuncCtx, 0, 3, "pers_fn_gep");
225  Builder.CreateStore(
226      Builder.CreateBitCast(PersonalityFn, 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 AI = F.arg_begin(), AE = F.arg_end(); AI != AE;
248       ++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)) {
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 = new BitCastInst(AI, AI->getType(), AI->getName() + ".tmp",
268                                     AfterAllocaInsPt);
269      AI->replaceAllUsesWith(NC);
270
271      // Set the operand of the cast instruction back to the AllocaInst.
272      // Normally it's forbidden to replace a CastInst's operand because it
273      // could cause the opcode to reflect an illegal conversion. However, we're
274      // replacing it here with the same value it was constructed with.  We do
275      // this because the above replaceAllUsesWith() clobbered the operand, but
276      // we want this one to remain.
277      NC->setOperand(0, AI);
278    }
279  }
280}
281
282/// lowerAcrossUnwindEdges - Find all variables which are alive across an unwind
283/// edge and spill them.
284void SjLjEHPrepare::lowerAcrossUnwindEdges(Function &F,
285                                           ArrayRef<InvokeInst *> Invokes) {
286  // Finally, scan the code looking for instructions with bad live ranges.
287  for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
288    for (BasicBlock::iterator II = BB->begin(), IIE = BB->end(); II != IIE;
289         ++II) {
290      // Ignore obvious cases we don't have to handle. In particular, most
291      // instructions either have no uses or only have a single use inside the
292      // current block. Ignore them quickly.
293      Instruction *Inst = II;
294      if (Inst->use_empty())
295        continue;
296      if (Inst->hasOneUse() &&
297          cast<Instruction>(Inst->user_back())->getParent() == BB &&
298          !isa<PHINode>(Inst->user_back()))
299        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 (User *U : Inst->users()) {
310        Instruction *UI = cast<Instruction>(U);
311        if (UI->getParent() != BB || isa<PHINode>(UI))
312          Users.push_back(UI);
313      }
314
315      // Find all of the blocks that this value is live in.
316      SmallPtrSet<BasicBlock *, 64> LiveBBs;
317      LiveBBs.insert(Inst->getParent());
318      while (!Users.empty()) {
319        Instruction *U = Users.back();
320        Users.pop_back();
321
322        if (!isa<PHINode>(U)) {
323          MarkBlocksLiveIn(U->getParent(), LiveBBs);
324        } else {
325          // Uses for a PHI node occur in their predecessor block.
326          PHINode *PN = cast<PHINode>(U);
327          for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
328            if (PN->getIncomingValue(i) == Inst)
329              MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs);
330        }
331      }
332
333      // Now that we know all of the blocks that this thing is live in, see if
334      // it includes any of the unwind locations.
335      bool NeedsSpill = false;
336      for (unsigned i = 0, e = Invokes.size(); i != e; ++i) {
337        BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest();
338        if (UnwindBlock != BB && LiveBBs.count(UnwindBlock)) {
339          DEBUG(dbgs() << "SJLJ Spill: " << *Inst << " around "
340                       << UnwindBlock->getName() << "\n");
341          NeedsSpill = true;
342          break;
343        }
344      }
345
346      // If we decided we need a spill, do it.
347      // FIXME: Spilling this way is overkill, as it forces all uses of
348      // the value to be reloaded from the stack slot, even those that aren't
349      // in the unwind blocks. We should be more selective.
350      if (NeedsSpill) {
351        DemoteRegToStack(*Inst, true);
352        ++NumSpilled;
353      }
354    }
355  }
356
357  // Go through the landing pads and remove any PHIs there.
358  for (unsigned i = 0, e = Invokes.size(); i != e; ++i) {
359    BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest();
360    LandingPadInst *LPI = UnwindBlock->getLandingPadInst();
361
362    // Place PHIs into a set to avoid invalidating the iterator.
363    SmallPtrSet<PHINode *, 8> PHIsToDemote;
364    for (BasicBlock::iterator PN = UnwindBlock->begin(); isa<PHINode>(PN); ++PN)
365      PHIsToDemote.insert(cast<PHINode>(PN));
366    if (PHIsToDemote.empty())
367      continue;
368
369    // Demote the PHIs to the stack.
370    for (SmallPtrSet<PHINode *, 8>::iterator I = PHIsToDemote.begin(),
371                                             E = PHIsToDemote.end();
372         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())
407    return false;
408
409  NumInvokes += Invokes.size();
410
411  lowerIncomingArguments(F);
412  lowerAcrossUnwindEdges(F, Invokes);
413
414  Value *FuncCtx =
415      setupFunctionContext(F, makeArrayRef(LPads.begin(), LPads.end()));
416  BasicBlock *EntryBB = F.begin();
417  IRBuilder<> Builder(EntryBB->getTerminator());
418
419  // Get a reference to the jump buffer.
420  Value *JBufPtr = Builder.CreateConstGEP2_32(FuncCtx, 0, 5, "jbuf_gep");
421
422  // Save the frame pointer.
423  Value *FramePtr = Builder.CreateConstGEP2_32(JBufPtr, 0, 0, "jbuf_fp_gep");
424
425  Value *Val = Builder.CreateCall(FrameAddrFn, Builder.getInt32(0), "fp");
426  Builder.CreateStore(Val, FramePtr, /*isVolatile=*/true);
427
428  // Save the stack pointer.
429  Value *StackPtr = Builder.CreateConstGEP2_32(JBufPtr, 0, 2, "jbuf_sp_gep");
430
431  Val = Builder.CreateCall(StackAddrFn, "sp");
432  Builder.CreateStore(Val, StackPtr, /*isVolatile=*/true);
433
434  // Call the setjmp instrinsic. It fills in the rest of the jmpbuf.
435  Value *SetjmpArg = Builder.CreateBitCast(JBufPtr, Builder.getInt8PtrTy());
436  Builder.CreateCall(BuiltinSetjmpFn, SetjmpArg);
437
438  // Store a pointer to the function context so that the back-end will know
439  // where to look for it.
440  Value *FuncCtxArg = Builder.CreateBitCast(FuncCtx, Builder.getInt8PtrTy());
441  Builder.CreateCall(FuncCtxFn, FuncCtxArg);
442
443  // At this point, we are all set up, update the invoke instructions to mark
444  // their call_site values.
445  for (unsigned I = 0, E = Invokes.size(); I != E; ++I) {
446    insertCallSiteStore(Invokes[I], I + 1);
447
448    ConstantInt *CallSiteNum =
449        ConstantInt::get(Type::getInt32Ty(F.getContext()), I + 1);
450
451    // Record the call site value for the back end so it stays associated with
452    // the invoke.
453    CallInst::Create(CallSiteFn, CallSiteNum, "", Invokes[I]);
454  }
455
456  // Mark call instructions that aren't nounwind as no-action (call_site ==
457  // -1). Skip the entry block, as prior to then, no function context has been
458  // created for this function and any unexpected exceptions thrown will go
459  // directly to the caller's context, which is what we want anyway, so no need
460  // to do anything here.
461  for (Function::iterator BB = F.begin(), E = F.end(); ++BB != E;)
462    for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I)
463      if (CallInst *CI = dyn_cast<CallInst>(I)) {
464        if (!CI->doesNotThrow())
465          insertCallSiteStore(CI, -1);
466      } else if (ResumeInst *RI = dyn_cast<ResumeInst>(I)) {
467        insertCallSiteStore(RI, -1);
468      }
469
470  // Register the function context and make sure it's known to not throw
471  CallInst *Register =
472      CallInst::Create(RegisterFn, FuncCtx, "", EntryBB->getTerminator());
473  Register->setDoesNotThrow();
474
475  // Following any allocas not in the entry block, update the saved SP in the
476  // jmpbuf to the new value.
477  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
478    if (BB == F.begin())
479      continue;
480    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
481      if (CallInst *CI = dyn_cast<CallInst>(I)) {
482        if (CI->getCalledFunction() != StackRestoreFn)
483          continue;
484      } else if (!isa<AllocaInst>(I)) {
485        continue;
486      }
487      Instruction *StackAddr = CallInst::Create(StackAddrFn, "sp");
488      StackAddr->insertAfter(I);
489      Instruction *StoreStackAddr = new StoreInst(StackAddr, StackPtr, true);
490      StoreStackAddr->insertAfter(StackAddr);
491    }
492  }
493
494  // Finally, for any returns from this function, if this function contains an
495  // invoke, add a call to unregister the function context.
496  for (unsigned I = 0, E = Returns.size(); I != E; ++I)
497    CallInst::Create(UnregisterFn, FuncCtx, "", Returns[I]);
498
499  return true;
500}
501
502bool SjLjEHPrepare::runOnFunction(Function &F) {
503  bool Res = setupEntryBlockAndCallSites(F);
504  return Res;
505}
506