LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

LowerInvoke.cpp

Go to the documentation of this file.
00001 //===- LowerInvoke.cpp - Eliminate Invoke & Unwind instructions -----------===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This transformation is designed for use by code generators which do not yet
00011 // support stack unwinding.  This pass supports two models of exception handling
00012 // lowering, the 'cheap' support and the 'expensive' support.
00013 //
00014 // 'Cheap' exception handling support gives the program the ability to execute
00015 // any program which does not "throw an exception", by turning 'invoke'
00016 // instructions into calls and by turning 'unwind' instructions into calls to
00017 // abort().  If the program does dynamically use the unwind instruction, the
00018 // program will print a message then abort.
00019 //
00020 // 'Expensive' exception handling support gives the full exception handling
00021 // support to the program at making the 'invoke' instruction really expensive.
00022 // It basically inserts setjmp/longjmp calls to emulate the exception handling
00023 // as necessary.
00024 //
00025 // Because the 'expensive' support slows down programs a lot, and EH is only
00026 // used for a subset of the programs, it must be specifically enabled by an
00027 // option.
00028 //
00029 // Note that after this pass runs the CFG is not entirely accurate (exceptional
00030 // control flow edges are not correct anymore) so only very simple things should
00031 // be done after the lowerinvoke pass has run (like generation of native code).
00032 // This should not be used as a general purpose "my LLVM-to-LLVM pass doesn't
00033 // support the invoke instruction yet" lowering pass.
00034 //
00035 //===----------------------------------------------------------------------===//
00036 
00037 #include "llvm/Transforms/Scalar.h"
00038 #include "llvm/Constants.h"
00039 #include "llvm/DerivedTypes.h"
00040 #include "llvm/Instructions.h"
00041 #include "llvm/Module.h"
00042 #include "llvm/Pass.h"
00043 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00044 #include "llvm/ADT/Statistic.h"
00045 #include "llvm/Support/CommandLine.h"
00046 #include <csetjmp>
00047 using namespace llvm;
00048 
00049 namespace {
00050   Statistic<> NumLowered("lowerinvoke", "Number of invoke & unwinds replaced");
00051   cl::opt<bool> ExpensiveEHSupport("enable-correct-eh-support",
00052  cl::desc("Make the -lowerinvoke pass insert expensive, but correct, EH code"));
00053 
00054   class LowerInvoke : public FunctionPass {
00055     // Used for both models.
00056     Function *WriteFn;
00057     Function *AbortFn;
00058     Value *AbortMessage;
00059     unsigned AbortMessageLength;
00060 
00061     // Used for expensive EH support.
00062     const Type *JBLinkTy;
00063     GlobalVariable *JBListHead;
00064     Function *SetJmpFn, *LongJmpFn;
00065   public:
00066     bool doInitialization(Module &M);
00067     bool runOnFunction(Function &F);
00068   private:
00069     void createAbortMessage();
00070     void writeAbortMessage(Instruction *IB);
00071     bool insertCheapEHSupport(Function &F);
00072     bool insertExpensiveEHSupport(Function &F);
00073   };
00074 
00075   RegisterOpt<LowerInvoke>
00076   X("lowerinvoke", "Lower invoke and unwind, for unwindless code generators");
00077 }
00078 
00079 const PassInfo *llvm::LowerInvokePassID = X.getPassInfo();
00080 
00081 // Public Interface To the LowerInvoke pass.
00082 FunctionPass *llvm::createLowerInvokePass() { return new LowerInvoke(); }
00083 
00084 // doInitialization - Make sure that there is a prototype for abort in the
00085 // current module.
00086 bool LowerInvoke::doInitialization(Module &M) {
00087   const Type *VoidPtrTy = PointerType::get(Type::SByteTy);
00088   AbortMessage = 0;
00089   if (ExpensiveEHSupport) {
00090     // Insert a type for the linked list of jump buffers.  Unfortunately, we
00091     // don't know the size of the target's setjmp buffer, so we make a guess.
00092     // If this guess turns out to be too small, bad stuff could happen.
00093     unsigned JmpBufSize = 200;  // PPC has 192 words
00094     assert(sizeof(jmp_buf) <= JmpBufSize*sizeof(void*) &&
00095        "LowerInvoke doesn't know about targets with jmp_buf size > 200 words!");
00096     const Type *JmpBufTy = ArrayType::get(VoidPtrTy, JmpBufSize);
00097 
00098     { // The type is recursive, so use a type holder.
00099       std::vector<const Type*> Elements;
00100       OpaqueType *OT = OpaqueType::get();
00101       Elements.push_back(PointerType::get(OT));
00102       Elements.push_back(JmpBufTy);
00103       PATypeHolder JBLType(StructType::get(Elements));
00104       OT->refineAbstractTypeTo(JBLType.get());  // Complete the cycle.
00105       JBLinkTy = JBLType.get();
00106       M.addTypeName("llvm.sjljeh.jmpbufty", JBLinkTy);
00107     }
00108 
00109     const Type *PtrJBList = PointerType::get(JBLinkTy);
00110 
00111     // Now that we've done that, insert the jmpbuf list head global, unless it
00112     // already exists.
00113     if (!(JBListHead = M.getGlobalVariable("llvm.sjljeh.jblist", PtrJBList)))
00114       JBListHead = new GlobalVariable(PtrJBList, false,
00115                                       GlobalValue::LinkOnceLinkage,
00116                                       Constant::getNullValue(PtrJBList),
00117                                       "llvm.sjljeh.jblist", &M);
00118     SetJmpFn = M.getOrInsertFunction("llvm.setjmp", Type::IntTy,
00119                                      PointerType::get(JmpBufTy), 0);
00120     LongJmpFn = M.getOrInsertFunction("llvm.longjmp", Type::VoidTy,
00121                                       PointerType::get(JmpBufTy),
00122                                       Type::IntTy, 0);
00123   }
00124 
00125   // We need the 'write' and 'abort' functions for both models.
00126   AbortFn = M.getOrInsertFunction("abort", Type::VoidTy, 0);
00127 
00128   // Unfortunately, 'write' can end up being prototyped in several different
00129   // ways.  If the user defines a three (or more) operand function named 'write'
00130   // we will use their prototype.  We _do not_ want to insert another instance
00131   // of a write prototype, because we don't know that the funcresolve pass will
00132   // run after us.  If there is a definition of a write function, but it's not
00133   // suitable for our uses, we just don't emit write calls.  If there is no
00134   // write prototype at all, we just add one.
00135   if (Function *WF = M.getNamedFunction("write")) {
00136     if (WF->getFunctionType()->getNumParams() > 3 ||
00137         WF->getFunctionType()->isVarArg())
00138       WriteFn = WF;
00139     else
00140       WriteFn = 0;
00141   } else {
00142     WriteFn = M.getOrInsertFunction("write", Type::VoidTy, Type::IntTy,
00143                                     VoidPtrTy, Type::IntTy, 0);
00144   }
00145   return true;
00146 }
00147 
00148 void LowerInvoke::createAbortMessage() {
00149   Module &M = *WriteFn->getParent();
00150   if (ExpensiveEHSupport) {
00151     // The abort message for expensive EH support tells the user that the
00152     // program 'unwound' without an 'invoke' instruction.
00153     Constant *Msg =
00154       ConstantArray::get("ERROR: Exception thrown, but not caught!\n");
00155     AbortMessageLength = Msg->getNumOperands()-1;  // don't include \0
00156     
00157     GlobalVariable *MsgGV = new GlobalVariable(Msg->getType(), true,
00158                                                GlobalValue::InternalLinkage,
00159                                                Msg, "abortmsg", &M);
00160     std::vector<Constant*> GEPIdx(2, Constant::getNullValue(Type::LongTy));
00161     AbortMessage = ConstantExpr::getGetElementPtr(MsgGV, GEPIdx);
00162   } else {
00163     // The abort message for cheap EH support tells the user that EH is not
00164     // enabled.
00165     Constant *Msg =
00166       ConstantArray::get("Exception handler needed, but not enabled.  Recompile"
00167                          " program with -enable-correct-eh-support.\n");
00168     AbortMessageLength = Msg->getNumOperands()-1;  // don't include \0
00169 
00170     GlobalVariable *MsgGV = new GlobalVariable(Msg->getType(), true,
00171                                                GlobalValue::InternalLinkage,
00172                                                Msg, "abortmsg", &M);
00173     std::vector<Constant*> GEPIdx(2, Constant::getNullValue(Type::LongTy));
00174     AbortMessage = ConstantExpr::getGetElementPtr(MsgGV, GEPIdx);
00175   }
00176 }
00177 
00178 
00179 void LowerInvoke::writeAbortMessage(Instruction *IB) {
00180   if (WriteFn) {
00181     if (AbortMessage == 0) createAbortMessage();
00182 
00183     // These are the arguments we WANT...
00184     std::vector<Value*> Args;
00185     Args.push_back(ConstantInt::get(Type::IntTy, 2));
00186     Args.push_back(AbortMessage);
00187     Args.push_back(ConstantInt::get(Type::IntTy, AbortMessageLength));
00188 
00189     // If the actual declaration of write disagrees, insert casts as
00190     // appropriate.
00191     const FunctionType *FT = WriteFn->getFunctionType();
00192     unsigned NumArgs = FT->getNumParams();
00193     for (unsigned i = 0; i != 3; ++i)
00194       if (i < NumArgs && FT->getParamType(i) != Args[i]->getType())
00195         Args[i] = ConstantExpr::getCast(cast<Constant>(Args[i]), 
00196                                         FT->getParamType(i));
00197 
00198     new CallInst(WriteFn, Args, "", IB);
00199   }
00200 }
00201 
00202 bool LowerInvoke::insertCheapEHSupport(Function &F) {
00203   bool Changed = false;
00204   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00205     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
00206       // Insert a normal call instruction...
00207       std::string Name = II->getName(); II->setName("");
00208       Value *NewCall = new CallInst(II->getCalledValue(),
00209                                     std::vector<Value*>(II->op_begin()+3,
00210                                                         II->op_end()), Name,II);
00211       II->replaceAllUsesWith(NewCall);
00212       
00213       // Insert an unconditional branch to the normal destination.
00214       new BranchInst(II->getNormalDest(), II);
00215 
00216       // Remove any PHI node entries from the exception destination.
00217       II->getUnwindDest()->removePredecessor(BB);
00218 
00219       // Remove the invoke instruction now.
00220       BB->getInstList().erase(II);
00221 
00222       ++NumLowered; Changed = true;
00223     } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
00224       // Insert a new call to write(2, AbortMessage, AbortMessageLength);
00225       writeAbortMessage(UI);
00226 
00227       // Insert a call to abort()
00228       new CallInst(AbortFn, std::vector<Value*>(), "", UI);
00229 
00230       // Insert a return instruction.  This really should be a "barrier", as it
00231       // is unreachable.
00232       new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
00233                             Constant::getNullValue(F.getReturnType()), UI);
00234 
00235       // Remove the unwind instruction now.
00236       BB->getInstList().erase(UI);
00237 
00238       ++NumLowered; Changed = true;
00239     }
00240   return Changed;
00241 }
00242 
00243 bool LowerInvoke::insertExpensiveEHSupport(Function &F) {
00244   bool Changed = false;
00245 
00246   // If a function uses invoke, we have an alloca for the jump buffer.
00247   AllocaInst *JmpBuf = 0;
00248 
00249   // If this function contains an unwind instruction, two blocks get added: one
00250   // to actually perform the longjmp, and one to terminate the program if there
00251   // is no handler.
00252   BasicBlock *UnwindBlock = 0, *TermBlock = 0;
00253   std::vector<LoadInst*> JBPtrs;
00254 
00255   for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
00256     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
00257       if (JmpBuf == 0)
00258         JmpBuf = new AllocaInst(JBLinkTy, 0, "jblink", F.begin()->begin());
00259 
00260       // On the entry to the invoke, we must install our JmpBuf as the top of
00261       // the stack.
00262       LoadInst *OldEntry = new LoadInst(JBListHead, "oldehlist", II);
00263 
00264       // Store this old value as our 'next' field, and store our alloca as the
00265       // current jblist.
00266       std::vector<Value*> Idx;
00267       Idx.push_back(Constant::getNullValue(Type::IntTy));
00268       Idx.push_back(ConstantUInt::get(Type::UIntTy, 0));
00269       Value *NextFieldPtr = new GetElementPtrInst(JmpBuf, Idx, "NextField", II);
00270       new StoreInst(OldEntry, NextFieldPtr, II);
00271       new StoreInst(JmpBuf, JBListHead, II);
00272       
00273       // Call setjmp, passing in the address of the jmpbuffer.
00274       Idx[1] = ConstantUInt::get(Type::UIntTy, 1);
00275       Value *JmpBufPtr = new GetElementPtrInst(JmpBuf, Idx, "TheJmpBuf", II);
00276       Value *SJRet = new CallInst(SetJmpFn, JmpBufPtr, "sjret", II);
00277 
00278       // Compare the return value to zero.
00279       Value *IsNormal = BinaryOperator::create(Instruction::SetEQ, SJRet,
00280                                        Constant::getNullValue(SJRet->getType()),
00281                                                "notunwind", II);
00282       // Create the receiver block if there is a critical edge to the normal
00283       // destination.
00284       SplitCriticalEdge(II, 0, this);
00285       Instruction *InsertLoc = II->getNormalDest()->begin();
00286       
00287       // Insert a normal call instruction on the normal execution path.
00288       std::string Name = II->getName(); II->setName("");
00289       Value *NewCall = new CallInst(II->getCalledValue(),
00290                                     std::vector<Value*>(II->op_begin()+3,
00291                                                         II->op_end()), Name,
00292                                     InsertLoc);
00293       II->replaceAllUsesWith(NewCall);
00294       
00295       // If we got this far, then no exception was thrown and we can pop our
00296       // jmpbuf entry off.
00297       new StoreInst(OldEntry, JBListHead, InsertLoc);
00298 
00299       // Now we change the invoke into a branch instruction.
00300       new BranchInst(II->getNormalDest(), II->getUnwindDest(), IsNormal, II);
00301 
00302       // Remove the InvokeInst now.
00303       BB->getInstList().erase(II);
00304       ++NumLowered; Changed = true;      
00305       
00306     } else if (UnwindInst *UI = dyn_cast<UnwindInst>(BB->getTerminator())) {
00307       if (UnwindBlock == 0) {
00308         // Create two new blocks, the unwind block and the terminate block.  Add
00309         // them at the end of the function because they are not hot.
00310         UnwindBlock = new BasicBlock("unwind", &F);
00311         TermBlock = new BasicBlock("unwinderror", &F);
00312 
00313         // Insert return instructions.  These really should be "barrier"s, as
00314         // they are unreachable.
00315         new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
00316                        Constant::getNullValue(F.getReturnType()), UnwindBlock);
00317         new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 :
00318                        Constant::getNullValue(F.getReturnType()), TermBlock);
00319       }
00320 
00321       // Load the JBList, if it's null, then there was no catch!
00322       LoadInst *Ptr = new LoadInst(JBListHead, "ehlist", UI);
00323       Value *NotNull = BinaryOperator::create(Instruction::SetNE, Ptr,
00324                                         Constant::getNullValue(Ptr->getType()),
00325                                               "notnull", UI);
00326       new BranchInst(UnwindBlock, TermBlock, NotNull, UI);
00327 
00328       // Remember the loaded value so we can insert the PHI node as needed.
00329       JBPtrs.push_back(Ptr);
00330 
00331       // Remove the UnwindInst now.
00332       BB->getInstList().erase(UI);
00333       ++NumLowered; Changed = true;      
00334     }
00335 
00336   // If an unwind instruction was inserted, we need to set up the Unwind and
00337   // term blocks.
00338   if (UnwindBlock) {
00339     // In the unwind block, we know that the pointer coming in on the JBPtrs
00340     // list are non-null.
00341     Instruction *RI = UnwindBlock->getTerminator();
00342 
00343     Value *RecPtr;
00344     if (JBPtrs.size() == 1)
00345       RecPtr = JBPtrs[0];
00346     else {
00347       // If there is more than one unwind in this function, make a PHI node to
00348       // merge in all of the loaded values.
00349       PHINode *PN = new PHINode(JBPtrs[0]->getType(), "jbptrs", RI);
00350       for (unsigned i = 0, e = JBPtrs.size(); i != e; ++i)
00351         PN->addIncoming(JBPtrs[i], JBPtrs[i]->getParent());
00352       RecPtr = PN;
00353     }
00354 
00355     // Now that we have a pointer to the whole record, remove the entry from the
00356     // JBList.
00357     std::vector<Value*> Idx;
00358     Idx.push_back(Constant::getNullValue(Type::LongTy));
00359     Idx.push_back(ConstantUInt::get(Type::UIntTy, 0));
00360     Value *NextFieldPtr = new GetElementPtrInst(RecPtr, Idx, "NextField", RI);
00361     Value *NextRec = new LoadInst(NextFieldPtr, "NextRecord", RI);
00362     new StoreInst(NextRec, JBListHead, RI);
00363 
00364     // Now that we popped the top of the JBList, get a pointer to the jmpbuf and
00365     // longjmp.
00366     Idx[1] = ConstantUInt::get(Type::UIntTy, 1);
00367     Idx[0] = new GetElementPtrInst(RecPtr, Idx, "JmpBuf", RI);
00368     Idx[1] = ConstantInt::get(Type::IntTy, 1);
00369     new CallInst(LongJmpFn, Idx, "", RI);
00370 
00371     // Now we set up the terminate block.
00372     RI = TermBlock->getTerminator();
00373     
00374     // Insert a new call to write(2, AbortMessage, AbortMessageLength);
00375     writeAbortMessage(RI);
00376 
00377     // Insert a call to abort()
00378     new CallInst(AbortFn, std::vector<Value*>(), "", RI);
00379   }
00380 
00381   return Changed;
00382 }
00383 
00384 bool LowerInvoke::runOnFunction(Function &F) {
00385   if (ExpensiveEHSupport)
00386     return insertExpensiveEHSupport(F);
00387   else
00388     return insertCheapEHSupport(F);
00389 }