X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSjLjEHPrepare.cpp;h=5ac0c09ded9990c9dac8987eadf1c7d4df839371;hb=bb54d21495ba5ce60931bc872e3e3df67386cb97;hp=ac99cca27b07e36bc02f7ab24da2573f56880d96;hpb=4762f7525162ddcd3a527677ed8a2d53856f21d9;p=oota-llvm.git diff --git a/lib/CodeGen/SjLjEHPrepare.cpp b/lib/CodeGen/SjLjEHPrepare.cpp index ac99cca27b0..5ac0c09ded9 100644 --- a/lib/CodeGen/SjLjEHPrepare.cpp +++ b/lib/CodeGen/SjLjEHPrepare.cpp @@ -1,4 +1,4 @@ -//===- SjLjEHPass.cpp - Eliminate Invoke & Unwind instructions -----------===// +//===- SjLjEHPrepare.cpp - Eliminate Invoke & Unwind instructions ---------===// // // The LLVM Compiler Infrastructure // @@ -21,6 +21,7 @@ #include "llvm/LLVMContext.h" #include "llvm/Module.h" #include "llvm/Pass.h" +#include "llvm/Analysis/Verifier.h" #include "llvm/CodeGen/Passes.h" #include "llvm/Target/TargetData.h" #include "llvm/Target/TargetLowering.h" @@ -29,6 +30,7 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/IRBuilder.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" @@ -41,8 +43,9 @@ STATISTIC(NumInvokes, "Number of invokes replaced"); STATISTIC(NumSpilled, "Number of registers live across unwind edges"); namespace { - class SjLjEHPass : public FunctionPass { + class SjLjEHPrepare : public FunctionPass { const TargetLowering *TLI; + Type *FunctionContextTy; Constant *RegisterFn; Constant *UnregisterFn; @@ -54,15 +57,17 @@ namespace { Value *PersonalityFn; Constant *CallSiteFn; Constant *FuncCtxFn; - Value *CallSite; + AllocaInst *FuncCtx; public: static char ID; // Pass identification, replacement for typeid - explicit SjLjEHPass(const TargetLowering *tli = NULL) - : FunctionPass(ID), TLI(tli) { } + explicit SjLjEHPrepare(const TargetLowering *tli = NULL) + : FunctionPass(ID), TLI(tli) {} bool doInitialization(Module &M); bool runOnFunction(Function &F); - virtual void getAnalysisUsage(AnalysisUsage &AU) const {} + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + FunctionPass::getAnalysisUsage(AU); + } const char *getPassName() const { return "SJLJ Exception Handling preparation"; } @@ -70,23 +75,23 @@ namespace { private: bool setupEntryBlockAndCallSites(Function &F); void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, - Value *SelVal, IRBuilder<> &Builder); + Value *SelVal); Value *setupFunctionContext(Function &F, ArrayRef LPads); void lowerIncomingArguments(Function &F); void lowerAcrossUnwindEdges(Function &F, ArrayRef Invokes); - void insertCallSiteStore(Instruction *I, int Number, Value *CallSite); + void insertCallSiteStore(Instruction *I, int Number); }; } // end anonymous namespace -char SjLjEHPass::ID = 0; +char SjLjEHPrepare::ID = 0; -// Public Interface To the SjLjEHPass pass. -FunctionPass *llvm::createSjLjEHPass(const TargetLowering *TLI) { - return new SjLjEHPass(TLI); +// Public Interface To the SjLjEHPrepare pass. +FunctionPass *llvm::createSjLjEHPreparePass(const TargetLowering *TLI) { + return new SjLjEHPrepare(TLI); } // doInitialization - Set up decalarations and types needed to process // exceptions. -bool SjLjEHPass::doInitialization(Module &M) { +bool SjLjEHPrepare::doInitialization(Module &M) { // Build the function context structure. // builtin_setjmp uses a five word jbuf Type *VoidPtrTy = Type::getInt8PtrTy(M.getContext()); @@ -122,28 +127,48 @@ bool SjLjEHPass::doInitialization(Module &M) { /// insertCallSiteStore - Insert a store of the call-site value to the /// function context -void SjLjEHPass::insertCallSiteStore(Instruction *I, int Number, - Value *CallSite) { +void SjLjEHPrepare::insertCallSiteStore(Instruction *I, int Number) { + IRBuilder<> Builder(I); + + // Get a reference to the call_site field. + Type *Int32Ty = Type::getInt32Ty(I->getContext()); + Value *Zero = ConstantInt::get(Int32Ty, 0); + Value *One = ConstantInt::get(Int32Ty, 1); + Value *Idxs[2] = { Zero, One }; + Value *CallSite = Builder.CreateGEP(FuncCtx, Idxs, "call_site"); + + // Insert a store of the call-site number ConstantInt *CallSiteNoC = ConstantInt::get(Type::getInt32Ty(I->getContext()), Number); - // Insert a store of the call-site number - new StoreInst(CallSiteNoC, CallSite, true, I); // volatile + Builder.CreateStore(CallSiteNoC, CallSite, true/*volatile*/); } -/// MarkBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until +/// markBlocksLiveIn - Insert BB and all of its predescessors into LiveBBs until /// we reach blocks we've already seen. -static void MarkBlocksLiveIn(BasicBlock *BB, - SmallPtrSet &LiveBBs) { - if (!LiveBBs.insert(BB)) return; // already been here. +static void markBlocksLiveIn(BasicBlock *BB, Instruction *Inst, + SmallPtrSet &LiveBBs, + SmallPtrSet &InvokesCrossed, + bool &FoundDef) { + if (!LiveBBs.insert(BB)) return; // Already been here. + if (BB == Inst->getParent()) { + FoundDef = true; + return; + } - for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) - MarkBlocksLiveIn(*PI, LiveBBs); + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + BasicBlock *Pred = *PI; + if (BB->isLandingPad() && BB != Inst->getParent()) { + InvokesCrossed.insert(Pred); + continue; + } + markBlocksLiveIn(Pred, Inst, LiveBBs, InvokesCrossed, FoundDef); + } } /// substituteLPadValues - Substitute the values returned by the landingpad /// instruction with those returned by the personality function. -void SjLjEHPass::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, - Value *SelVal, IRBuilder<> &Builder) { +void SjLjEHPrepare::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, + Value *SelVal) { SmallVector UseWorkList(LPI->use_begin(), LPI->use_end()); while (!UseWorkList.empty()) { Value *Val = UseWorkList.pop_back_val(); @@ -164,6 +189,8 @@ void SjLjEHPass::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, // values and replace the LPI with that aggregate. Type *LPadType = LPI->getType(); Value *LPadVal = UndefValue::get(LPadType); + IRBuilder<> + Builder(llvm::next(BasicBlock::iterator(cast(SelVal)))); LPadVal = Builder.CreateInsertValue(LPadVal, ExnVal, 0, "lpad.val"); LPadVal = Builder.CreateInsertValue(LPadVal, SelVal, 1, "lpad.val"); @@ -172,7 +199,7 @@ void SjLjEHPass::substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, /// setupFunctionContext - Allocate the function context on the stack and fill /// it with all of the data that we know at this point. -Value *SjLjEHPass:: +Value *SjLjEHPrepare:: setupFunctionContext(Function &F, ArrayRef LPads) { BasicBlock *EntryBB = F.begin(); @@ -181,51 +208,42 @@ setupFunctionContext(Function &F, ArrayRef LPads) { // because the value needs to be added to the global context list. unsigned Align = TLI->getTargetData()->getPrefTypeAlignment(FunctionContextTy); - AllocaInst *FuncCtx = + FuncCtx = new AllocaInst(FunctionContextTy, 0, Align, "fn_context", EntryBB->begin()); // Fill in the function context structure. - Value *Idxs[2]; Type *Int32Ty = Type::getInt32Ty(F.getContext()); Value *Zero = ConstantInt::get(Int32Ty, 0); Value *One = ConstantInt::get(Int32Ty, 1); + Value *Two = ConstantInt::get(Int32Ty, 2); + Value *Three = ConstantInt::get(Int32Ty, 3); + Value *Four = ConstantInt::get(Int32Ty, 4); - // Keep around a reference to the call_site field. - Idxs[0] = Zero; - Idxs[1] = One; - CallSite = GetElementPtrInst::Create(FuncCtx, Idxs, "call_site", - EntryBB->getTerminator()); - - // Reference the __data field. - Idxs[1] = ConstantInt::get(Int32Ty, 2); - Value *FCData = GetElementPtrInst::Create(FuncCtx, Idxs, "__data", - EntryBB->getTerminator()); - - // The exception value comes back in context->__data[0]. - Idxs[1] = Zero; - Value *ExceptionAddr = GetElementPtrInst::Create(FCData, Idxs, - "exception_gep", - EntryBB->getTerminator()); - - // The exception selector comes back in context->__data[1]. - Idxs[1] = One; - Value *SelectorAddr = GetElementPtrInst::Create(FCData, Idxs, - "exn_selector_gep", - EntryBB->getTerminator()); + Value *Idxs[2] = { Zero, 0 }; for (unsigned I = 0, E = LPads.size(); I != E; ++I) { LandingPadInst *LPI = LPads[I]; IRBuilder<> Builder(LPI->getParent()->getFirstInsertionPt()); + // Reference the __data field. + Idxs[1] = Two; + Value *FCData = Builder.CreateGEP(FuncCtx, Idxs, "__data"); + + // The exception values come back in context->__data[0]. + Idxs[1] = Zero; + Value *ExceptionAddr = Builder.CreateGEP(FCData, Idxs, "exception_gep"); Value *ExnVal = Builder.CreateLoad(ExceptionAddr, true, "exn_val"); ExnVal = Builder.CreateIntToPtr(ExnVal, Type::getInt8PtrTy(F.getContext())); + + Idxs[1] = One; + Value *SelectorAddr = Builder.CreateGEP(FCData, Idxs, "exn_selector_gep"); Value *SelVal = Builder.CreateLoad(SelectorAddr, true, "exn_selector_val"); - substituteLPadValues(LPI, ExnVal, SelVal, Builder); + substituteLPadValues(LPI, ExnVal, SelVal); } // Personality function - Idxs[1] = ConstantInt::get(Int32Ty, 3); + Idxs[1] = Three; if (!PersonalityFn) PersonalityFn = LPads[0]->getPersonalityFn(); Value *PersonalityFieldPtr = @@ -235,11 +253,11 @@ setupFunctionContext(Function &F, ArrayRef LPads) { EntryBB->getTerminator()); // LSDA address - Idxs[1] = ConstantInt::get(Int32Ty, 4); - Value *LSDAFieldPtr = GetElementPtrInst::Create(FuncCtx, Idxs, "lsda_gep", - EntryBB->getTerminator()); Value *LSDA = CallInst::Create(LSDAAddrFn, "lsda_addr", EntryBB->getTerminator()); + Idxs[1] = Four; + Value *LSDAFieldPtr = GetElementPtrInst::Create(FuncCtx, Idxs, "lsda_gep", + EntryBB->getTerminator()); new StoreInst(LSDA, LSDAFieldPtr, true, EntryBB->getTerminator()); return FuncCtx; @@ -249,7 +267,7 @@ setupFunctionContext(Function &F, ArrayRef LPads) { /// specially, we lower each arg to a copy instruction in the entry block. This /// ensures that the argument value itself cannot be live out of the entry /// block. -void SjLjEHPass::lowerIncomingArguments(Function &F) { +void SjLjEHPrepare::lowerIncomingArguments(Function &F) { BasicBlock::iterator AfterAllocaInsPt = F.begin()->begin(); while (isa(AfterAllocaInsPt) && isa(cast(AfterAllocaInsPt)->getArraySize())) @@ -293,8 +311,11 @@ void SjLjEHPass::lowerIncomingArguments(Function &F) { /// lowerAcrossUnwindEdges - Find all variables which are alive across an unwind /// edge and spill them. -void SjLjEHPass::lowerAcrossUnwindEdges(Function &F, - ArrayRef Invokes) { +void SjLjEHPrepare::lowerAcrossUnwindEdges(Function &F, + ArrayRef Invokes) { + SmallVector, 32> ReloadUsers; + DenseMap, AllocaInst*> AllocaMap; + // Finally, scan the code looking for instructions with bad live ranges. for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) { @@ -325,45 +346,118 @@ void SjLjEHPass::lowerAcrossUnwindEdges(Function &F, } // Find all of the blocks that this value is live in. - SmallPtrSet LiveBBs; - LiveBBs.insert(Inst->getParent()); + std::map > InvokesCrossed; + std::map > LiveBBs; + bool FoundDef = false; while (!Users.empty()) { - Instruction *U = Users.back(); - Users.pop_back(); + Instruction *U = Users.pop_back_val(); - if (!isa(U)) { - MarkBlocksLiveIn(U->getParent(), LiveBBs); - } else { + if (PHINode *PN = dyn_cast(U)) { // 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); + markBlocksLiveIn(PN->getIncomingBlock(i), Inst, LiveBBs[U], + InvokesCrossed[U], FoundDef); + } else { + markBlocksLiveIn(U->getParent(), Inst, LiveBBs[U], + InvokesCrossed[U], FoundDef); } } - // 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; - break; + // If we hit the definition, resort to the dump-this-value-everywhere + // method. + if (FoundDef) { + // 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) continue; + + for (std::map >::iterator + MI = LiveBBs.begin(), ME = LiveBBs.end(); MI != ME; ++MI) { + if (MI->second.count(UnwindBlock)) { + DEBUG({ + dbgs() << "SJLJ Spill: " << *Inst << " around " + << UnwindBlock->getName() << "\n"; + }); + NeedsSpill = true; + break; + } + } + + // If we decided we need a spill, do it. + if (NeedsSpill) { + DemoteRegToStack(*Inst, true); + ++NumSpilled; + } } + + // We don't need this map anymore. + InvokesCrossed.clear(); } - // If we decided we need a spill, do it. - // FIXME: Spilling this way is overkill, as it forces all uses of - // the value to be reloaded from the stack slot, even those that aren't - // in the unwind blocks. We should be more selective. - if (NeedsSpill) { - DemoteRegToStack(*Inst, true); - ++NumSpilled; + // Go through the invokes the value crosses and insert a spill right + // before the invoke. + for (std::map >::iterator + MI = InvokesCrossed.begin(), ME = InvokesCrossed.end(); + MI != ME; ++MI) { + Instruction *User = MI->first; + SmallPtrSet &Crossings = MI->second; + if (Crossings.empty()) continue; + + ReloadUsers.push_back(std::make_pair(Inst, User)); + + AllocaInst *&Slot = AllocaMap[std::make_pair(Inst, User)]; + if (!Slot) + Slot = new AllocaInst(Inst->getType(), 0, + Inst->getName() + ".reg2mem", + F.getEntryBlock().begin()); + + for (SmallPtrSet::iterator + CI = Crossings.begin(), CE = Crossings.end(); CI != CE; ++CI) { + new StoreInst(Inst, Slot, (*CI)->getTerminator()); + ++NumSpilled; + } } } } + // Now go through the instructions which were spilled and replace their uses + // after a crossed invoke with a reload instruction. + for (SmallVectorImpl >::iterator + I = ReloadUsers.begin(), E = ReloadUsers.end(); I != E; ++I) { + Instruction *User = I->second; + AllocaInst *Slot = AllocaMap[*I]; + assert(Slot && "A spill slot hasn't been allocated yet!"); + + if (PHINode *PN = dyn_cast(User)) { + // If this is a PHI node, we can't insert a load of the value before the + // use. Instead insert the load in the predecessor block corresponding to + // the incoming value. + // + // Note that if there are multiple edges from a basic block to this PHI + // node that we cannot have multiple loads. The problem is that the + // resulting PHI node will have multiple values (from each load) coming in + // from the same block, which is illegal SSA form. For this reason, we + // keep track of and reuse loads we insert. + DenseMap Loads; + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) + if (PN->getIncomingValue(i) == I->first) { + Value *&V = Loads[PN->getIncomingBlock(i)]; + if (V == 0) + // Insert the load into the predecessor block + V = new LoadInst(Slot, I->first->getName() + ".reload", true, + PN->getIncomingBlock(i)->getTerminator()); + + PN->setIncomingValue(i, V); + } + } else { + LoadInst *Reload = new LoadInst(Slot, Slot->getName() + ".reload", User); + User->replaceUsesOfWith(I->first, Reload); + } + } + // Go through the landing pads and remove any PHIs there. for (unsigned i = 0, e = Invokes.size(); i != e; ++i) { BasicBlock *UnwindBlock = Invokes[i]->getUnwindDest(); @@ -389,7 +483,7 @@ void SjLjEHPass::lowerAcrossUnwindEdges(Function &F, /// setupEntryBlockAndCallSites - Setup the entry block by creating and filling /// the function context and marking the call sites with the appropriate /// values. These values are used by the DWARF EH emitter. -bool SjLjEHPass::setupEntryBlockAndCallSites(Function &F) { +bool SjLjEHPrepare::setupEntryBlockAndCallSites(Function &F) { SmallVector Returns; SmallVector Invokes; SmallSetVector LPads; @@ -459,7 +553,7 @@ bool SjLjEHPass::setupEntryBlockAndCallSites(Function &F) { // At this point, we are all set up, update the invoke instructions to mark // their call_site values. for (unsigned I = 0, E = Invokes.size(); I != E; ++I) { - insertCallSiteStore(Invokes[I], I + 1, CallSite); + insertCallSiteStore(Invokes[I], I + 1); ConstantInt *CallSiteNum = ConstantInt::get(Type::getInt32Ty(F.getContext()), I + 1); @@ -478,9 +572,9 @@ bool SjLjEHPass::setupEntryBlockAndCallSites(Function &F) { for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I) if (CallInst *CI = dyn_cast(I)) { if (!CI->doesNotThrow()) - insertCallSiteStore(CI, -1, CallSite); + insertCallSiteStore(CI, -1); } else if (ResumeInst *RI = dyn_cast(I)) { - insertCallSiteStore(RI, -1, CallSite); + insertCallSiteStore(RI, -1); } // Register the function context and make sure it's known to not throw @@ -515,7 +609,11 @@ bool SjLjEHPass::setupEntryBlockAndCallSites(Function &F) { return true; } -bool SjLjEHPass::runOnFunction(Function &F) { +bool SjLjEHPrepare::runOnFunction(Function &F) { bool Res = setupEntryBlockAndCallSites(F); + DEBUG({ + if (verifyFunction(F)) + report_fatal_error("verifyFunction failed!"); + }); return Res; }