lib/Transforms/Utils/LowerInvoke.cpp

   1 //===- LowerInvoke.cpp - Eliminate Invoke & Unwind instructions -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This transformation is designed for use by code generators which do not yet
  11 // support stack unwinding.  This pass supports two models of exception handling
  12 // lowering, the 'cheap' support and the 'expensive' support.
  13 //
  14 // 'Cheap' exception handling support gives the program the ability to execute
  15 // any program which does not "throw an exception", by turning 'invoke'
  16 // instructions into calls and by turning 'unwind' instructions into calls to
  17 // abort().  If the program does dynamically use the unwind instruction, the
  18 // program will print a message then abort.
  19 //
  20 // 'Expensive' exception handling support gives the full exception handling
  21 // support to the program at making the 'invoke' instruction really expensive.
  22 // It basically inserts setjmp/longjmp calls to emulate the exception handling
  23 // as necessary.
  24 //
  25 // Because the 'expensive' support slows down programs a lot, and EH is only
  26 // used for a subset of the programs, it must be specifically enabled by an
  27 // option.
  28 //
  29 //===----------------------------------------------------------------------===//
  30
  31 #include "llvm/Transforms/Scalar.h"
  32 #include "llvm/Constants.h"
  33 #include "llvm/DerivedTypes.h"
  34 #include "llvm/Instructions.h"
  35 #include "llvm/Module.h"
  36 #include "llvm/Pass.h"
  37 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  38 #include "Support/Statistic.h"
  39 #include "Support/CommandLine.h"
  40 #include <csetjmp>
  41 using namespace llvm;
  42
  43 namespace {
  44   Statistic<> NumLowered("lowerinvoke", "Number of invoke & unwinds replaced");
  45   cl::opt<bool> ExpensiveEHSupport("enable-correct-eh-support",
  46  cl::desc("Make the -lowerinvoke pass insert expensive, but correct, EH code"));
  47
  48   class LowerInvoke : public FunctionPass {
  49     // Used for both models.
  50     Function *WriteFn;
  51     Function *AbortFn;
  52     Value *AbortMessage;
  53     unsigned AbortMessageLength;
  54
  55     // Used for expensive EH support.
  56     const Type *JBLinkTy;
  57     GlobalVariable *JBListHead;
  58     Function *SetJmpFn, *LongJmpFn;
  59   public:
  60     bool doInitialization(Module &M);
  61     bool runOnFunction(Function &F);
  62   private:
  63     bool insertCheapEHSupport(Function &F);
  64     bool insertExpensiveEHSupport(Function &F);
  65   };
  66
  67   RegisterOpt<LowerInvoke>
  68   X("lowerinvoke", "Lower invoke and unwind, for unwindless code generators");
  69 }
  70
  71 // Public Interface To the LowerInvoke pass.
  72 FunctionPass *llvm::createLowerInvokePass() { return new LowerInvoke(); }
  73
  74 // doInitialization - Make sure that there is a prototype for abort in the
  75 // current module.
  76 bool LowerInvoke::doInitialization(Module &M) {
  77   const Type *VoidPtrTy = PointerType::get(Type::SByteTy);
  78   if (ExpensiveEHSupport) {
  79     // Insert a type for the linked list of jump buffers.  Unfortunately, we
  80     // don't know the size of the target's setjmp buffer, so we make a guess.
  81     // If this guess turns out to be too small, bad stuff could happen.
  82     unsigned JmpBufSize = 200;  // PPC has 192 words
  83     assert(sizeof(jmp_buf) <= JmpBufSize*sizeof(void*) &&
  84        "LowerInvoke doesn't know about targets with jmp_buf size > 200 words!");
  85     const Type *JmpBufTy = ArrayType::get(VoidPtrTy, JmpBufSize);
  86
  87     { // The type is recursive, so use a type holder.
  88       std::vector<const Type*> Elements;
  89       OpaqueType *OT = OpaqueType::get();
  90       Elements.push_back(PointerType::get(OT));
  91       Elements.push_back(JmpBufTy);
  92       PATypeHolder JBLType(StructType::get(Elements));
  93       OT->refineAbstractTypeTo(JBLType.get());  // Complete the cycle.
  94       JBLinkTy = JBLType.get();
  95     }
  96
  97     const Type *PtrJBList = PointerType::get(JBLinkTy);
  98
  99     // Now that we've done that, insert the jmpbuf list head global, unless it
 100     // already exists.
 101     if (!(JBListHead = M.getGlobalVariable("llvm.sjljeh.jblist", PtrJBList)))
 102       JBListHead = new GlobalVariable(PtrJBList, false,
 103                                       GlobalValue::LinkOnceLinkage,
 104                                       Constant::getNullValue(PtrJBList),
 105                                       "llvm.sjljeh.jblist", &M);
 106     SetJmpFn = M.getOrInsertFunction("setjmp", Type::IntTy,
 107                                      PointerType::get(JmpBufTy), 0);
 108     LongJmpFn = M.getOrInsertFunction("longjmp", Type::VoidTy,
 109                                       PointerType::get(JmpBufTy),
 110                                       Type::IntTy, 0);
 111
 112     // The abort message for expensive EH support tells the user that the
 113     // program 'unwound' without an 'invoke' instruction.
 114     Constant *Msg =
 115       ConstantArray::get("ERROR: Exception thrown, but not caught!\n");
 116     AbortMessageLength = Msg->getNumOperands()-1;  // don't include \0
 117
 118     GlobalVariable *MsgGV = M.getGlobalVariable("abort.msg", Msg->getType());
 119     if (MsgGV && (!MsgGV->hasInitializer() || MsgGV->getInitializer() != Msg))
 120       MsgGV = 0;
 121     if (!MsgGV)
 122       MsgGV = new GlobalVariable(Msg->getType(), true,
 123                                  GlobalValue::InternalLinkage,
 124                                  Msg, "abort.msg", &M);
 125     std::vector<Constant*> GEPIdx(2, Constant::getNullValue(Type::LongTy));
 126     AbortMessage =
 127       ConstantExpr::getGetElementPtr(ConstantPointerRef::get(MsgGV), GEPIdx);
 128
 129   } else {
 130     // The abort message for cheap EH support tells the user that EH is not
 131     // enabled.
 132     Constant *Msg =
 133       ConstantArray::get("Exception handler needed, but not enabled.  Recompile"
 134                          " program with -enable-correct-eh-support.\n");
 135     AbortMessageLength = Msg->getNumOperands()-1;  // don't include \0
 136
 137     GlobalVariable *MsgGV = M.getGlobalVariable("abort.msg", Msg->getType());
 138     if (MsgGV && (!MsgGV->hasInitializer() || MsgGV->getInitializer() != Msg))
 139       MsgGV = 0;
 140
 141     if (!MsgGV)
 142       MsgGV = new GlobalVariable(Msg->getType(), true,
 143                                  GlobalValue::InternalLinkage,
 144                                  Msg, "abort.msg", &M);
 145     std::vector<Constant*> GEPIdx(2, Constant::getNullValue(Type::LongTy));
 146     AbortMessage =
 147       ConstantExpr::getGetElementPtr(ConstantPointerRef::get(MsgGV), GEPIdx);
 148   }
 149
 150   // We need the 'write' and 'abort' functions for both models.
 151   WriteFn = M.getOrInsertFunction("write", Type::VoidTy, Type::IntTy,
 152                                   VoidPtrTy, Type::IntTy, 0);
 153   AbortFn = M.getOrInsertFunction("abort", Type::VoidTy, 0);
 154   return true;
 155 }
 156
 157 bool LowerInvoke::insertCheapEHSupport(Function &F) {
 158   bool Changed = false;
 159   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 160     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
 161       // Insert a normal call instruction...
 162       std::string Name = II->getName(); II->setName("");
 163       Value *NewCall = new CallInst(II->getCalledValue(),
 164                                     std::vector<Value*>(II->op_begin()+3,
 165                                                         II->op_end()), Name,II);
 166       II->replaceAllUsesWith(NewCall);
 167
 168       // Insert an unconditional branch to the normal destination.
 169       new BranchInst(II->getNormalDest(), II);
 170
 171       // Remove any PHI node entries from the exception destination.
 172       II->getUnwindDest()->removePredecessor(BB);
 173
 174       // Remove the invoke instruction now.
 175       BB->getInstList().erase(II);
 176
 177       ++NumLowered; Changed = true;
 178     } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
 179       // Insert a new call to write(2, AbortMessage, AbortMessageLength);
 180       std::vector<Value*> Args;
 181       Args.push_back(ConstantInt::get(Type::IntTy, 2));
 182       Args.push_back(AbortMessage);
 183       Args.push_back(ConstantInt::get(Type::IntTy, AbortMessageLength));
 184       new CallInst(WriteFn, Args, "", UI);
 185
 186       // Insert a call to abort()
 187       new CallInst(AbortFn, std::vector<Value*>(), "", UI);
 188
 189       // Insert a return instruction.  This really should be a "barrier", as it
 190       // is unreachable.
 191       new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
 192                             Constant::getNullValue(F.getReturnType()), UI);
 193
 194       // Remove the unwind instruction now.
 195       BB->getInstList().erase(UI);
 196
 197       ++NumLowered; Changed = true;
 198     }
 199   return Changed;
 200 }
 201
 202 bool LowerInvoke::insertExpensiveEHSupport(Function &F) {
 203   bool Changed = false;
 204
 205   // If a function uses invoke, we have an alloca for the jump buffer.
 206   AllocaInst *JmpBuf = 0;
 207
 208   // If this function contains an unwind instruction, two blocks get added: one
 209   // to actually perform the longjmp, and one to terminate the program if there
 210   // is no handler.
 211   BasicBlock *UnwindBlock = 0, *TermBlock = 0;
 212   std::vector<LoadInst*> JBPtrs;
 213
 214   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 215     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
 216       if (JmpBuf == 0)
 217         JmpBuf = new AllocaInst(JBLinkTy, 0, "jblink", F.begin()->begin());
 218
 219       // On the entry to the invoke, we must install our JmpBuf as the top of
 220       // the stack.
 221       LoadInst *OldEntry = new LoadInst(JBListHead, "oldehlist", II);
 222
 223       // Store this old value as our 'next' field, and store our alloca as the
 224       // current jblist.
 225       std::vector<Value*> Idx;
 226       Idx.push_back(Constant::getNullValue(Type::LongTy));
 227       Idx.push_back(ConstantUInt::get(Type::UByteTy, 0));
 228       Value *NextFieldPtr = new GetElementPtrInst(JmpBuf, Idx, "NextField", II);
 229       new StoreInst(OldEntry, NextFieldPtr, II);
 230       new StoreInst(JmpBuf, JBListHead, II);
 231
 232       // Call setjmp, passing in the address of the jmpbuffer.
 233       Idx[1] = ConstantUInt::get(Type::UByteTy, 1);
 234       Value *JmpBufPtr = new GetElementPtrInst(JmpBuf, Idx, "TheJmpBuf", II);
 235       Value *SJRet = new CallInst(SetJmpFn, JmpBufPtr, "sjret", II);
 236
 237       // Compare the return value to zero.
 238       Value *IsNormal = BinaryOperator::create(Instruction::SetEQ, SJRet,
 239                                        Constant::getNullValue(SJRet->getType()),
 240                                                "notunwind", II);
 241       // Create the receiver block if there is a critical edge to the normal
 242       // destination.
 243       SplitCriticalEdge(II, 0, this);
 244       Instruction *InsertLoc = II->getNormalDest()->begin();
 245
 246       // Insert a normal call instruction on the normal execution path.
 247       std::string Name = II->getName(); II->setName("");
 248       Value *NewCall = new CallInst(II->getCalledValue(),
 249                                     std::vector<Value*>(II->op_begin()+3,
 250                                                         II->op_end()), Name,
 251                                     InsertLoc);
 252       II->replaceAllUsesWith(NewCall);
 253
 254       // If we got this far, then no exception was thrown and we can pop our
 255       // jmpbuf entry off.
 256       new StoreInst(OldEntry, JBListHead, InsertLoc);
 257
 258       // Now we change the invoke into a branch instruction.
 259       new BranchInst(II->getNormalDest(), II->getUnwindDest(), IsNormal, II);
 260
 261       // Remove the InvokeInst now.
 262       BB->getInstList().erase(II);
 263       ++NumLowered; Changed = true;
 264
 265     } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
 266       if (UnwindBlock == 0) {
 267         // Create two new blocks, the unwind block and the terminate block.  Add
 268         // them at the end of the function because they are not hot.
 269         UnwindBlock = new BasicBlock("unwind", &F);
 270         TermBlock = new BasicBlock("unwinderror", &F);
 271
 272         // Insert return instructions.  These really should be "barrier"s, as
 273         // they are unreachable.
 274         new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
 275                        Constant::getNullValue(F.getReturnType()), UnwindBlock);
 276         new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
 277                        Constant::getNullValue(F.getReturnType()), TermBlock);
 278       }
 279
 280       // Load the JBList, if it's null, then there was no catch!
 281       LoadInst *Ptr = new LoadInst(JBListHead, "ehlist", UI);
 282       Value *NotNull = BinaryOperator::create(Instruction::SetNE, Ptr,
 283                                         Constant::getNullValue(Ptr->getType()),
 284                                               "notnull", UI);
 285       new BranchInst(UnwindBlock, TermBlock, NotNull, UI);
 286
 287       // Remember the loaded value so we can insert the PHI node as needed.
 288       JBPtrs.push_back(Ptr);
 289
 290       // Remove the UnwindInst now.
 291       BB->getInstList().erase(UI);
 292       ++NumLowered; Changed = true;
 293     }
 294
 295   // If an unwind instruction was inserted, we need to set up the Unwind and
 296   // term blocks.
 297   if (UnwindBlock) {
 298     // In the unwind block, we know that the pointer coming in on the JBPtrs
 299     // list are non-null.
 300     Instruction *RI = UnwindBlock->getTerminator();
 301
 302     Value *RecPtr;
 303     if (JBPtrs.size() == 1)
 304       RecPtr = JBPtrs[0];
 305     else {
 306       // If there is more than one unwind in this function, make a PHI node to
 307       // merge in all of the loaded values.
 308       PHINode *PN = new PHINode(JBPtrs[0]->getType(), "jbptrs", RI);
 309       for (unsigned i = 0, e = JBPtrs.size(); i != e; ++i)
 310         PN->addIncoming(JBPtrs[i], JBPtrs[i]->getParent());
 311       RecPtr = PN;
 312     }
 313
 314     // Now that we have a pointer to the whole record, remove the entry from the
 315     // JBList.
 316     std::vector<Value*> Idx;
 317     Idx.push_back(Constant::getNullValue(Type::LongTy));
 318     Idx.push_back(ConstantUInt::get(Type::UByteTy, 0));
 319     Value *NextFieldPtr = new GetElementPtrInst(RecPtr, Idx, "NextField", RI);
 320     Value *NextRec = new LoadInst(NextFieldPtr, "NextRecord", RI);
 321     new StoreInst(NextRec, JBListHead, RI);
 322
 323     // Now that we popped the top of the JBList, get a pointer to the jmpbuf and
 324     // longjmp.
 325     Idx[1] = ConstantUInt::get(Type::UByteTy, 1);
 326     Idx[0] = new GetElementPtrInst(RecPtr, Idx, "JmpBuf", RI);
 327     Idx[1] = ConstantInt::get(Type::IntTy, 1);
 328     new CallInst(LongJmpFn, Idx, "", RI);
 329
 330     // Now we set up the terminate block.
 331     RI = TermBlock->getTerminator();
 332
 333     // Insert a new call to write(2, AbortMessage, AbortMessageLength);
 334     Idx[0] = ConstantInt::get(Type::IntTy, 2);
 335     Idx[1] = AbortMessage;
 336     Idx.push_back(ConstantInt::get(Type::IntTy, AbortMessageLength));
 337     new CallInst(WriteFn, Idx, "", RI);
 338
 339     // Insert a call to abort()
 340     new CallInst(AbortFn, std::vector<Value*>(), "", RI);
 341   }
 342
 343   return Changed;
 344 }
 345
 346 bool LowerInvoke::runOnFunction(Function &F) {
 347   if (ExpensiveEHSupport)
 348     return insertExpensiveEHSupport(F);
 349   else
 350     return insertCheapEHSupport(F);
 351 }