lib/CodeGen/SjLjEHPrepare.cpp

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