X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FLowerInvoke.cpp;h=4ecf6d7ba2604de466159f46f244059e8912c377;hb=fd5249e15bfea699a146c2b7642081deb229465c;hp=2738b4aa5e3b762b98e3e1eeaa4232d11f7718c4;hpb=1381dd8a6eeb882db92024a46cdbd6689ea1cd94;p=oota-llvm.git diff --git a/lib/Transforms/Utils/LowerInvoke.cpp b/lib/Transforms/Utils/LowerInvoke.cpp index 2738b4aa5e3..4ecf6d7ba26 100644 --- a/lib/Transforms/Utils/LowerInvoke.cpp +++ b/lib/Transforms/Utils/LowerInvoke.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -34,184 +34,211 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "lowerinvoke" #include "llvm/Transforms/Scalar.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/Instructions.h" +#include "llvm/Intrinsics.h" +#include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Local.h" #include "llvm/ADT/Statistic.h" #include "llvm/Support/CommandLine.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Target/TargetLowering.h" #include +#include using namespace llvm; -namespace { - Statistic<> NumLowered("lowerinvoke", "Number of invoke & unwinds replaced"); - cl::opt ExpensiveEHSupport("enable-correct-eh-support", +STATISTIC(NumInvokes, "Number of invokes replaced"); +STATISTIC(NumUnwinds, "Number of unwinds replaced"); +STATISTIC(NumSpilled, "Number of registers live across unwind edges"); + +static cl::opt ExpensiveEHSupport("enable-correct-eh-support", cl::desc("Make the -lowerinvoke pass insert expensive, but correct, EH code")); - class LowerInvoke : public FunctionPass { +namespace { + class VISIBILITY_HIDDEN LowerInvoke : public FunctionPass { // Used for both models. - Function *WriteFn; - Function *AbortFn; + Constant *WriteFn; + Constant *AbortFn; Value *AbortMessage; unsigned AbortMessageLength; // Used for expensive EH support. const Type *JBLinkTy; GlobalVariable *JBListHead; - Function *SetJmpFn, *LongJmpFn; + Constant *SetJmpFn, *LongJmpFn; + + // We peek in TLI to grab the target's jmp_buf size and alignment + const TargetLowering *TLI; + public: + static char ID; // Pass identification, replacement for typeid + explicit LowerInvoke(const TargetLowering *tli = NULL) + : FunctionPass(&ID), TLI(tli) { } bool doInitialization(Module &M); bool runOnFunction(Function &F); + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + // This is a cluster of orthogonal Transforms + AU.addPreservedID(PromoteMemoryToRegisterID); + AU.addPreservedID(LowerSwitchID); + AU.addPreservedID(LowerAllocationsID); + } + private: - void createAbortMessage(); + void createAbortMessage(Module *M); void writeAbortMessage(Instruction *IB); bool insertCheapEHSupport(Function &F); + void splitLiveRangesLiveAcrossInvokes(std::vector &Invokes); + void rewriteExpensiveInvoke(InvokeInst *II, unsigned InvokeNo, + AllocaInst *InvokeNum, SwitchInst *CatchSwitch); bool insertExpensiveEHSupport(Function &F); }; - - RegisterOpt - X("lowerinvoke", "Lower invoke and unwind, for unwindless code generators"); } -const PassInfo *llvm::LowerInvokePassID = X.getPassInfo(); +char LowerInvoke::ID = 0; +static RegisterPass +X("lowerinvoke", "Lower invoke and unwind, for unwindless code generators"); + +const PassInfo *const llvm::LowerInvokePassID = &X; // Public Interface To the LowerInvoke pass. -FunctionPass *llvm::createLowerInvokePass() { return new LowerInvoke(); } +FunctionPass *llvm::createLowerInvokePass(const TargetLowering *TLI) { + return new LowerInvoke(TLI); +} // doInitialization - Make sure that there is a prototype for abort in the // current module. bool LowerInvoke::doInitialization(Module &M) { - const Type *VoidPtrTy = PointerType::get(Type::SByteTy); + const Type *VoidPtrTy = + PointerType::getUnqual(Type::getInt8Ty(M.getContext())); AbortMessage = 0; if (ExpensiveEHSupport) { - // Insert a type for the linked list of jump buffers. Unfortunately, we - // don't know the size of the target's setjmp buffer, so we make a guess. - // If this guess turns out to be too small, bad stuff could happen. - unsigned JmpBufSize = 200; // PPC has 192 words - assert(sizeof(jmp_buf) <= JmpBufSize*sizeof(void*) && - "LowerInvoke doesn't know about targets with jmp_buf size > 200 words!"); - const Type *JmpBufTy = ArrayType::get(VoidPtrTy, JmpBufSize); + // Insert a type for the linked list of jump buffers. + unsigned JBSize = TLI ? TLI->getJumpBufSize() : 0; + JBSize = JBSize ? JBSize : 200; + const Type *JmpBufTy = ArrayType::get(VoidPtrTy, JBSize); { // The type is recursive, so use a type holder. std::vector Elements; - OpaqueType *OT = OpaqueType::get(); - Elements.push_back(PointerType::get(OT)); Elements.push_back(JmpBufTy); - PATypeHolder JBLType(StructType::get(Elements)); + OpaqueType *OT = OpaqueType::get(M.getContext()); + Elements.push_back(PointerType::getUnqual(OT)); + PATypeHolder JBLType(StructType::get(M.getContext(), Elements)); OT->refineAbstractTypeTo(JBLType.get()); // Complete the cycle. JBLinkTy = JBLType.get(); M.addTypeName("llvm.sjljeh.jmpbufty", JBLinkTy); } - const Type *PtrJBList = PointerType::get(JBLinkTy); + const Type *PtrJBList = PointerType::getUnqual(JBLinkTy); // Now that we've done that, insert the jmpbuf list head global, unless it // already exists. - if (!(JBListHead = M.getGlobalVariable("llvm.sjljeh.jblist", PtrJBList))) - JBListHead = new GlobalVariable(PtrJBList, false, - GlobalValue::LinkOnceLinkage, + if (!(JBListHead = M.getGlobalVariable("llvm.sjljeh.jblist", PtrJBList))) { + JBListHead = new GlobalVariable(M, PtrJBList, false, + GlobalValue::LinkOnceAnyLinkage, Constant::getNullValue(PtrJBList), - "llvm.sjljeh.jblist", &M); - SetJmpFn = M.getOrInsertFunction("llvm.setjmp", Type::IntTy, - PointerType::get(JmpBufTy), 0); - LongJmpFn = M.getOrInsertFunction("llvm.longjmp", Type::VoidTy, - PointerType::get(JmpBufTy), - Type::IntTy, 0); + "llvm.sjljeh.jblist"); + } + +// VisualStudio defines setjmp as _setjmp via #include / , +// so it looks like Intrinsic::_setjmp +#if defined(_MSC_VER) && defined(setjmp) +#define setjmp_undefined_for_visual_studio +#undef setjmp +#endif + + SetJmpFn = Intrinsic::getDeclaration(&M, Intrinsic::setjmp); + +#if defined(_MSC_VER) && defined(setjmp_undefined_for_visual_studio) +// let's return it to _setjmp state in case anyone ever needs it after this +// point under VisualStudio +#define setjmp _setjmp +#endif + + LongJmpFn = Intrinsic::getDeclaration(&M, Intrinsic::longjmp); } // We need the 'write' and 'abort' functions for both models. - AbortFn = M.getOrInsertFunction("abort", Type::VoidTy, 0); - - // Unfortunately, 'write' can end up being prototyped in several different - // ways. If the user defines a three (or more) operand function named 'write' - // we will use their prototype. We _do not_ want to insert another instance - // of a write prototype, because we don't know that the funcresolve pass will - // run after us. If there is a definition of a write function, but it's not - // suitable for our uses, we just don't emit write calls. If there is no - // write prototype at all, we just add one. - if (Function *WF = M.getNamedFunction("write")) { - if (WF->getFunctionType()->getNumParams() > 3 || - WF->getFunctionType()->isVarArg()) - WriteFn = WF; - else - WriteFn = 0; - } else { - WriteFn = M.getOrInsertFunction("write", Type::VoidTy, Type::IntTy, - VoidPtrTy, Type::IntTy, 0); - } + AbortFn = M.getOrInsertFunction("abort", Type::getVoidTy(M.getContext()), + (Type *)0); +#if 0 // "write" is Unix-specific.. code is going away soon anyway. + WriteFn = M.getOrInsertFunction("write", Type::VoidTy, Type::Int32Ty, + VoidPtrTy, Type::Int32Ty, (Type *)0); +#else + WriteFn = 0; +#endif return true; } -void LowerInvoke::createAbortMessage() { - Module &M = *WriteFn->getParent(); +void LowerInvoke::createAbortMessage(Module *M) { if (ExpensiveEHSupport) { // The abort message for expensive EH support tells the user that the // program 'unwound' without an 'invoke' instruction. Constant *Msg = - ConstantArray::get("ERROR: Exception thrown, but not caught!\n"); + ConstantArray::get(M->getContext(), + "ERROR: Exception thrown, but not caught!\n"); AbortMessageLength = Msg->getNumOperands()-1; // don't include \0 - GlobalVariable *MsgGV = new GlobalVariable(Msg->getType(), true, + GlobalVariable *MsgGV = new GlobalVariable(*M, Msg->getType(), true, GlobalValue::InternalLinkage, - Msg, "abortmsg", &M); - std::vector GEPIdx(2, Constant::getNullValue(Type::IntTy)); - AbortMessage = ConstantExpr::getGetElementPtr(MsgGV, GEPIdx); + Msg, "abortmsg"); + std::vector GEPIdx(2, + Constant::getNullValue(Type::getInt32Ty(M->getContext()))); + AbortMessage = ConstantExpr::getGetElementPtr(MsgGV, &GEPIdx[0], 2); } else { // The abort message for cheap EH support tells the user that EH is not // enabled. Constant *Msg = - ConstantArray::get("Exception handler needed, but not enabled. Recompile" - " program with -enable-correct-eh-support.\n"); + ConstantArray::get(M->getContext(), + "Exception handler needed, but not enabled." + "Recompile program with -enable-correct-eh-support.\n"); AbortMessageLength = Msg->getNumOperands()-1; // don't include \0 - GlobalVariable *MsgGV = new GlobalVariable(Msg->getType(), true, + GlobalVariable *MsgGV = new GlobalVariable(*M, Msg->getType(), true, GlobalValue::InternalLinkage, - Msg, "abortmsg", &M); - std::vector GEPIdx(2, Constant::getNullValue(Type::IntTy)); - AbortMessage = ConstantExpr::getGetElementPtr(MsgGV, GEPIdx); + Msg, "abortmsg"); + std::vector GEPIdx(2, Constant::getNullValue( + Type::getInt32Ty(M->getContext()))); + AbortMessage = ConstantExpr::getGetElementPtr(MsgGV, &GEPIdx[0], 2); } } void LowerInvoke::writeAbortMessage(Instruction *IB) { - if (WriteFn) { - if (AbortMessage == 0) createAbortMessage(); - - // These are the arguments we WANT... - std::vector Args; - Args.push_back(ConstantInt::get(Type::IntTy, 2)); - Args.push_back(AbortMessage); - Args.push_back(ConstantInt::get(Type::IntTy, AbortMessageLength)); - - // If the actual declaration of write disagrees, insert casts as - // appropriate. - const FunctionType *FT = WriteFn->getFunctionType(); - unsigned NumArgs = FT->getNumParams(); - for (unsigned i = 0; i != 3; ++i) - if (i < NumArgs && FT->getParamType(i) != Args[i]->getType()) - Args[i] = ConstantExpr::getCast(cast(Args[i]), - FT->getParamType(i)); - - (new CallInst(WriteFn, Args, "", IB))->setTailCall(); - } +#if 0 + if (AbortMessage == 0) + createAbortMessage(IB->getParent()->getParent()->getParent()); + + // These are the arguments we WANT... + Value* Args[3]; + Args[0] = ConstantInt::get(Type::Int32Ty, 2); + Args[1] = AbortMessage; + Args[2] = ConstantInt::get(Type::Int32Ty, AbortMessageLength); + (new CallInst(WriteFn, Args, 3, "", IB))->setTailCall(); +#endif } bool LowerInvoke::insertCheapEHSupport(Function &F) { bool Changed = false; for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) if (InvokeInst *II = dyn_cast(BB->getTerminator())) { + std::vector CallArgs(II->op_begin()+3, II->op_end()); // Insert a normal call instruction... - std::string Name = II->getName(); II->setName(""); - Value *NewCall = new CallInst(II->getCalledValue(), - std::vector(II->op_begin()+3, - II->op_end()), Name,II); + CallInst *NewCall = CallInst::Create(II->getCalledValue(), + CallArgs.begin(), CallArgs.end(), "",II); + NewCall->takeName(II); + NewCall->setCallingConv(II->getCallingConv()); + NewCall->setAttributes(II->getAttributes()); II->replaceAllUsesWith(NewCall); // Insert an unconditional branch to the normal destination. - new BranchInst(II->getNormalDest(), II); + BranchInst::Create(II->getNormalDest(), II); // Remove any PHI node entries from the exception destination. II->getUnwindDest()->removePredecessor(BB); @@ -219,166 +246,381 @@ bool LowerInvoke::insertCheapEHSupport(Function &F) { // Remove the invoke instruction now. BB->getInstList().erase(II); - ++NumLowered; Changed = true; + ++NumInvokes; Changed = true; } else if (UnwindInst *UI = dyn_cast(BB->getTerminator())) { // Insert a new call to write(2, AbortMessage, AbortMessageLength); writeAbortMessage(UI); // Insert a call to abort() - (new CallInst(AbortFn, std::vector(), "", UI))->setTailCall(); + CallInst::Create(AbortFn, "", UI)->setTailCall(); // Insert a return instruction. This really should be a "barrier", as it // is unreachable. - new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 : - Constant::getNullValue(F.getReturnType()), UI); + ReturnInst::Create(F.getContext(), + F.getReturnType() == Type::getVoidTy(F.getContext()) ? + 0 : Constant::getNullValue(F.getReturnType()), UI); // Remove the unwind instruction now. BB->getInstList().erase(UI); - ++NumLowered; Changed = true; + ++NumUnwinds; Changed = true; } return Changed; } -bool LowerInvoke::insertExpensiveEHSupport(Function &F) { - bool Changed = false; - - // If a function uses invoke, we have an alloca for the jump buffer. - AllocaInst *JmpBuf = 0; +/// rewriteExpensiveInvoke - Insert code and hack the function to replace the +/// specified invoke instruction with a call. +void LowerInvoke::rewriteExpensiveInvoke(InvokeInst *II, unsigned InvokeNo, + AllocaInst *InvokeNum, + SwitchInst *CatchSwitch) { + ConstantInt *InvokeNoC = ConstantInt::get(Type::getInt32Ty(II->getContext()), + InvokeNo); + + // If the unwind edge has phi nodes, split the edge. + if (isa(II->getUnwindDest()->begin())) { + SplitCriticalEdge(II, 1, this); + + // If there are any phi nodes left, they must have a single predecessor. + while (PHINode *PN = dyn_cast(II->getUnwindDest()->begin())) { + PN->replaceAllUsesWith(PN->getIncomingValue(0)); + PN->eraseFromParent(); + } + } - // If this function contains an unwind instruction, two blocks get added: one - // to actually perform the longjmp, and one to terminate the program if there - // is no handler. - BasicBlock *UnwindBlock = 0, *TermBlock = 0; - std::vector JBPtrs; + // Insert a store of the invoke num before the invoke and store zero into the + // location afterward. + new StoreInst(InvokeNoC, InvokeNum, true, II); // volatile + + BasicBlock::iterator NI = II->getNormalDest()->getFirstNonPHI(); + // nonvolatile. + new StoreInst(Constant::getNullValue(Type::getInt32Ty(II->getContext())), + InvokeNum, false, NI); + + // Add a switch case to our unwind block. + CatchSwitch->addCase(InvokeNoC, II->getUnwindDest()); + + // Insert a normal call instruction. + std::vector CallArgs(II->op_begin()+3, II->op_end()); + CallInst *NewCall = CallInst::Create(II->getCalledValue(), + CallArgs.begin(), CallArgs.end(), "", + II); + NewCall->takeName(II); + NewCall->setCallingConv(II->getCallingConv()); + NewCall->setAttributes(II->getAttributes()); + II->replaceAllUsesWith(NewCall); + + // Replace the invoke with an uncond branch. + BranchInst::Create(II->getNormalDest(), NewCall->getParent()); + II->eraseFromParent(); +} - for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) - if (InvokeInst *II = dyn_cast(BB->getTerminator())) { - if (JmpBuf == 0) - JmpBuf = new AllocaInst(JBLinkTy, 0, "jblink", F.begin()->begin()); - - // On the entry to the invoke, we must install our JmpBuf as the top of - // the stack. - LoadInst *OldEntry = new LoadInst(JBListHead, "oldehlist", II); - - // Store this old value as our 'next' field, and store our alloca as the - // current jblist. - std::vector Idx; - Idx.push_back(Constant::getNullValue(Type::IntTy)); - Idx.push_back(ConstantUInt::get(Type::UIntTy, 0)); - Value *NextFieldPtr = new GetElementPtrInst(JmpBuf, Idx, "NextField", II); - new StoreInst(OldEntry, NextFieldPtr, II); - new StoreInst(JmpBuf, JBListHead, II); - - // Call setjmp, passing in the address of the jmpbuffer. - Idx[1] = ConstantUInt::get(Type::UIntTy, 1); - Value *JmpBufPtr = new GetElementPtrInst(JmpBuf, Idx, "TheJmpBuf", II); - Value *SJRet = new CallInst(SetJmpFn, JmpBufPtr, "sjret", II); - - // Compare the return value to zero. - Value *IsNormal = BinaryOperator::create(Instruction::SetEQ, SJRet, - Constant::getNullValue(SJRet->getType()), - "notunwind", II); - // Create the receiver block if there is a critical edge to the normal - // destination. - SplitCriticalEdge(II, 0, this); - Instruction *InsertLoc = II->getNormalDest()->begin(); - - // Insert a normal call instruction on the normal execution path. - std::string Name = II->getName(); II->setName(""); - Value *NewCall = new CallInst(II->getCalledValue(), - std::vector(II->op_begin()+3, - II->op_end()), Name, - InsertLoc); - II->replaceAllUsesWith(NewCall); +/// MarkBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until +/// we reach blocks we've already seen. +static void MarkBlocksLiveIn(BasicBlock *BB, std::set &LiveBBs) { + if (!LiveBBs.insert(BB).second) return; // already been here. - // If we got this far, then no exception was thrown and we can pop our - // jmpbuf entry off. - new StoreInst(OldEntry, JBListHead, InsertLoc); + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + MarkBlocksLiveIn(*PI, LiveBBs); +} - // Now we change the invoke into a branch instruction. - new BranchInst(II->getNormalDest(), II->getUnwindDest(), IsNormal, II); +// First thing we need to do is scan the whole function for values that are +// live across unwind edges. Each value that is live across an unwind edge +// we spill into a stack location, guaranteeing that there is nothing live +// across the unwind edge. This process also splits all critical edges +// coming out of invoke's. +void LowerInvoke:: +splitLiveRangesLiveAcrossInvokes(std::vector &Invokes) { + // First step, split all critical edges from invoke instructions. + for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { + InvokeInst *II = Invokes[i]; + SplitCriticalEdge(II, 0, this); + SplitCriticalEdge(II, 1, this); + assert(!isa(II->getNormalDest()) && + !isa(II->getUnwindDest()) && + "critical edge splitting left single entry phi nodes?"); + } - // Remove the InvokeInst now. - BB->getInstList().erase(II); - ++NumLowered; Changed = true; + Function *F = Invokes.back()->getParent()->getParent(); + + // To avoid having to handle incoming arguments specially, we lower each arg + // to a copy instruction in the entry block. This ensures that the argument + // value itself cannot be live across the entry block. + BasicBlock::iterator AfterAllocaInsertPt = F->begin()->begin(); + while (isa(AfterAllocaInsertPt) && + isa(cast(AfterAllocaInsertPt)->getArraySize())) + ++AfterAllocaInsertPt; + for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); + AI != E; ++AI) { + // This is always a no-op cast because we're casting AI to AI->getType() so + // src and destination types are identical. BitCast is the only possibility. + CastInst *NC = new BitCastInst( + AI, AI->getType(), AI->getName()+".tmp", AfterAllocaInsertPt); + AI->replaceAllUsesWith(NC); + // Normally its is forbidden to replace a CastInst's operand because it + // could cause the opcode to reflect an illegal conversion. However, we're + // replacing it here with the same value it was constructed with to simply + // make NC its user. + NC->setOperand(0, AI); + } - } else if (UnwindInst *UI = dyn_cast(BB->getTerminator())) { - if (UnwindBlock == 0) { - // Create two new blocks, the unwind block and the terminate block. Add - // them at the end of the function because they are not hot. - UnwindBlock = new BasicBlock("unwind", &F); - TermBlock = new BasicBlock("unwinderror", &F); - - // Insert return instructions. These really should be "barrier"s, as - // they are unreachable. - new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 : - Constant::getNullValue(F.getReturnType()), UnwindBlock); - new ReturnInst(F.getReturnType() == Type::VoidTy ? 0 : - Constant::getNullValue(F.getReturnType()), TermBlock); + // Finally, scan the code looking for instructions with bad live ranges. + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) + for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ++II) { + // Ignore obvious cases we don't have to handle. In particular, most + // instructions either have no uses or only have a single use inside the + // current block. Ignore them quickly. + Instruction *Inst = II; + if (Inst->use_empty()) continue; + if (Inst->hasOneUse() && + cast(Inst->use_back())->getParent() == BB && + !isa(Inst->use_back())) continue; + + // If this is an alloca in the entry block, it's not a real register + // value. + if (AllocaInst *AI = dyn_cast(Inst)) + if (isa(AI->getArraySize()) && BB == F->begin()) + continue; + + // Avoid iterator invalidation by copying users to a temporary vector. + std::vector Users; + for (Value::use_iterator UI = Inst->use_begin(), E = Inst->use_end(); + UI != E; ++UI) { + Instruction *User = cast(*UI); + if (User->getParent() != BB || isa(User)) + Users.push_back(User); } - // Load the JBList, if it's null, then there was no catch! - LoadInst *Ptr = new LoadInst(JBListHead, "ehlist", UI); - Value *NotNull = BinaryOperator::create(Instruction::SetNE, Ptr, - Constant::getNullValue(Ptr->getType()), - "notnull", UI); - new BranchInst(UnwindBlock, TermBlock, NotNull, UI); + // Scan all of the uses and see if the live range is live across an unwind + // edge. If we find a use live across an invoke edge, create an alloca + // and spill the value. + std::set InvokesWithStoreInserted; + + // Find all of the blocks that this value is live in. + std::set LiveBBs; + LiveBBs.insert(Inst->getParent()); + while (!Users.empty()) { + Instruction *U = Users.back(); + Users.pop_back(); + + if (!isa(U)) { + MarkBlocksLiveIn(U->getParent(), LiveBBs); + } else { + // Uses for a PHI node occur in their predecessor block. + PHINode *PN = cast(U); + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + if (PN->getIncomingValue(i) == Inst) + MarkBlocksLiveIn(PN->getIncomingBlock(i), LiveBBs); + } + } - // Remember the loaded value so we can insert the PHI node as needed. - JBPtrs.push_back(Ptr); + // Now that we know all of the blocks that this thing is live in, see if + // it includes any of the unwind locations. + bool NeedsSpill = false; + for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { + BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest(); + if (UnwindBlock != BB && LiveBBs.count(UnwindBlock)) { + NeedsSpill = true; + } + } - // Remove the UnwindInst now. - BB->getInstList().erase(UI); - ++NumLowered; Changed = true; + // If we decided we need a spill, do it. + if (NeedsSpill) { + ++NumSpilled; + DemoteRegToStack(*Inst, true); + } } +} - // If an unwind instruction was inserted, we need to set up the Unwind and - // term blocks. - if (UnwindBlock) { - // In the unwind block, we know that the pointer coming in on the JBPtrs - // list are non-null. - Instruction *RI = UnwindBlock->getTerminator(); - - Value *RecPtr; - if (JBPtrs.size() == 1) - RecPtr = JBPtrs[0]; - else { - // If there is more than one unwind in this function, make a PHI node to - // merge in all of the loaded values. - PHINode *PN = new PHINode(JBPtrs[0]->getType(), "jbptrs", RI); - for (unsigned i = 0, e = JBPtrs.size(); i != e; ++i) - PN->addIncoming(JBPtrs[i], JBPtrs[i]->getParent()); - RecPtr = PN; +bool LowerInvoke::insertExpensiveEHSupport(Function &F) { + std::vector Returns; + std::vector Unwinds; + std::vector Invokes; + + for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) + if (ReturnInst *RI = dyn_cast(BB->getTerminator())) { + // Remember all return instructions in case we insert an invoke into this + // function. + Returns.push_back(RI); + } else if (InvokeInst *II = dyn_cast(BB->getTerminator())) { + Invokes.push_back(II); + } else if (UnwindInst *UI = dyn_cast(BB->getTerminator())) { + Unwinds.push_back(UI); } - // Now that we have a pointer to the whole record, remove the entry from the - // JBList. + if (Unwinds.empty() && Invokes.empty()) return false; + + NumInvokes += Invokes.size(); + NumUnwinds += Unwinds.size(); + + // TODO: This is not an optimal way to do this. In particular, this always + // inserts setjmp calls into the entries of functions with invoke instructions + // even though there are possibly paths through the function that do not + // execute any invokes. In particular, for functions with early exits, e.g. + // the 'addMove' method in hexxagon, it would be nice to not have to do the + // setjmp stuff on the early exit path. This requires a bit of dataflow, but + // would not be too hard to do. + + // If we have an invoke instruction, insert a setjmp that dominates all + // invokes. After the setjmp, use a cond branch that goes to the original + // code path on zero, and to a designated 'catch' block of nonzero. + Value *OldJmpBufPtr = 0; + if (!Invokes.empty()) { + // First thing we need to do is scan the whole function for values that are + // live across unwind edges. Each value that is live across an unwind edge + // we spill into a stack location, guaranteeing that there is nothing live + // across the unwind edge. This process also splits all critical edges + // coming out of invoke's. + splitLiveRangesLiveAcrossInvokes(Invokes); + + BasicBlock *EntryBB = F.begin(); + + // Create an alloca for the incoming jump buffer ptr and the new jump buffer + // that needs to be restored on all exits from the function. This is an + // alloca because the value needs to be live across invokes. + unsigned Align = TLI ? TLI->getJumpBufAlignment() : 0; + AllocaInst *JmpBuf = + new AllocaInst(JBLinkTy, 0, Align, + "jblink", F.begin()->begin()); + std::vector Idx; - Idx.push_back(Constant::getNullValue(Type::IntTy)); - Idx.push_back(ConstantUInt::get(Type::UIntTy, 0)); - Value *NextFieldPtr = new GetElementPtrInst(RecPtr, Idx, "NextField", RI); - Value *NextRec = new LoadInst(NextFieldPtr, "NextRecord", RI); - new StoreInst(NextRec, JBListHead, RI); - - // Now that we popped the top of the JBList, get a pointer to the jmpbuf and - // longjmp. - Idx[1] = ConstantUInt::get(Type::UIntTy, 1); - Idx[0] = new GetElementPtrInst(RecPtr, Idx, "JmpBuf", RI); - Idx[1] = ConstantInt::get(Type::IntTy, 1); - new CallInst(LongJmpFn, Idx, "", RI); - - // Now we set up the terminate block. - RI = TermBlock->getTerminator(); - - // Insert a new call to write(2, AbortMessage, AbortMessageLength); - writeAbortMessage(RI); - - // Insert a call to abort() - (new CallInst(AbortFn, std::vector(), "", RI))->setTailCall(); + Idx.push_back(Constant::getNullValue(Type::getInt32Ty(F.getContext()))); + Idx.push_back(ConstantInt::get(Type::getInt32Ty(F.getContext()), 1)); + OldJmpBufPtr = GetElementPtrInst::Create(JmpBuf, Idx.begin(), Idx.end(), + "OldBuf", + EntryBB->getTerminator()); + + // Copy the JBListHead to the alloca. + Value *OldBuf = new LoadInst(JBListHead, "oldjmpbufptr", true, + EntryBB->getTerminator()); + new StoreInst(OldBuf, OldJmpBufPtr, true, EntryBB->getTerminator()); + + // Add the new jumpbuf to the list. + new StoreInst(JmpBuf, JBListHead, true, EntryBB->getTerminator()); + + // Create the catch block. The catch block is basically a big switch + // statement that goes to all of the invoke catch blocks. + BasicBlock *CatchBB = + BasicBlock::Create(F.getContext(), "setjmp.catch", &F); + + // Create an alloca which keeps track of which invoke is currently + // executing. For normal calls it contains zero. + AllocaInst *InvokeNum = new AllocaInst(Type::getInt32Ty(F.getContext()), 0, + "invokenum",EntryBB->begin()); + new StoreInst(ConstantInt::get(Type::getInt32Ty(F.getContext()), 0), + InvokeNum, true, EntryBB->getTerminator()); + + // Insert a load in the Catch block, and a switch on its value. By default, + // we go to a block that just does an unwind (which is the correct action + // for a standard call). + BasicBlock *UnwindBB = BasicBlock::Create(F.getContext(), "unwindbb", &F); + Unwinds.push_back(new UnwindInst(F.getContext(), UnwindBB)); + + Value *CatchLoad = new LoadInst(InvokeNum, "invoke.num", true, CatchBB); + SwitchInst *CatchSwitch = + SwitchInst::Create(CatchLoad, UnwindBB, Invokes.size(), CatchBB); + + // Now that things are set up, insert the setjmp call itself. + + // Split the entry block to insert the conditional branch for the setjmp. + BasicBlock *ContBlock = EntryBB->splitBasicBlock(EntryBB->getTerminator(), + "setjmp.cont"); + + Idx[1] = ConstantInt::get(Type::getInt32Ty(F.getContext()), 0); + Value *JmpBufPtr = GetElementPtrInst::Create(JmpBuf, Idx.begin(), Idx.end(), + "TheJmpBuf", + EntryBB->getTerminator()); + JmpBufPtr = new BitCastInst(JmpBufPtr, + PointerType::getUnqual(Type::getInt8Ty(F.getContext())), + "tmp", EntryBB->getTerminator()); + Value *SJRet = CallInst::Create(SetJmpFn, JmpBufPtr, "sjret", + EntryBB->getTerminator()); + + // Compare the return value to zero. + Value *IsNormal = new ICmpInst(EntryBB->getTerminator(), + ICmpInst::ICMP_EQ, SJRet, + Constant::getNullValue(SJRet->getType()), + "notunwind"); + // Nuke the uncond branch. + EntryBB->getTerminator()->eraseFromParent(); + + // Put in a new condbranch in its place. + BranchInst::Create(ContBlock, CatchBB, IsNormal, EntryBB); + + // At this point, we are all set up, rewrite each invoke instruction. + for (unsigned i = 0, e = Invokes.size(); i != e; ++i) + rewriteExpensiveInvoke(Invokes[i], i+1, InvokeNum, CatchSwitch); } - return Changed; + // We know that there is at least one unwind. + + // Create three new blocks, the block to load the jmpbuf ptr and compare + // against null, the block to do the longjmp, and the error block for if it + // is null. Add them at the end of the function because they are not hot. + BasicBlock *UnwindHandler = BasicBlock::Create(F.getContext(), + "dounwind", &F); + BasicBlock *UnwindBlock = BasicBlock::Create(F.getContext(), "unwind", &F); + BasicBlock *TermBlock = BasicBlock::Create(F.getContext(), "unwinderror", &F); + + // If this function contains an invoke, restore the old jumpbuf ptr. + Value *BufPtr; + if (OldJmpBufPtr) { + // Before the return, insert a copy from the saved value to the new value. + BufPtr = new LoadInst(OldJmpBufPtr, "oldjmpbufptr", UnwindHandler); + new StoreInst(BufPtr, JBListHead, UnwindHandler); + } else { + BufPtr = new LoadInst(JBListHead, "ehlist", UnwindHandler); + } + + // Load the JBList, if it's null, then there was no catch! + Value *NotNull = new ICmpInst(*UnwindHandler, ICmpInst::ICMP_NE, BufPtr, + Constant::getNullValue(BufPtr->getType()), + "notnull"); + BranchInst::Create(UnwindBlock, TermBlock, NotNull, UnwindHandler); + + // Create the block to do the longjmp. + // Get a pointer to the jmpbuf and longjmp. + std::vector Idx; + Idx.push_back(Constant::getNullValue(Type::getInt32Ty(F.getContext()))); + Idx.push_back(ConstantInt::get(Type::getInt32Ty(F.getContext()), 0)); + Idx[0] = GetElementPtrInst::Create(BufPtr, Idx.begin(), Idx.end(), "JmpBuf", + UnwindBlock); + Idx[0] = new BitCastInst(Idx[0], + PointerType::getUnqual(Type::getInt8Ty(F.getContext())), + "tmp", UnwindBlock); + Idx[1] = ConstantInt::get(Type::getInt32Ty(F.getContext()), 1); + CallInst::Create(LongJmpFn, Idx.begin(), Idx.end(), "", UnwindBlock); + new UnreachableInst(F.getContext(), UnwindBlock); + + // Set up the term block ("throw without a catch"). + new UnreachableInst(F.getContext(), TermBlock); + + // Insert a new call to write(2, AbortMessage, AbortMessageLength); + writeAbortMessage(TermBlock->getTerminator()); + + // Insert a call to abort() + CallInst::Create(AbortFn, "", + TermBlock->getTerminator())->setTailCall(); + + + // Replace all unwinds with a branch to the unwind handler. + for (unsigned i = 0, e = Unwinds.size(); i != e; ++i) { + BranchInst::Create(UnwindHandler, Unwinds[i]); + Unwinds[i]->eraseFromParent(); + } + + // Finally, for any returns from this function, if this function contains an + // invoke, restore the old jmpbuf pointer to its input value. + if (OldJmpBufPtr) { + for (unsigned i = 0, e = Returns.size(); i != e; ++i) { + ReturnInst *R = Returns[i]; + + // Before the return, insert a copy from the saved value to the new value. + Value *OldBuf = new LoadInst(OldJmpBufPtr, "oldjmpbufptr", true, R); + new StoreInst(OldBuf, JBListHead, true, R); + } + } + + return true; } bool LowerInvoke::runOnFunction(Function &F) {