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#include "llvm/CodeGen/Passes.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/SetVector.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/IR/Constants.h"
22#include "llvm/IR/DataLayout.h"
23#include "llvm/IR/DerivedTypes.h"
24#include "llvm/IR/IRBuilder.h"
25#include "llvm/IR/Instructions.h"
26#include "llvm/IR/Intrinsics.h"
27#include "llvm/IR/LLVMContext.h"
28#include "llvm/IR/Module.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/raw_ostream.h"
33#include "llvm/Target/TargetLowering.h"
34#include "llvm/Transforms/Scalar.h"
35#include "llvm/Transforms/Utils/BasicBlockUtils.h"
36#include "llvm/Transforms/Utils/Local.h"
37#include <set>
38using namespace llvm;
39
40#define DEBUG_TYPE "sjljehprepare"
41
42STATISTIC(NumInvokes, "Number of invokes replaced");
43STATISTIC(NumSpilled, "Number of registers live across unwind edges");
44
45namespace {
46class SjLjEHPrepare : public FunctionPass {
47  const TargetMachine *TM;
48  Type *FunctionContextTy;
49  Constant *RegisterFn;
50  Constant *UnregisterFn;
51  Constant *BuiltinSetjmpFn;
52  Constant *FrameAddrFn;
53  Constant *StackAddrFn;
54  Constant *StackRestoreFn;
55  Constant *LSDAAddrFn;
56  Value *PersonalityFn;
57  Constant *CallSiteFn;
58  Constant *FuncCtxFn;
59  AllocaInst *FuncCtx;
60
61public:
62  static char ID; // Pass identification, replacement for typeid
63  explicit SjLjEHPrepare(const TargetMachine *TM) : FunctionPass(ID), TM(TM) {}
64  bool doInitialization(Module &M) override;
65  bool runOnFunction(Function &F) override;
66
67  void getAnalysisUsage(AnalysisUsage &AU) const override {}
68  const char *getPassName() const override {
69    return "SJLJ Exception Handling preparation";
70  }
71
72private:
73  bool setupEntryBlockAndCallSites(Function &F);
74  void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, 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 TargetMachine *TM) {
86  return new SjLjEHPrepare(TM);
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 = 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(
103      "_Unwind_SjLj_Register", Type::getVoidTy(M.getContext()),
104      PointerType::getUnqual(FunctionContextTy), (Type *)nullptr);
105  UnregisterFn = M.getOrInsertFunction(
106      "_Unwind_SjLj_Unregister", Type::getVoidTy(M.getContext()),
107      PointerType::getUnqual(FunctionContextTy), (Type *)nullptr);
108  FrameAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::frameaddress);
109  StackAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::stacksave);
110  StackRestoreFn = Intrinsic::getDeclaration(&M, Intrinsic::stackrestore);
111  BuiltinSetjmpFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_setjmp);
112  LSDAAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_lsda);
113  CallSiteFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_callsite);
114  FuncCtxFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_functioncontext);
115  PersonalityFn = nullptr;
116
117  return true;
118}
119
120/// insertCallSiteStore - Insert a store of the call-site value to the
121/// function context
122void SjLjEHPrepare::insertCallSiteStore(Instruction *I, int Number) {
123  IRBuilder<> Builder(I);
124
125  // Get a reference to the call_site field.
126  Type *Int32Ty = Type::getInt32Ty(I->getContext());
127  Value *Zero = ConstantInt::get(Int32Ty, 0);
128  Value *One = ConstantInt::get(Int32Ty, 1);
129  Value *Idxs[2] = { Zero, One };
130  Value *CallSite = Builder.CreateGEP(FuncCtx, Idxs, "call_site");
131
132  // Insert a store of the call-site number
133  ConstantInt *CallSiteNoC =
134      ConstantInt::get(Type::getInt32Ty(I->getContext()), Number);
135  Builder.CreateStore(CallSiteNoC, CallSite, true /*volatile*/);
136}
137
138/// MarkBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until
139/// we reach blocks we've already seen.
140static void MarkBlocksLiveIn(BasicBlock *BB,
141                             SmallPtrSet<BasicBlock *, 64> &LiveBBs) {
142  if (!LiveBBs.insert(BB))
143    return; // already been here.
144
145  for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
146    MarkBlocksLiveIn(*PI, LiveBBs);
147}
148
149/// substituteLPadValues - Substitute the values returned by the landingpad
150/// instruction with those returned by the personality function.
151void SjLjEHPrepare::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal,
152                                         Value *SelVal) {
153  SmallVector<Value *, 8> UseWorkList(LPI->user_begin(), LPI->user_end());
154  while (!UseWorkList.empty()) {
155    Value *Val = UseWorkList.pop_back_val();
156    ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(Val);
157    if (!EVI)
158      continue;
159    if (EVI->getNumIndices() != 1)
160      continue;
161    if (*EVI->idx_begin() == 0)
162      EVI->replaceAllUsesWith(ExnVal);
163    else if (*EVI->idx_begin() == 1)
164      EVI->replaceAllUsesWith(SelVal);
165    if (EVI->getNumUses() == 0)
166      EVI->eraseFromParent();
167  }
168
169  if (LPI->getNumUses() == 0)
170    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<> Builder(
177      std::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::setupFunctionContext(Function &F,
187                                           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  const TargetLowering *TLI = TM->getTargetLowering();
194  unsigned Align =
195      TLI->getDataLayout()->getPrefTypeAlignment(FunctionContextTy);
196  FuncCtx = new AllocaInst(FunctionContextTy, nullptr, Align, "fn_context",
197                           EntryBB->begin());
198
199  // Fill in the function context structure.
200  for (unsigned I = 0, E = LPads.size(); I != E; ++I) {
201    LandingPadInst *LPI = LPads[I];
202    IRBuilder<> Builder(LPI->getParent()->getFirstInsertionPt());
203
204    // Reference the __data field.
205    Value *FCData = Builder.CreateConstGEP2_32(FuncCtx, 0, 2, "__data");
206
207    // The exception values come back in context->__data[0].
208    Value *ExceptionAddr =
209        Builder.CreateConstGEP2_32(FCData, 0, 0, "exception_gep");
210    Value *ExnVal = Builder.CreateLoad(ExceptionAddr, true, "exn_val");
211    ExnVal = Builder.CreateIntToPtr(ExnVal, Builder.getInt8PtrTy());
212
213    Value *SelectorAddr =
214        Builder.CreateConstGEP2_32(FCData, 0, 1, "exn_selector_gep");
215    Value *SelVal = Builder.CreateLoad(SelectorAddr, true, "exn_selector_val");
216
217    substituteLPadValues(LPI, ExnVal, SelVal);
218  }
219
220  // Personality function
221  IRBuilder<> Builder(EntryBB->getTerminator());
222  if (!PersonalityFn)
223    PersonalityFn = LPads[0]->getPersonalityFn();
224  Value *PersonalityFieldPtr =
225      Builder.CreateConstGEP2_32(FuncCtx, 0, 3, "pers_fn_gep");
226  Builder.CreateStore(
227      Builder.CreateBitCast(PersonalityFn, Builder.getInt8PtrTy()),
228      PersonalityFieldPtr, /*isVolatile=*/true);
229
230  // LSDA address
231  Value *LSDA = Builder.CreateCall(LSDAAddrFn, "lsda_addr");
232  Value *LSDAFieldPtr = Builder.CreateConstGEP2_32(FuncCtx, 0, 4, "lsda_gep");
233  Builder.CreateStore(LSDA, LSDAFieldPtr, /*isVolatile=*/true);
234
235  return FuncCtx;
236}
237
238/// lowerIncomingArguments - To avoid having to handle incoming arguments
239/// specially, we lower each arg to a copy instruction in the entry block. This
240/// ensures that the argument value itself cannot be live out of the entry
241/// block.
242void SjLjEHPrepare::lowerIncomingArguments(Function &F) {
243  BasicBlock::iterator AfterAllocaInsPt = F.begin()->begin();
244  while (isa<AllocaInst>(AfterAllocaInsPt) &&
245         isa<ConstantInt>(cast<AllocaInst>(AfterAllocaInsPt)->getArraySize()))
246    ++AfterAllocaInsPt;
247
248  for (Function::arg_iterator AI = F.arg_begin(), AE = F.arg_end(); AI != AE;
249       ++AI) {
250    Type *Ty = AI->getType();
251
252    // Aggregate types can't be cast, but are legal argument types, so we have
253    // to handle them differently. We use an extract/insert pair as a
254    // lightweight method to achieve the same goal.
255    if (isa<StructType>(Ty) || isa<ArrayType>(Ty)) {
256      Instruction *EI = ExtractValueInst::Create(AI, 0, "", AfterAllocaInsPt);
257      Instruction *NI = InsertValueInst::Create(AI, EI, 0);
258      NI->insertAfter(EI);
259      AI->replaceAllUsesWith(NI);
260
261      // Set the operand of the instructions back to the AllocaInst.
262      EI->setOperand(0, AI);
263      NI->setOperand(0, AI);
264    } else {
265      // This is always a no-op cast because we're casting AI to AI->getType()
266      // so src and destination types are identical. BitCast is the only
267      // possibility.
268      CastInst *NC = 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 BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) {
289    for (BasicBlock::iterator II = BB->begin(), IIE = BB->end(); II != IIE;
290         ++II) {
291      // Ignore obvious cases we don't have to handle. In particular, most
292      // instructions either have no uses or only have a single use inside the
293      // current block. Ignore them quickly.
294      Instruction *Inst = II;
295      if (Inst->use_empty())
296        continue;
297      if (Inst->hasOneUse() &&
298          cast<Instruction>(Inst->user_back())->getParent() == BB &&
299          !isa<PHINode>(Inst->user_back()))
300        continue;
301
302      // If this is an alloca in the entry block, it's not a real register
303      // value.
304      if (AllocaInst *AI = dyn_cast<AllocaInst>(Inst))
305        if (isa<ConstantInt>(AI->getArraySize()) && BB == F.begin())
306          continue;
307
308      // Avoid iterator invalidation by copying users to a temporary vector.
309      SmallVector<Instruction *, 16> Users;
310      for (User *U : Inst->users()) {
311        Instruction *UI = cast<Instruction>(U);
312        if (UI->getParent() != BB || isa<PHINode>(UI))
313          Users.push_back(UI);
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 PN = UnwindBlock->begin(); isa<PHINode>(PN); ++PN)
366      PHIsToDemote.insert(cast<PHINode>(PN));
367    if (PHIsToDemote.empty())
368      continue;
369
370    // Demote the PHIs to the stack.
371    for (SmallPtrSet<PHINode *, 8>::iterator I = PHIsToDemote.begin(),
372                                             E = PHIsToDemote.end();
373         I != E; ++I)
374      DemotePHIToStack(*I);
375
376    // Move the landingpad instruction back to the top of the landing pad block.
377    LPI->moveBefore(UnwindBlock->begin());
378  }
379}
380
381/// setupEntryBlockAndCallSites - Setup the entry block by creating and filling
382/// the function context and marking the call sites with the appropriate
383/// values. These values are used by the DWARF EH emitter.
384bool SjLjEHPrepare::setupEntryBlockAndCallSites(Function &F) {
385  SmallVector<ReturnInst *, 16> Returns;
386  SmallVector<InvokeInst *, 16> Invokes;
387  SmallSetVector<LandingPadInst *, 16> LPads;
388
389  // Look through the terminators of the basic blocks to find invokes.
390  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
391    if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
392      if (Function *Callee = II->getCalledFunction())
393        if (Callee->isIntrinsic() &&
394            Callee->getIntrinsicID() == Intrinsic::donothing) {
395          // Remove the NOP invoke.
396          BranchInst::Create(II->getNormalDest(), II);
397          II->eraseFromParent();
398          continue;
399        }
400
401      Invokes.push_back(II);
402      LPads.insert(II->getUnwindDest()->getLandingPadInst());
403    } else if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) {
404      Returns.push_back(RI);
405    }
406
407  if (Invokes.empty())
408    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  IRBuilder<> Builder(EntryBB->getTerminator());
419
420  // Get a reference to the jump buffer.
421  Value *JBufPtr = Builder.CreateConstGEP2_32(FuncCtx, 0, 5, "jbuf_gep");
422
423  // Save the frame pointer.
424  Value *FramePtr = Builder.CreateConstGEP2_32(JBufPtr, 0, 0, "jbuf_fp_gep");
425
426  Value *Val = Builder.CreateCall(FrameAddrFn, Builder.getInt32(0), "fp");
427  Builder.CreateStore(Val, FramePtr, /*isVolatile=*/true);
428
429  // Save the stack pointer.
430  Value *StackPtr = Builder.CreateConstGEP2_32(JBufPtr, 0, 2, "jbuf_sp_gep");
431
432  Val = Builder.CreateCall(StackAddrFn, "sp");
433  Builder.CreateStore(Val, StackPtr, /*isVolatile=*/true);
434
435  // Call the setjmp instrinsic. It fills in the rest of the jmpbuf.
436  Value *SetjmpArg = Builder.CreateBitCast(JBufPtr, Builder.getInt8PtrTy());
437  Builder.CreateCall(BuiltinSetjmpFn, SetjmpArg);
438
439  // Store a pointer to the function context so that the back-end will know
440  // where to look for it.
441  Value *FuncCtxArg = Builder.CreateBitCast(FuncCtx, Builder.getInt8PtrTy());
442  Builder.CreateCall(FuncCtxFn, FuncCtxArg);
443
444  // At this point, we are all set up, update the invoke instructions to mark
445  // their call_site values.
446  for (unsigned I = 0, E = Invokes.size(); I != E; ++I) {
447    insertCallSiteStore(Invokes[I], I + 1);
448
449    ConstantInt *CallSiteNum =
450        ConstantInt::get(Type::getInt32Ty(F.getContext()), I + 1);
451
452    // Record the call site value for the back end so it stays associated with
453    // the invoke.
454    CallInst::Create(CallSiteFn, CallSiteNum, "", Invokes[I]);
455  }
456
457  // Mark call instructions that aren't nounwind as no-action (call_site ==
458  // -1). Skip the entry block, as prior to then, no function context has been
459  // created for this function and any unexpected exceptions thrown will go
460  // directly to the caller's context, which is what we want anyway, so no need
461  // to do anything here.
462  for (Function::iterator BB = F.begin(), E = F.end(); ++BB != E;)
463    for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I)
464      if (CallInst *CI = dyn_cast<CallInst>(I)) {
465        if (!CI->doesNotThrow())
466          insertCallSiteStore(CI, -1);
467      } else if (ResumeInst *RI = dyn_cast<ResumeInst>(I)) {
468        insertCallSiteStore(RI, -1);
469      }
470
471  // Register the function context and make sure it's known to not throw
472  CallInst *Register =
473      CallInst::Create(RegisterFn, FuncCtx, "", EntryBB->getTerminator());
474  Register->setDoesNotThrow();
475
476  // Following any allocas not in the entry block, update the saved SP in the
477  // jmpbuf to the new value.
478  for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
479    if (BB == F.begin())
480      continue;
481    for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
482      if (CallInst *CI = dyn_cast<CallInst>(I)) {
483        if (CI->getCalledFunction() != StackRestoreFn)
484          continue;
485      } else if (!isa<AllocaInst>(I)) {
486        continue;
487      }
488      Instruction *StackAddr = CallInst::Create(StackAddrFn, "sp");
489      StackAddr->insertAfter(I);
490      Instruction *StoreStackAddr = new StoreInst(StackAddr, StackPtr, true);
491      StoreStackAddr->insertAfter(StackAddr);
492    }
493  }
494
495  // Finally, for any returns from this function, if this function contains an
496  // invoke, add a call to unregister the function context.
497  for (unsigned I = 0, E = Returns.size(); I != E; ++I)
498    CallInst::Create(UnregisterFn, FuncCtx, "", Returns[I]);
499
500  return true;
501}
502
503bool SjLjEHPrepare::runOnFunction(Function &F) {
504  bool Res = setupEntryBlockAndCallSites(F);
505  return Res;
506}
507