lib/CodeGen/SjLjEHPrepare.cpp

   1 //===- SjLjEHPrepare.cpp - Eliminate Invoke & Unwind instructions ---------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This transformation is designed for use by code generators which use SjLj
  10 // based exception handling.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/ADT/SetVector.h"
  15 #include "llvm/ADT/SmallPtrSet.h"
  16 #include "llvm/ADT/SmallVector.h"
  17 #include "llvm/ADT/Statistic.h"
  18 #include "llvm/Transforms/Utils/Local.h"
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/IR/Constants.h"
  21 #include "llvm/IR/DataLayout.h"
  22 #include "llvm/IR/DerivedTypes.h"
  23 #include "llvm/IR/IRBuilder.h"
  24 #include "llvm/IR/Instructions.h"
  25 #include "llvm/IR/Intrinsics.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/Pass.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "sjljehprepare"
  33
  34 STATISTIC(NumInvokes, "Number of invokes replaced");
  35 STATISTIC(NumSpilled, "Number of registers live across unwind edges");
  36
  37 namespace {
  38 class SjLjEHPrepare : public FunctionPass {
  39   Type *doubleUnderDataTy;
  40   Type *doubleUnderJBufTy;
  41   Type *FunctionContextTy;
  42   FunctionCallee RegisterFn;
  43   FunctionCallee UnregisterFn;
  44   Function *BuiltinSetupDispatchFn;
  45   Function *FrameAddrFn;
  46   Function *StackAddrFn;
  47   Function *StackRestoreFn;
  48   Function *LSDAAddrFn;
  49   Function *CallSiteFn;
  50   Function *FuncCtxFn;
  51   AllocaInst *FuncCtx;
  52
  53 public:
  54   static char ID; // Pass identification, replacement for typeid
  55   explicit SjLjEHPrepare() : FunctionPass(ID) {}
  56   bool doInitialization(Module &M) override;
  57   bool runOnFunction(Function &F) override;
  58
  59   void getAnalysisUsage(AnalysisUsage &AU) const override {}
  60   StringRef getPassName() const override {
  61     return "SJLJ Exception Handling preparation";
  62   }
  63
  64 private:
  65   bool setupEntryBlockAndCallSites(Function &F);
  66   void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, Value *SelVal);
  67   Value *setupFunctionContext(Function &F, ArrayRef<LandingPadInst *> LPads);
  68   void lowerIncomingArguments(Function &F);
  69   void lowerAcrossUnwindEdges(Function &F, ArrayRef<InvokeInst *> Invokes);
  70   void insertCallSiteStore(Instruction *I, int Number);
  71 };
  72 } // end anonymous namespace
  73
  74 char SjLjEHPrepare::ID = 0;
  75 INITIALIZE_PASS(SjLjEHPrepare, DEBUG_TYPE, "Prepare SjLj exceptions",
  76                 false, false)
  77
  78 // Public Interface To the SjLjEHPrepare pass.
  79 FunctionPass *llvm::createSjLjEHPreparePass() { return new SjLjEHPrepare(); }
  80 // doInitialization - Set up decalarations and types needed to process
  81 // exceptions.
  82 bool SjLjEHPrepare::doInitialization(Module &M) {
  83   // Build the function context structure.
  84   // builtin_setjmp uses a five word jbuf
  85   Type *VoidPtrTy = Type::getInt8PtrTy(M.getContext());
  86   Type *Int32Ty = Type::getInt32Ty(M.getContext());
  87   doubleUnderDataTy = ArrayType::get(Int32Ty, 4);
  88   doubleUnderJBufTy = ArrayType::get(VoidPtrTy, 5);
  89   FunctionContextTy = StructType::get(VoidPtrTy,         // __prev
  90                                       Int32Ty,           // call_site
  91                                       doubleUnderDataTy, // __data
  92                                       VoidPtrTy,         // __personality
  93                                       VoidPtrTy,         // __lsda
  94                                       doubleUnderJBufTy  // __jbuf
  95                                       );
  96
  97   return true;
  98 }
  99
 100 /// insertCallSiteStore - Insert a store of the call-site value to the
 101 /// function context
 102 void SjLjEHPrepare::insertCallSiteStore(Instruction *I, int Number) {
 103   IRBuilder<> Builder(I);
 104
 105   // Get a reference to the call_site field.
 106   Type *Int32Ty = Type::getInt32Ty(I->getContext());
 107   Value *Zero = ConstantInt::get(Int32Ty, 0);
 108   Value *One = ConstantInt::get(Int32Ty, 1);
 109   Value *Idxs[2] = { Zero, One };
 110   Value *CallSite =
 111       Builder.CreateGEP(FunctionContextTy, FuncCtx, Idxs, "call_site");
 112
 113   // Insert a store of the call-site number
 114   ConstantInt *CallSiteNoC =
 115       ConstantInt::get(Type::getInt32Ty(I->getContext()), Number);
 116   Builder.CreateStore(CallSiteNoC, CallSite, true /*volatile*/);
 117 }
 118
 119 /// MarkBlocksLiveIn - Insert BB and all of its predecessors into LiveBBs until
 120 /// we reach blocks we've already seen.
 121 static void MarkBlocksLiveIn(BasicBlock *BB,
 122                              SmallPtrSetImpl<BasicBlock *> &LiveBBs) {
 123   if (!LiveBBs.insert(BB).second)
 124     return; // already been here.
 125
 126   df_iterator_default_set<BasicBlock*> Visited;
 127
 128   for (BasicBlock *B : inverse_depth_first_ext(BB, Visited))
 129     LiveBBs.insert(B);
 130
 131 }
 132
 133 /// substituteLPadValues - Substitute the values returned by the landingpad
 134 /// instruction with those returned by the personality function.
 135 void SjLjEHPrepare::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal,
 136                                          Value *SelVal) {
 137   SmallVector<Value *, 8> UseWorkList(LPI->user_begin(), LPI->user_end());
 138   while (!UseWorkList.empty()) {
 139     Value *Val = UseWorkList.pop_back_val();
 140     auto *EVI = dyn_cast<ExtractValueInst>(Val);
 141     if (!EVI)
 142       continue;
 143     if (EVI->getNumIndices() != 1)
 144       continue;
 145     if (*EVI->idx_begin() == 0)
 146       EVI->replaceAllUsesWith(ExnVal);
 147     else if (*EVI->idx_begin() == 1)
 148       EVI->replaceAllUsesWith(SelVal);
 149     if (EVI->use_empty())
 150       EVI->eraseFromParent();
 151   }
 152
 153   if (LPI->use_empty())
 154     return;
 155
 156   // There are still some uses of LPI. Construct an aggregate with the exception
 157   // values and replace the LPI with that aggregate.
 158   Type *LPadType = LPI->getType();
 159   Value *LPadVal = UndefValue::get(LPadType);
 160   auto *SelI = cast<Instruction>(SelVal);
 161   IRBuilder<> Builder(SelI->getParent(), std::next(SelI->getIterator()));
 162   LPadVal = Builder.CreateInsertValue(LPadVal, ExnVal, 0, "lpad.val");
 163   LPadVal = Builder.CreateInsertValue(LPadVal, SelVal, 1, "lpad.val");
 164
 165   LPI->replaceAllUsesWith(LPadVal);
 166 }
 167
 168 /// setupFunctionContext - Allocate the function context on the stack and fill
 169 /// it with all of the data that we know at this point.
 170 Value *SjLjEHPrepare::setupFunctionContext(Function &F,
 171                                            ArrayRef<LandingPadInst *> LPads) {
 172   BasicBlock *EntryBB = &F.front();
 173
 174   // Create an alloca for the incoming jump buffer ptr and the new jump buffer
 175   // that needs to be restored on all exits from the function. This is an alloca
 176   // because the value needs to be added to the global context list.
 177   auto &DL = F.getParent()->getDataLayout();
 178   unsigned Align = DL.getPrefTypeAlignment(FunctionContextTy);
 179   FuncCtx = new AllocaInst(FunctionContextTy, DL.getAllocaAddrSpace(),
 180                            nullptr, Align, "fn_context", &EntryBB->front());
 181
 182   // Fill in the function context structure.
 183   for (LandingPadInst *LPI : LPads) {
 184     IRBuilder<> Builder(LPI->getParent(),
 185                         LPI->getParent()->getFirstInsertionPt());
 186
 187     // Reference the __data field.
 188     Value *FCData =
 189         Builder.CreateConstGEP2_32(FunctionContextTy, FuncCtx, 0, 2, "__data");
 190
 191     // The exception values come back in context->__data[0].
 192     Type *Int32Ty = Type::getInt32Ty(F.getContext());
 193     Value *ExceptionAddr = Builder.CreateConstGEP2_32(doubleUnderDataTy, FCData,
 194                                                       0, 0, "exception_gep");
 195     Value *ExnVal = Builder.CreateLoad(Int32Ty, ExceptionAddr, true, "exn_val");
 196     ExnVal = Builder.CreateIntToPtr(ExnVal, Builder.getInt8PtrTy());
 197
 198     Value *SelectorAddr = Builder.CreateConstGEP2_32(doubleUnderDataTy, FCData,
 199                                                      0, 1, "exn_selector_gep");
 200     Value *SelVal =
 201         Builder.CreateLoad(Int32Ty, SelectorAddr, true, "exn_selector_val");
 202
 203     substituteLPadValues(LPI, ExnVal, SelVal);
 204   }
 205
 206   // Personality function
 207   IRBuilder<> Builder(EntryBB->getTerminator());
 208   Value *PersonalityFn = F.getPersonalityFn();
 209   Value *PersonalityFieldPtr = Builder.CreateConstGEP2_32(
 210       FunctionContextTy, FuncCtx, 0, 3, "pers_fn_gep");
 211   Builder.CreateStore(
 212       Builder.CreateBitCast(PersonalityFn, Builder.getInt8PtrTy()),
 213       PersonalityFieldPtr, /*isVolatile=*/true);
 214
 215   // LSDA address
 216   Value *LSDA = Builder.CreateCall(LSDAAddrFn, {}, "lsda_addr");
 217   Value *LSDAFieldPtr =
 218       Builder.CreateConstGEP2_32(FunctionContextTy, FuncCtx, 0, 4, "lsda_gep");
 219   Builder.CreateStore(LSDA, LSDAFieldPtr, /*isVolatile=*/true);
 220
 221   return FuncCtx;
 222 }
 223
 224 /// lowerIncomingArguments - To avoid having to handle incoming arguments
 225 /// specially, we lower each arg to a copy instruction in the entry block. This
 226 /// ensures that the argument value itself cannot be live out of the entry
 227 /// block.
 228 void SjLjEHPrepare::lowerIncomingArguments(Function &F) {
 229   BasicBlock::iterator AfterAllocaInsPt = F.begin()->begin();
 230   while (isa<AllocaInst>(AfterAllocaInsPt) &&
 231          cast<AllocaInst>(AfterAllocaInsPt)->isStaticAlloca())
 232     ++AfterAllocaInsPt;
 233   assert(AfterAllocaInsPt != F.front().end());
 234
 235   for (auto &AI : F.args()) {
 236     // Swift error really is a register that we model as memory -- instruction
 237     // selection will perform mem-to-reg for us and spill/reload appropriately
 238     // around calls that clobber it. There is no need to spill this
 239     // value to the stack and doing so would not be allowed.
 240     if (AI.isSwiftError())
 241       continue;
 242
 243     Type *Ty = AI.getType();
 244
 245     // Use 'select i8 true, %arg, undef' to simulate a 'no-op' instruction.
 246     Value *TrueValue = ConstantInt::getTrue(F.getContext());
 247     Value *UndefValue = UndefValue::get(Ty);
 248     Instruction *SI = SelectInst::Create(
 249         TrueValue, &AI, UndefValue, AI.getName() + ".tmp", &*AfterAllocaInsPt);
 250     AI.replaceAllUsesWith(SI);
 251
 252     // Reset the operand, because it  was clobbered by the RAUW above.
 253     SI->setOperand(1, &AI);
 254   }
 255 }
 256
 257 /// lowerAcrossUnwindEdges - Find all variables which are alive across an unwind
 258 /// edge and spill them.
 259 void SjLjEHPrepare::lowerAcrossUnwindEdges(Function &F,
 260                                            ArrayRef<InvokeInst *> Invokes) {
 261   // Finally, scan the code looking for instructions with bad live ranges.
 262   for (BasicBlock &BB : F) {
 263     for (Instruction &Inst : BB) {
 264       // Ignore obvious cases we don't have to handle. In particular, most
 265       // instructions either have no uses or only have a single use inside the
 266       // current block. Ignore them quickly.
 267       if (Inst.use_empty())
 268         continue;
 269       if (Inst.hasOneUse() &&
 270           cast<Instruction>(Inst.user_back())->getParent() == &BB &&
 271           !isa<PHINode>(Inst.user_back()))
 272         continue;
 273
 274       // If this is an alloca in the entry block, it's not a real register
 275       // value.
 276       if (auto *AI = dyn_cast<AllocaInst>(&Inst))
 277         if (AI->isStaticAlloca())
 278           continue;
 279
 280       // Avoid iterator invalidation by copying users to a temporary vector.
 281       SmallVector<Instruction *, 16> Users;
 282       for (User *U : Inst.users()) {
 283         Instruction *UI = cast<Instruction>(U);
 284         if (UI->getParent() != &BB || isa<PHINode>(UI))
 285           Users.push_back(UI);
 286       }
 287
 288       // Find all of the blocks that this value is live in.
 289       SmallPtrSet<BasicBlock *, 32> LiveBBs;
 290       LiveBBs.insert(&BB);
 291       while (!Users.empty()) {
 292         Instruction *U = Users.pop_back_val();
 293
 294         if (!isa<PHINode>(U)) {
 295           MarkBlocksLiveIn(U->getParent(), LiveBBs);
 296         } else {
 297           // Uses for a PHI node occur in their predecessor block.
 298           PHINode *PN = cast<PHINode>(U);
 299           for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
 300             if (PN->getIncomingValue(i) == &Inst)
 301               MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs);
 302         }
 303       }
 304
 305       // Now that we know all of the blocks that this thing is live in, see if
 306       // it includes any of the unwind locations.
 307       bool NeedsSpill = false;
 308       for (InvokeInst *Invoke : Invokes) {
 309         BasicBlock *UnwindBlock = Invoke->getUnwindDest();
 310         if (UnwindBlock != &BB && LiveBBs.count(UnwindBlock)) {
 311           LLVM_DEBUG(dbgs() << "SJLJ Spill: " << Inst << " around "
 312                             << UnwindBlock->getName() << "\n");
 313           NeedsSpill = true;
 314           break;
 315         }
 316       }
 317
 318       // If we decided we need a spill, do it.
 319       // FIXME: Spilling this way is overkill, as it forces all uses of
 320       // the value to be reloaded from the stack slot, even those that aren't
 321       // in the unwind blocks. We should be more selective.
 322       if (NeedsSpill) {
 323         DemoteRegToStack(Inst, true);
 324         ++NumSpilled;
 325       }
 326     }
 327   }
 328
 329   // Go through the landing pads and remove any PHIs there.
 330   for (InvokeInst *Invoke : Invokes) {
 331     BasicBlock *UnwindBlock = Invoke->getUnwindDest();
 332     LandingPadInst *LPI = UnwindBlock->getLandingPadInst();
 333
 334     // Place PHIs into a set to avoid invalidating the iterator.
 335     SmallPtrSet<PHINode *, 8> PHIsToDemote;
 336     for (BasicBlock::iterator PN = UnwindBlock->begin(); isa<PHINode>(PN); ++PN)
 337       PHIsToDemote.insert(cast<PHINode>(PN));
 338     if (PHIsToDemote.empty())
 339       continue;
 340
 341     // Demote the PHIs to the stack.
 342     for (PHINode *PN : PHIsToDemote)
 343       DemotePHIToStack(PN);
 344
 345     // Move the landingpad instruction back to the top of the landing pad block.
 346     LPI->moveBefore(&UnwindBlock->front());
 347   }
 348 }
 349
 350 /// setupEntryBlockAndCallSites - Setup the entry block by creating and filling
 351 /// the function context and marking the call sites with the appropriate
 352 /// values. These values are used by the DWARF EH emitter.
 353 bool SjLjEHPrepare::setupEntryBlockAndCallSites(Function &F) {
 354   SmallVector<ReturnInst *, 16> Returns;
 355   SmallVector<InvokeInst *, 16> Invokes;
 356   SmallSetVector<LandingPadInst *, 16> LPads;
 357
 358   // Look through the terminators of the basic blocks to find invokes.
 359   for (BasicBlock &BB : F)
 360     if (auto *II = dyn_cast<InvokeInst>(BB.getTerminator())) {
 361       if (Function *Callee = II->getCalledFunction())
 362         if (Callee->getIntrinsicID() == Intrinsic::donothing) {
 363           // Remove the NOP invoke.
 364           BranchInst::Create(II->getNormalDest(), II);
 365           II->eraseFromParent();
 366           continue;
 367         }
 368
 369       Invokes.push_back(II);
 370       LPads.insert(II->getUnwindDest()->getLandingPadInst());
 371     } else if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
 372       Returns.push_back(RI);
 373     }
 374
 375   if (Invokes.empty())
 376     return false;
 377
 378   NumInvokes += Invokes.size();
 379
 380   lowerIncomingArguments(F);
 381   lowerAcrossUnwindEdges(F, Invokes);
 382
 383   Value *FuncCtx =
 384       setupFunctionContext(F, makeArrayRef(LPads.begin(), LPads.end()));
 385   BasicBlock *EntryBB = &F.front();
 386   IRBuilder<> Builder(EntryBB->getTerminator());
 387
 388   // Get a reference to the jump buffer.
 389   Value *JBufPtr =
 390       Builder.CreateConstGEP2_32(FunctionContextTy, FuncCtx, 0, 5, "jbuf_gep");
 391
 392   // Save the frame pointer.
 393   Value *FramePtr = Builder.CreateConstGEP2_32(doubleUnderJBufTy, JBufPtr, 0, 0,
 394                                                "jbuf_fp_gep");
 395
 396   Value *Val = Builder.CreateCall(FrameAddrFn, Builder.getInt32(0), "fp");
 397   Builder.CreateStore(Val, FramePtr, /*isVolatile=*/true);
 398
 399   // Save the stack pointer.
 400   Value *StackPtr = Builder.CreateConstGEP2_32(doubleUnderJBufTy, JBufPtr, 0, 2,
 401                                                "jbuf_sp_gep");
 402
 403   Val = Builder.CreateCall(StackAddrFn, {}, "sp");
 404   Builder.CreateStore(Val, StackPtr, /*isVolatile=*/true);
 405
 406   // Call the setup_dispatch instrinsic. It fills in the rest of the jmpbuf.
 407   Builder.CreateCall(BuiltinSetupDispatchFn, {});
 408
 409   // Store a pointer to the function context so that the back-end will know
 410   // where to look for it.
 411   Value *FuncCtxArg = Builder.CreateBitCast(FuncCtx, Builder.getInt8PtrTy());
 412   Builder.CreateCall(FuncCtxFn, FuncCtxArg);
 413
 414   // At this point, we are all set up, update the invoke instructions to mark
 415   // their call_site values.
 416   for (unsigned I = 0, E = Invokes.size(); I != E; ++I) {
 417     insertCallSiteStore(Invokes[I], I + 1);
 418
 419     ConstantInt *CallSiteNum =
 420         ConstantInt::get(Type::getInt32Ty(F.getContext()), I + 1);
 421
 422     // Record the call site value for the back end so it stays associated with
 423     // the invoke.
 424     CallInst::Create(CallSiteFn, CallSiteNum, "", Invokes[I]);
 425   }
 426
 427   // Mark call instructions that aren't nounwind as no-action (call_site ==
 428   // -1). Skip the entry block, as prior to then, no function context has been
 429   // created for this function and any unexpected exceptions thrown will go
 430   // directly to the caller's context, which is what we want anyway, so no need
 431   // to do anything here.
 432   for (BasicBlock &BB : F) {
 433     if (&BB == &F.front())
 434       continue;
 435     for (Instruction &I : BB)
 436       if (I.mayThrow())
 437         insertCallSiteStore(&I, -1);
 438   }
 439
 440   // Register the function context and make sure it's known to not throw
 441   CallInst *Register =
 442       CallInst::Create(RegisterFn, FuncCtx, "", EntryBB->getTerminator());
 443   Register->setDoesNotThrow();
 444
 445   // Following any allocas not in the entry block, update the saved SP in the
 446   // jmpbuf to the new value.
 447   for (BasicBlock &BB : F) {
 448     if (&BB == &F.front())
 449       continue;
 450     for (Instruction &I : BB) {
 451       if (auto *CI = dyn_cast<CallInst>(&I)) {
 452         if (CI->getCalledFunction() != StackRestoreFn)
 453           continue;
 454       } else if (!isa<AllocaInst>(&I)) {
 455         continue;
 456       }
 457       Instruction *StackAddr = CallInst::Create(StackAddrFn, "sp");
 458       StackAddr->insertAfter(&I);
 459       Instruction *StoreStackAddr = new StoreInst(StackAddr, StackPtr, true);
 460       StoreStackAddr->insertAfter(StackAddr);
 461     }
 462   }
 463
 464   // Finally, for any returns from this function, if this function contains an
 465   // invoke, add a call to unregister the function context.
 466   for (ReturnInst *Return : Returns)
 467     CallInst::Create(UnregisterFn, FuncCtx, "", Return);
 468
 469   return true;
 470 }
 471
 472 bool SjLjEHPrepare::runOnFunction(Function &F) {
 473   Module &M = *F.getParent();
 474   RegisterFn = M.getOrInsertFunction(
 475       "_Unwind_SjLj_Register", Type::getVoidTy(M.getContext()),
 476       PointerType::getUnqual(FunctionContextTy));
 477   UnregisterFn = M.getOrInsertFunction(
 478       "_Unwind_SjLj_Unregister", Type::getVoidTy(M.getContext()),
 479       PointerType::getUnqual(FunctionContextTy));
 480   FrameAddrFn = Intrinsic::getDeclaration(
 481       &M, Intrinsic::frameaddress,
 482       {Type::getInt8PtrTy(M.getContext(),
 483                           M.getDataLayout().getAllocaAddrSpace())});
 484   StackAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::stacksave);
 485   StackRestoreFn = Intrinsic::getDeclaration(&M, Intrinsic::stackrestore);
 486   BuiltinSetupDispatchFn =
 487     Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_setup_dispatch);
 488   LSDAAddrFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_lsda);
 489   CallSiteFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_callsite);
 490   FuncCtxFn = Intrinsic::getDeclaration(&M, Intrinsic::eh_sjlj_functioncontext);
 491
 492   bool Res = setupEntryBlockAndCallSites(F);
 493   return Res;
 494 }