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 // Note that after this pass runs the CFG is not entirely accurate (exceptional
  30 // control flow edges are not correct anymore) so only very simple things should
  31 // be done after the lowerinvoke pass has run (like generation of native code).
  32 // This should not be used as a general purpose "my LLVM-to-LLVM pass doesn't
  33 // support the invoke instruction yet" lowering pass.
  34 //
  35 //===----------------------------------------------------------------------===//
  36
  37 #include "llvm/Transforms/Scalar.h"
  38 #include "llvm/Constants.h"
  39 #include "llvm/DerivedTypes.h"
  40 #include "llvm/Instructions.h"
  41 #include "llvm/Module.h"
  42 #include "llvm/Pass.h"
  43 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  44 #include "Support/Statistic.h"
  45 #include "Support/CommandLine.h"
  46 #include <csetjmp>
  47 using namespace llvm;
  48
  49 namespace {
  50   Statistic<> NumLowered("lowerinvoke", "Number of invoke & unwinds replaced");
  51   cl::opt<bool> ExpensiveEHSupport("enable-correct-eh-support",
  52  cl::desc("Make the -lowerinvoke pass insert expensive, but correct, EH code"));
  53
  54   class LowerInvoke : public FunctionPass {
  55     // Used for both models.
  56     Function *WriteFn;
  57     Function *AbortFn;
  58     Constant *AbortMessageInit;
  59     Value *AbortMessage;
  60     unsigned AbortMessageLength;
  61
  62     // Used for expensive EH support.
  63     const Type *JBLinkTy;
  64     GlobalVariable *JBListHead;
  65     Function *SetJmpFn, *LongJmpFn;
  66   public:
  67     bool doInitialization(Module &M);
  68     bool runOnFunction(Function &F);
  69   private:
  70     void writeAbortMessage(Instruction *IB);
  71     bool insertCheapEHSupport(Function &F);
  72     bool insertExpensiveEHSupport(Function &F);
  73   };
  74
  75   RegisterOpt<LowerInvoke>
  76   X("lowerinvoke", "Lower invoke and unwind, for unwindless code generators");
  77 }
  78
  79 const PassInfo *llvm::LowerInvokePassID = X.getPassInfo();
  80
  81 // Public Interface To the LowerInvoke pass.
  82 FunctionPass *llvm::createLowerInvokePass() { return new LowerInvoke(); }
  83
  84 // doInitialization - Make sure that there is a prototype for abort in the
  85 // current module.
  86 bool LowerInvoke::doInitialization(Module &M) {
  87   const Type *VoidPtrTy = PointerType::get(Type::SByteTy);
  88   AbortMessage = 0;
  89   if (ExpensiveEHSupport) {
  90     // Insert a type for the linked list of jump buffers.  Unfortunately, we
  91     // don't know the size of the target's setjmp buffer, so we make a guess.
  92     // If this guess turns out to be too small, bad stuff could happen.
  93     unsigned JmpBufSize = 200;  // PPC has 192 words
  94     assert(sizeof(jmp_buf) <= JmpBufSize*sizeof(void*) &&
  95        "LowerInvoke doesn't know about targets with jmp_buf size > 200 words!");
  96     const Type *JmpBufTy = ArrayType::get(VoidPtrTy, JmpBufSize);
  97
  98     { // The type is recursive, so use a type holder.
  99       std::vector<const Type*> Elements;
 100       OpaqueType *OT = OpaqueType::get();
 101       Elements.push_back(PointerType::get(OT));
 102       Elements.push_back(JmpBufTy);
 103       PATypeHolder JBLType(StructType::get(Elements));
 104       OT->refineAbstractTypeTo(JBLType.get());  // Complete the cycle.
 105       JBLinkTy = JBLType.get();
 106     }
 107
 108     const Type *PtrJBList = PointerType::get(JBLinkTy);
 109
 110     // Now that we've done that, insert the jmpbuf list head global, unless it
 111     // already exists.
 112     if (!(JBListHead = M.getGlobalVariable("llvm.sjljeh.jblist", PtrJBList)))
 113       JBListHead = new GlobalVariable(PtrJBList, false,
 114                                       GlobalValue::LinkOnceLinkage,
 115                                       Constant::getNullValue(PtrJBList),
 116                                       "llvm.sjljeh.jblist", &M);
 117     SetJmpFn = M.getOrInsertFunction("llvm.setjmp", Type::IntTy,
 118                                      PointerType::get(JmpBufTy), 0);
 119     LongJmpFn = M.getOrInsertFunction("llvm.longjmp", Type::VoidTy,
 120                                       PointerType::get(JmpBufTy),
 121                                       Type::IntTy, 0);
 122
 123     // The abort message for expensive EH support tells the user that the
 124     // program 'unwound' without an 'invoke' instruction.
 125     Constant *Msg =
 126       ConstantArray::get("ERROR: Exception thrown, but not caught!\n");
 127     AbortMessageLength = Msg->getNumOperands()-1;  // don't include \0
 128     AbortMessageInit = Msg;
 129
 130     GlobalVariable *MsgGV = M.getGlobalVariable("abort.msg", Msg->getType());
 131     if (MsgGV && (!MsgGV->hasInitializer() || MsgGV->getInitializer() != Msg))
 132       MsgGV = 0;
 133
 134     if (MsgGV) {
 135       std::vector<Constant*> GEPIdx(2, Constant::getNullValue(Type::LongTy));
 136       AbortMessage =
 137         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(MsgGV), GEPIdx);
 138     }
 139
 140   } else {
 141     // The abort message for cheap EH support tells the user that EH is not
 142     // enabled.
 143     Constant *Msg =
 144       ConstantArray::get("Exception handler needed, but not enabled.  Recompile"
 145                          " program with -enable-correct-eh-support.\n");
 146     AbortMessageLength = Msg->getNumOperands()-1;  // don't include \0
 147     AbortMessageInit = Msg;
 148
 149     GlobalVariable *MsgGV = M.getGlobalVariable("abort.msg", Msg->getType());
 150     if (MsgGV && (!MsgGV->hasInitializer() || MsgGV->getInitializer() != Msg))
 151       MsgGV = 0;
 152
 153     if (MsgGV) {
 154       std::vector<Constant*> GEPIdx(2, Constant::getNullValue(Type::LongTy));
 155       AbortMessage =
 156         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(MsgGV), GEPIdx);
 157     }
 158   }
 159
 160   // We need the 'write' and 'abort' functions for both models.
 161   AbortFn = M.getOrInsertFunction("abort", Type::VoidTy, 0);
 162
 163   // Unfortunately, 'write' can end up being prototyped in several different
 164   // ways.  If the user defines a three (or more) operand function named 'write'
 165   // we will use their prototype.  We _do not_ want to insert another instance
 166   // of a write prototype, because we don't know that the funcresolve pass will
 167   // run after us.  If there is a definition of a write function, but it's not
 168   // suitable for our uses, we just don't emit write calls.  If there is no
 169   // write prototype at all, we just add one.
 170   if (Function *WF = M.getNamedFunction("write")) {
 171     if (WF->getFunctionType()->getNumParams() > 3 ||
 172         WF->getFunctionType()->isVarArg())
 173       WriteFn = WF;
 174     else
 175       WriteFn = 0;
 176   } else {
 177     WriteFn = M.getOrInsertFunction("write", Type::VoidTy, Type::IntTy,
 178                                     VoidPtrTy, Type::IntTy, 0);
 179   }
 180   return true;
 181 }
 182
 183 void LowerInvoke::writeAbortMessage(Instruction *IB) {
 184   if (WriteFn) {
 185     if (!AbortMessage) {
 186       GlobalVariable *MsgGV = new GlobalVariable(AbortMessageInit->getType(),
 187                                                  true,
 188                                                  GlobalValue::InternalLinkage,
 189                                                  AbortMessageInit, "abort.msg",
 190                                                  WriteFn->getParent());
 191       std::vector<Constant*> GEPIdx(2, Constant::getNullValue(Type::LongTy));
 192       AbortMessage =
 193         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(MsgGV), GEPIdx);
 194     }
 195
 196     // These are the arguments we WANT...
 197     std::vector<Value*> Args;
 198     Args.push_back(ConstantInt::get(Type::IntTy, 2));
 199     Args.push_back(AbortMessage);
 200     Args.push_back(ConstantInt::get(Type::IntTy, AbortMessageLength));
 201
 202     // If the actual declaration of write disagrees, insert casts as
 203     // appropriate.
 204     const FunctionType *FT = WriteFn->getFunctionType();
 205     unsigned NumArgs = FT->getNumParams();
 206     for (unsigned i = 0; i != 3; ++i)
 207       if (i < NumArgs && FT->getParamType(i) != Args[i]->getType())
 208         Args[i] = ConstantExpr::getCast(cast<Constant>(Args[i]),
 209                                         FT->getParamType(i));
 210
 211     new CallInst(WriteFn, Args, "", IB);
 212   }
 213 }
 214
 215 bool LowerInvoke::insertCheapEHSupport(Function &F) {
 216   bool Changed = false;
 217   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 218     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
 219       // Insert a normal call instruction...
 220       std::string Name = II->getName(); II->setName("");
 221       Value *NewCall = new CallInst(II->getCalledValue(),
 222                                     std::vector<Value*>(II->op_begin()+3,
 223                                                         II->op_end()), Name,II);
 224       II->replaceAllUsesWith(NewCall);
 225
 226       // Insert an unconditional branch to the normal destination.
 227       new BranchInst(II->getNormalDest(), II);
 228
 229       // Remove any PHI node entries from the exception destination.
 230       II->getUnwindDest()->removePredecessor(BB);
 231
 232       // Remove the invoke instruction now.
 233       BB->getInstList().erase(II);
 234
 235       ++NumLowered; Changed = true;
 236     } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
 237       // Insert a new call to write(2, AbortMessage, AbortMessageLength);
 238       writeAbortMessage(UI);
 239
 240       // Insert a call to abort()
 241       new CallInst(AbortFn, std::vector<Value*>(), "", UI);
 242
 243       // Insert a return instruction.  This really should be a "barrier", as it
 244       // is unreachable.
 245       new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
 246                             Constant::getNullValue(F.getReturnType()), UI);
 247
 248       // Remove the unwind instruction now.
 249       BB->getInstList().erase(UI);
 250
 251       ++NumLowered; Changed = true;
 252     }
 253   return Changed;
 254 }
 255
 256 bool LowerInvoke::insertExpensiveEHSupport(Function &F) {
 257   bool Changed = false;
 258
 259   // If a function uses invoke, we have an alloca for the jump buffer.
 260   AllocaInst *JmpBuf = 0;
 261
 262   // If this function contains an unwind instruction, two blocks get added: one
 263   // to actually perform the longjmp, and one to terminate the program if there
 264   // is no handler.
 265   BasicBlock *UnwindBlock = 0, *TermBlock = 0;
 266   std::vector<LoadInst*> JBPtrs;
 267
 268   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 269     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
 270       if (JmpBuf == 0)
 271         JmpBuf = new AllocaInst(JBLinkTy, 0, "jblink", F.begin()->begin());
 272
 273       // On the entry to the invoke, we must install our JmpBuf as the top of
 274       // the stack.
 275       LoadInst *OldEntry = new LoadInst(JBListHead, "oldehlist", II);
 276
 277       // Store this old value as our 'next' field, and store our alloca as the
 278       // current jblist.
 279       std::vector<Value*> Idx;
 280       Idx.push_back(Constant::getNullValue(Type::LongTy));
 281       Idx.push_back(ConstantUInt::get(Type::UByteTy, 0));
 282       Value *NextFieldPtr = new GetElementPtrInst(JmpBuf, Idx, "NextField", II);
 283       new StoreInst(OldEntry, NextFieldPtr, II);
 284       new StoreInst(JmpBuf, JBListHead, II);
 285
 286       // Call setjmp, passing in the address of the jmpbuffer.
 287       Idx[1] = ConstantUInt::get(Type::UByteTy, 1);
 288       Value *JmpBufPtr = new GetElementPtrInst(JmpBuf, Idx, "TheJmpBuf", II);
 289       Value *SJRet = new CallInst(SetJmpFn, JmpBufPtr, "sjret", II);
 290
 291       // Compare the return value to zero.
 292       Value *IsNormal = BinaryOperator::create(Instruction::SetEQ, SJRet,
 293                                        Constant::getNullValue(SJRet->getType()),
 294                                                "notunwind", II);
 295       // Create the receiver block if there is a critical edge to the normal
 296       // destination.
 297       SplitCriticalEdge(II, 0, this);
 298       Instruction *InsertLoc = II->getNormalDest()->begin();
 299
 300       // Insert a normal call instruction on the normal execution path.
 301       std::string Name = II->getName(); II->setName("");
 302       Value *NewCall = new CallInst(II->getCalledValue(),
 303                                     std::vector<Value*>(II->op_begin()+3,
 304                                                         II->op_end()), Name,
 305                                     InsertLoc);
 306       II->replaceAllUsesWith(NewCall);
 307
 308       // If we got this far, then no exception was thrown and we can pop our
 309       // jmpbuf entry off.
 310       new StoreInst(OldEntry, JBListHead, InsertLoc);
 311
 312       // Now we change the invoke into a branch instruction.
 313       new BranchInst(II->getNormalDest(), II->getUnwindDest(), IsNormal, II);
 314
 315       // Remove the InvokeInst now.
 316       BB->getInstList().erase(II);
 317       ++NumLowered; Changed = true;
 318
 319     } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
 320       if (UnwindBlock == 0) {
 321         // Create two new blocks, the unwind block and the terminate block.  Add
 322         // them at the end of the function because they are not hot.
 323         UnwindBlock = new BasicBlock("unwind", &F);
 324         TermBlock = new BasicBlock("unwinderror", &F);
 325
 326         // Insert return instructions.  These really should be "barrier"s, as
 327         // they are unreachable.
 328         new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
 329                        Constant::getNullValue(F.getReturnType()), UnwindBlock);
 330         new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
 331                        Constant::getNullValue(F.getReturnType()), TermBlock);
 332       }
 333
 334       // Load the JBList, if it's null, then there was no catch!
 335       LoadInst *Ptr = new LoadInst(JBListHead, "ehlist", UI);
 336       Value *NotNull = BinaryOperator::create(Instruction::SetNE, Ptr,
 337                                         Constant::getNullValue(Ptr->getType()),
 338                                               "notnull", UI);
 339       new BranchInst(UnwindBlock, TermBlock, NotNull, UI);
 340
 341       // Remember the loaded value so we can insert the PHI node as needed.
 342       JBPtrs.push_back(Ptr);
 343
 344       // Remove the UnwindInst now.
 345       BB->getInstList().erase(UI);
 346       ++NumLowered; Changed = true;
 347     }
 348
 349   // If an unwind instruction was inserted, we need to set up the Unwind and
 350   // term blocks.
 351   if (UnwindBlock) {
 352     // In the unwind block, we know that the pointer coming in on the JBPtrs
 353     // list are non-null.
 354     Instruction *RI = UnwindBlock->getTerminator();
 355
 356     Value *RecPtr;
 357     if (JBPtrs.size() == 1)
 358       RecPtr = JBPtrs[0];
 359     else {
 360       // If there is more than one unwind in this function, make a PHI node to
 361       // merge in all of the loaded values.
 362       PHINode *PN = new PHINode(JBPtrs[0]->getType(), "jbptrs", RI);
 363       for (unsigned i = 0, e = JBPtrs.size(); i != e; ++i)
 364         PN->addIncoming(JBPtrs[i], JBPtrs[i]->getParent());
 365       RecPtr = PN;
 366     }
 367
 368     // Now that we have a pointer to the whole record, remove the entry from the
 369     // JBList.
 370     std::vector<Value*> Idx;
 371     Idx.push_back(Constant::getNullValue(Type::LongTy));
 372     Idx.push_back(ConstantUInt::get(Type::UByteTy, 0));
 373     Value *NextFieldPtr = new GetElementPtrInst(RecPtr, Idx, "NextField", RI);
 374     Value *NextRec = new LoadInst(NextFieldPtr, "NextRecord", RI);
 375     new StoreInst(NextRec, JBListHead, RI);
 376
 377     // Now that we popped the top of the JBList, get a pointer to the jmpbuf and
 378     // longjmp.
 379     Idx[1] = ConstantUInt::get(Type::UByteTy, 1);
 380     Idx[0] = new GetElementPtrInst(RecPtr, Idx, "JmpBuf", RI);
 381     Idx[1] = ConstantInt::get(Type::IntTy, 1);
 382     new CallInst(LongJmpFn, Idx, "", RI);
 383
 384     // Now we set up the terminate block.
 385     RI = TermBlock->getTerminator();
 386
 387     // Insert a new call to write(2, AbortMessage, AbortMessageLength);
 388     writeAbortMessage(RI);
 389
 390     // Insert a call to abort()
 391     new CallInst(AbortFn, std::vector<Value*>(), "", RI);
 392   }
 393
 394   return Changed;
 395 }
 396
 397 bool LowerInvoke::runOnFunction(Function &F) {
 398   if (ExpensiveEHSupport)
 399     return insertExpensiveEHSupport(F);
 400   else
 401     return insertCheapEHSupport(F);
 402 }