-//===- SjLjEHPass.cpp - Eliminate Invoke & Unwind instructions -----------===//
+//===- SjLjEHPrepare.cpp - Eliminate Invoke & Unwind instructions ---------===//
//
// The LLVM Compiler Infrastructure
//
#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"
#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"
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;
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";
}
private:
bool setupEntryBlockAndCallSites(Function &F);
void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal,
- Value *SelVal, IRBuilder<> &Builder);
+ Value *SelVal);
Value *setupFunctionContext(Function &F, ArrayRef<LandingPadInst*> LPads);
void lowerIncomingArguments(Function &F);
void lowerAcrossUnwindEdges(Function &F, ArrayRef<InvokeInst*> 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());
/// 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<BasicBlock*, 64> &LiveBBs) {
- if (!LiveBBs.insert(BB)) return; // already been here.
+static void markBlocksLiveIn(BasicBlock *BB, Instruction *Inst,
+ SmallPtrSet<BasicBlock*, 64> &LiveBBs,
+ SmallPtrSet<BasicBlock*, 4> &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<Value*, 8> UseWorkList(LPI->use_begin(), LPI->use_end());
while (!UseWorkList.empty()) {
Value *Val = UseWorkList.pop_back_val();
// values and replace the LPI with that aggregate.
Type *LPadType = LPI->getType();
Value *LPadVal = UndefValue::get(LPadType);
+ IRBuilder<>
+ Builder(llvm::next(BasicBlock::iterator(cast<Instruction>(SelVal))));
LPadVal = Builder.CreateInsertValue(LPadVal, ExnVal, 0, "lpad.val");
LPadVal = Builder.CreateInsertValue(LPadVal, SelVal, 1, "lpad.val");
/// 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<LandingPadInst*> LPads) {
BasicBlock *EntryBB = F.begin();
// 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 =
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;
/// 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<AllocaInst>(AfterAllocaInsPt) &&
isa<ConstantInt>(cast<AllocaInst>(AfterAllocaInsPt)->getArraySize()))
/// lowerAcrossUnwindEdges - Find all variables which are alive across an unwind
/// edge and spill them.
-void SjLjEHPass::lowerAcrossUnwindEdges(Function &F,
- ArrayRef<InvokeInst*> Invokes) {
+void SjLjEHPrepare::lowerAcrossUnwindEdges(Function &F,
+ ArrayRef<InvokeInst*> Invokes) {
+ SmallVector<std::pair<Instruction*, Instruction*>, 32> ReloadUsers;
+ DenseMap<std::pair<Instruction*, Instruction*>, 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) {
}
// Find all of the blocks that this value is live in.
- SmallPtrSet<BasicBlock*, 64> LiveBBs;
- LiveBBs.insert(Inst->getParent());
+ std::map<Instruction*, SmallPtrSet<BasicBlock*, 4> > InvokesCrossed;
+ std::map<Instruction*, SmallPtrSet<BasicBlock*, 64> > LiveBBs;
+ bool FoundDef = false;
while (!Users.empty()) {
- Instruction *U = Users.back();
- Users.pop_back();
+ Instruction *U = Users.pop_back_val();
- if (!isa<PHINode>(U)) {
- MarkBlocksLiveIn(U->getParent(), LiveBBs);
- } else {
+ if (PHINode *PN = dyn_cast<PHINode>(U)) {
// Uses for a PHI node occur in their predecessor block.
- PHINode *PN = cast<PHINode>(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<Instruction*, SmallPtrSet<BasicBlock*, 64> >::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<Instruction*, SmallPtrSet<BasicBlock*, 4> >::iterator
+ MI = InvokesCrossed.begin(), ME = InvokesCrossed.end();
+ MI != ME; ++MI) {
+ Instruction *User = MI->first;
+ SmallPtrSet<BasicBlock*, 4> &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<BasicBlock*, 4>::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<std::pair<Instruction*, Instruction*> >::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<PHINode>(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<BasicBlock*, Value*> 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();
/// 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<ReturnInst*, 16> Returns;
SmallVector<InvokeInst*, 16> Invokes;
SmallSetVector<LandingPadInst*, 16> LPads;
// 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);
for (BasicBlock::iterator I = BB->begin(), end = BB->end(); I != end; ++I)
if (CallInst *CI = dyn_cast<CallInst>(I)) {
if (!CI->doesNotThrow())
- insertCallSiteStore(CI, -1, CallSite);
+ insertCallSiteStore(CI, -1);
} else if (ResumeInst *RI = dyn_cast<ResumeInst>(I)) {
- insertCallSiteStore(RI, -1, CallSite);
+ insertCallSiteStore(RI, -1);
}
// Register the function context and make sure it's known to not throw
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;
}