//===- LowerSetJmp.cpp - Code pertaining to lowering set/long jumps -------===//
//
+// 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 implements the lowering of setjmp and longjmp to use the
// LLVM invoke and unwind instructions as necessary.
//
// pass invokable via the "opt" command at will.
//===----------------------------------------------------------------------===//
+#include "llvm/Transforms/IPO.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
-#include "llvm/Support/InstIterator.h"
+#include "llvm/Support/CFG.h"
#include "llvm/Support/InstVisitor.h"
-#include "Support/Statistic.h"
-#include "Support/StringExtras.h"
-#include "Support/VectorExtras.h"
-
-#include <set>
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/VectorExtras.h"
+using namespace llvm;
namespace {
Statistic<> LongJmpsTransformed("lowersetjmp",
"Number of longjmps transformed");
Statistic<> SetJmpsTransformed("lowersetjmp",
"Number of setjmps transformed");
+ Statistic<> CallsTransformed("lowersetjmp",
+ "Number of calls invokified");
+ Statistic<> InvokesTransformed("lowersetjmp",
+ "Number of invokes modified");
//===--------------------------------------------------------------------===//
- // LowerSetJmp pass implementation. This is subclassed from the "Pass"
- // class because it works on a module as a whole, not a function at a
- // time.
-
- class LowerSetJmp : public Pass,
+ // LowerSetJmp pass implementation.
+ class LowerSetJmp : public ModulePass,
public InstVisitor<LowerSetJmp> {
// LLVM library functions...
Function* InitSJMap; // __llvm_sjljeh_init_setjmpmap
typedef std::pair<SwitchInst*, CallInst*> SwitchValuePair;
+ // Keep track of those basic blocks reachable via a depth-first search of
+ // the CFG from a setjmp call. We only need to transform those "call" and
+ // "invoke" instructions that are reachable from the setjmp call site.
+ std::set<BasicBlock*> DFSBlocks;
+
// The setjmp map is going to hold information about which setjmps
// were called (each setjmp gets its own number) and with which
// buffer it was called.
void visitReturnInst(ReturnInst& RI);
void visitUnwindInst(UnwindInst& UI);
- bool run(Module& M);
+ bool runOnModule(Module& M);
bool doInitialization(Module& M);
};
// run - Run the transformation on the program. We grab the function
// prototypes for longjmp and setjmp. If they are used in the program,
// then we can go directly to the places they're at and transform them.
-bool LowerSetJmp::run(Module& M)
-{
+bool LowerSetJmp::runOnModule(Module& M) {
bool Changed = false;
// These are what the functions are called.
// setjmp/longjmp functions.
doInitialization(M);
- if (SetJmp)
+ if (SetJmp) {
+ for (Value::use_iterator B = SetJmp->use_begin(), E = SetJmp->use_end();
+ B != E; ++B) {
+ BasicBlock* BB = cast<Instruction>(*B)->getParent();
+ for (df_ext_iterator<BasicBlock*> I = df_ext_begin(BB, DFSBlocks),
+ E = df_ext_end(BB, DFSBlocks); I != E; ++I)
+ /* empty */;
+ }
+
while (!SetJmp->use_empty()) {
assert(isa<CallInst>(SetJmp->use_back()) &&
"User of setjmp intrinsic not a call?");
TransformSetJmpCall(cast<CallInst>(SetJmp->use_back()));
Changed = true;
}
+ }
if (LongJmp)
while (!LongJmp->use_empty()) {
}
}
+ DFSBlocks.clear();
SJMap.clear();
RethrowBBMap.clear();
PrelimBBMap.clear();
// void __llvm_sjljeh_init_setjmpmap(void**)
InitSJMap = M.getOrInsertFunction("__llvm_sjljeh_init_setjmpmap",
- Type::VoidTy, SBPPTy, 0);
+ Type::VoidTy, SBPPTy, NULL);
// void __llvm_sjljeh_destroy_setjmpmap(void**)
DestroySJMap = M.getOrInsertFunction("__llvm_sjljeh_destroy_setjmpmap",
- Type::VoidTy, SBPPTy, 0);
+ Type::VoidTy, SBPPTy, NULL);
// void __llvm_sjljeh_add_setjmp_to_map(void**, void*, unsigned)
AddSJToMap = M.getOrInsertFunction("__llvm_sjljeh_add_setjmp_to_map",
Type::VoidTy, SBPPTy, SBPTy,
- Type::UIntTy, 0);
+ Type::UIntTy, NULL);
// void __llvm_sjljeh_throw_longjmp(int*, int)
ThrowLongJmp = M.getOrInsertFunction("__llvm_sjljeh_throw_longjmp",
- Type::VoidTy, SBPTy, Type::IntTy, 0);
+ Type::VoidTy, SBPTy, Type::IntTy, NULL);
// unsigned __llvm_sjljeh_try_catching_longjmp_exception(void **)
TryCatchLJ =
M.getOrInsertFunction("__llvm_sjljeh_try_catching_longjmp_exception",
- Type::UIntTy, SBPPTy, 0);
+ Type::UIntTy, SBPPTy, NULL);
// bool __llvm_sjljeh_is_longjmp_exception()
IsLJException = M.getOrInsertFunction("__llvm_sjljeh_is_longjmp_exception",
- Type::BoolTy, 0);
+ Type::BoolTy, NULL);
// int __llvm_sjljeh_get_longjmp_value()
GetLJValue = M.getOrInsertFunction("__llvm_sjljeh_get_longjmp_value",
- Type::IntTy, 0);
+ Type::IntTy, NULL);
return true;
}
// "llvm.{setjmp,longjmp}" functions and none of the setjmp/longjmp error
// handling functions (beginning with __llvm_sjljeh_...they don't throw
// exceptions).
-bool LowerSetJmp::IsTransformableFunction(const std::string& Name)
-{
+bool LowerSetJmp::IsTransformableFunction(const std::string& Name) {
std::string SJLJEh("__llvm_sjljeh");
if (Name.size() > SJLJEh.size())
else
new UnwindInst(Inst);
- // Remove all insts after the branch/unwind inst.
- Inst->getParent()->getInstList().erase(Inst,
- Inst->getParent()->getInstList().end());
+ // Remove all insts after the branch/unwind inst. Go from back to front to
+ // avoid replaceAllUsesWith if possible.
+ BasicBlock *BB = Inst->getParent();
+ Instruction *Removed;
+ do {
+ Removed = &BB->back();
+ // If the removed instructions have any users, replace them now.
+ if (!Removed->use_empty())
+ Removed->replaceAllUsesWith(UndefValue::get(Removed->getType()));
+ Removed->eraseFromParent();
+ } while (Removed != Inst);
++LongJmpsTransformed;
}
// The basic block we're going to jump to if we need to rethrow the
// exception.
BasicBlock* Rethrow = new BasicBlock("RethrowExcept", Func);
- BasicBlock::InstListType& RethrowBlkIL = Rethrow->getInstList();
// Fill in the "Rethrow" BB with a call to rethrow the exception. This
// is the last instruction in the BB since at this point the runtime
// should exit this function and go to the next function.
- RethrowBlkIL.push_back(new UnwindInst());
+ new UnwindInst(Rethrow);
return RethrowBBMap[Func] = Rethrow;
}
BasicBlock* DecisionBB = new BasicBlock("LJDecisionBB", Func);
BasicBlock::InstListType& DecisionBBIL = DecisionBB->getInstList();
- LongJmpPreIL.push_back(new BranchInst(DecisionBB, Rethrow, Cond));
+ new BranchInst(DecisionBB, Rethrow, Cond, LongJmpPre);
// Fill in the "decision" basic block.
CallInst* LJVal = new CallInst(GetLJValue, std::vector<Value*>(), "LJVal");
CallInst(TryCatchLJ, make_vector<Value*>(GetSetJmpMap(Func), 0), "SJNum");
DecisionBBIL.push_back(SJNum);
- SwitchInst* SI = new SwitchInst(SJNum, Rethrow);
- DecisionBBIL.push_back(SI);
+ SwitchInst* SI = new SwitchInst(SJNum, Rethrow, 0, DecisionBB);
return SwitchValMap[Func] = SwitchValuePair(SI, LJVal);
}
SetJmpIDMap[Func]++), 0),
"", Inst);
+ // We are guaranteed that there are no values live across basic blocks
+ // (because we are "not in SSA form" yet), but there can still be values live
+ // in basic blocks. Because of this, splitting the setjmp block can cause
+ // values above the setjmp to not dominate uses which are after the setjmp
+ // call. For all of these occasions, we must spill the value to the stack.
+ //
+ std::set<Instruction*> InstrsAfterCall;
+
+ // The call is probably very close to the end of the basic block, for the
+ // common usage pattern of: 'if (setjmp(...))', so keep track of the
+ // instructions after the call.
+ for (BasicBlock::iterator I = ++BasicBlock::iterator(Inst), E = ABlock->end();
+ I != E; ++I)
+ InstrsAfterCall.insert(I);
+
+ for (BasicBlock::iterator II = ABlock->begin();
+ II != BasicBlock::iterator(Inst); ++II)
+ // Loop over all of the uses of instruction. If any of them are after the
+ // call, "spill" the value to the stack.
+ for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
+ UI != E; ++UI)
+ if (cast<Instruction>(*UI)->getParent() != ABlock ||
+ InstrsAfterCall.count(cast<Instruction>(*UI))) {
+ DemoteRegToStack(*II);
+ break;
+ }
+ InstrsAfterCall.clear();
+
// Change the setjmp call into a branch statement. We'll remove the
// setjmp call in a little bit. No worries.
BasicBlock* SetJmpContBlock = ABlock->splitBasicBlock(Inst);
assert(SetJmpContBlock && "Couldn't split setjmp BB!!");
- SetJmpContBlock->setName("SetJmpContBlock");
+ SetJmpContBlock->setName(ABlock->getName()+"SetJmpCont");
- // Reposition the split BB in the BB list to make things tidier.
- Func->getBasicBlockList().remove(SetJmpContBlock);
- Func->getBasicBlockList().insert(++Function::iterator(ABlock),
- SetJmpContBlock);
+ // Add the SetJmpContBlock to the set of blocks reachable from a setjmp.
+ DFSBlocks.insert(SetJmpContBlock);
// This PHI node will be in the new block created from the
// splitBasicBlock call.
CI.getCalledFunction()->isIntrinsic()) return;
BasicBlock* OldBB = CI.getParent();
+
+ // If not reachable from a setjmp call, don't transform.
+ if (!DFSBlocks.count(OldBB)) return;
+
BasicBlock* NewBB = OldBB->splitBasicBlock(CI);
assert(NewBB && "Couldn't split BB of \"call\" instruction!!");
+ DFSBlocks.insert(NewBB);
NewBB->setName("Call2Invoke");
- // Reposition the split BB in the BB list to make things tidier.
Function* Func = OldBB->getParent();
- Func->getBasicBlockList().remove(NewBB);
- Func->getBasicBlockList().insert(++Function::iterator(OldBB), NewBB);
// Construct the new "invoke" instruction.
TerminatorInst* Term = OldBB->getTerminator();
std::vector<Value*> Params(CI.op_begin() + 1, CI.op_end());
InvokeInst* II = new
InvokeInst(CI.getCalledValue(), NewBB, PrelimBBMap[Func],
- Params, CI.getName(), Term);
+ Params, CI.getName(), Term);
// Replace the old call inst with the invoke inst and remove the call.
CI.replaceAllUsesWith(II);
// The old terminator is useless now that we have the invoke inst.
Term->getParent()->getInstList().erase(Term);
+ ++CallsTransformed;
}
// visitInvokeInst - Converting the "invoke" instruction is fairly
if (!IsTransformableFunction(II.getCalledFunction()->getName()) ||
II.getCalledFunction()->isIntrinsic()) return;
- Function* Func = II.getParent()->getParent();
+ BasicBlock* BB = II.getParent();
+
+ // If not reachable from a setjmp call, don't transform.
+ if (!DFSBlocks.count(BB)) return;
BasicBlock* NormalBB = II.getNormalDest();
- BasicBlock* ExceptBB = II.getExceptionalDest();
+ BasicBlock* ExceptBB = II.getUnwindDest();
+ Function* Func = BB->getParent();
BasicBlock* NewExceptBB = new BasicBlock("InvokeExcept", Func);
BasicBlock::InstListType& InstList = NewExceptBB->getInstList();
CallInst(IsLJException, std::vector<Value*>(), "IsLJExcept");
InstList.push_back(IsLJExcept);
- BranchInst* BR = new BranchInst(PrelimBBMap[Func], ExceptBB, IsLJExcept);
- InstList.push_back(BR);
+ new BranchInst(PrelimBBMap[Func], ExceptBB, IsLJExcept, NewExceptBB);
- II.setExceptionalDest(NewExceptBB);
+ II.setUnwindDest(NewExceptBB);
+ ++InvokesTransformed;
}
// visitReturnInst - We want to destroy the setjmp map upon exit from the
// function.
-void LowerSetJmp::visitReturnInst(ReturnInst& RI)
-{
+void LowerSetJmp::visitReturnInst(ReturnInst &RI) {
Function* Func = RI.getParent()->getParent();
new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
"", &RI);
// visitUnwindInst - We want to destroy the setjmp map upon exit from the
// function.
-void LowerSetJmp::visitUnwindInst(UnwindInst& UI)
-{
+void LowerSetJmp::visitUnwindInst(UnwindInst &UI) {
Function* Func = UI.getParent()->getParent();
new CallInst(DestroySJMap, make_vector<Value*>(GetSetJmpMap(Func), 0),
"", &UI);
}
-Pass* createLowerSetJmpPass()
-{
+ModulePass *llvm::createLowerSetJmpPass() {
return new LowerSetJmp();
}
+
projects / oota-llvm.git / blobdiff